快速排序填坑口訣
快速排序由於排序效率在同為O(N*logN)的幾種排序方法中效率較高,因此經常被採用,再加上快速排序思想----分治法也確實實用,因此在很多筆試面試中出現的機率很高。
直接默寫出快速排序還是有一定難度的,所以一定要弄清楚原理再去記憶而不是去硬背。
快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序。它採用了一種分治的策略,通常稱其為分治法(Divide-and-Conque)。
最常見的實現方法是"填坑法",它的實現步驟如下:
- 選定數列頭元素為基準元素pivot,並記住這個位置index,這個位置相當於一個"坑"。
- 設定兩個指標left和right,分別指向數列的最左和最右兩個元素。
- 接下來從right指標開始,把指標所指向的元素和基準元素做比較,如果比pivot大,則right指標向左移動;如果比pivot小,則把所指向的元素放入index對應的位置。
- 將被放入坑中的元素(right指標移動之前指向的元素)之前的位置賦值給index讓這個位置變成一個新的"坑",同時left指標向右移動一位。
- 接下來切換到left指標進行比較,如果left當前指向的元素小於pivot,則left指標向右移動;如果元素大於pivot,則把元素放入坑中,left指向的位置賦值給index,使其變成一個新的"坑",同時right指標向左移動一位。
- 重複步驟3,4,5直到left等於right時,將pivot放入left和right重合的位置,此時數列中比pivot小的元素都在pivot左邊,比pivot大的都在pivot元素位置的右邊。
- 獲取pivot的位置pivotIndex,分而制之,將pivotIndex左側和右側的子數列分別重複上述步驟1~6,直到不能拆分子數列為止,整個數列就是一個從頭開始遞增的數列。
具體的程式碼實現如下:
<?php class QuickSortClass { public function partition(array &$arr, $startIndex, $endIndex) { // 取第一個元素為基準值 $pivot = $arr[$startIndex]; $left = $startIndex; $right = $endIndex; // 坑的位置,出事等於基準值pivot的位置 $dataIndex = $startIndex; while ($right >= $left) { // right 指標從右向左進行移動,如果當前值小於基準值則將當前元素放到坑中,當前元素的位置變成新坑,left向右移動一個位置,切換到left進行比較,否則right往左移動一個位置繼續用新元素的值與基準值進行比較 while ($right >= $left) { if ($arr[$right] < $pivot) { $arr[$dataIndex] = $arr[$right]; $dataIndex = $right; $left++; break; } $right--; } // left 指標從左往右移動,如果當前值大於基準值則將當前元素放到坑中,當前元素變為新坑,right向左移動一個位置,切換到right進行比較,否則left往右移動一個位置繼續與基準值進行比較 while($right >= $left) { if ($arr[$left] > $pivot) { $arr[$dataIndex] = $arr[$left]; $dataIndex = $left; $right --; break; } $left ++; } } $arr[$dataIndex] = $pivot; return $dataIndex; } public function quickSort(&$arr, $startIndex, $endIndex) { // startIndex大於等於endIndex的時候遞迴結束 if ($startIndex >= $endIndex) { return ; } $pivotIndex = $this->partition($arr, $startIndex, $endIndex); $this->quickSort($arr, $startIndex, $pivotIndex - 1); $this->quickSort($arr, $pivotIndex + 1, $endIndex); } } $quickSortClass = new quickSortClass(); $arr = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85]; $quickSortClass->quickSort($arr, 0, count($arr) - 1); var_dump($arr);
填坑法的口訣如下
1.$left=strart; $right = end; $pivot=$arr[$left];
第一個坑為$arr[$left]
2.$right--
由後向前找比$pivot
小的數,找到後挖出此數填到前一個坑$arr[$left]
中,$arr[$right]
變成新坑。
3.$left++
由前向後找比$pivot
大的數,找到後也挖出此數填到前一個坑$arr[$right]
中。
4.重複執行2,3二步,直到$left==$right
,將基準數$pivot
填入$arr[$left]
中。