php如何實現快速排序

php實作快速排序的方法：先建立一個PHP範例檔；然後建立交換函數和主函數；接著對低子表和高子表進行遞歸排序；最後呼叫QuickSort演算法即可。

#推薦：《PHP影片教學》

基本思想：

快速排序（Quicksort）是對冒泡排序的一種改進。他的基本想法是：透過一趟排序將待排記錄分割成獨立的兩部分，其中一部分的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行快速排序，整個排序過程可以遞歸進行，以達到整個序列有序的目的​​。

基本演算法步驟：

舉個栗子：

假如現在待排序記錄是：

6   2   7   3   8   9

第一步、建立變數$low 指向記錄中的第一個記錄，$high 指向最後一個記錄，$pivot 作為樞軸賦值為待排序記錄的第一個元素（不一定是第一個），這裡：

$low = 0;
$high = 5;
$pivot = 6;

第二步、我們要把所有比$pivot 小的數移動到$pivot 的左面，所以我們可以開始尋找比6小的數，從$high 開始，從右往左找，不斷遞減變數$high 的值，我們找到第一個下標3 的資料比6 小，於是把資料3 移到下標0 的位置（$low 指向的位置），把下標0 的資料6 移到下標3，完成第一次比較：

3   2   7   6   8   9

//这时候,$high 减小为 3
$low = 0;
$high = 3;
$pivot = 6;

第三步、我們開始第二次比較，這次要變成找比$pivot 大的了，而且要從前往後找了。遞加變數$low，發現下標2 的資料是第一個比$pivot 大的，於是用下標2 （$low 指向的位置）的資料7 和指向的下標3 （$high 指向的位置）的資料的6 做交換，資料狀態變成下表：

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 3;
$pivot = 6;

完成第二步和第三步我們稱為完成一個迴圈。

第四步（也就是開啟下一個迴圈）、模仿第二步的過程執行。
第五步、模仿第三步的過程執行。

執行完第二個循環之後，資料狀態如下：

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 2;
$pivot = 6;

到了這一步，我們發現 $low 和 $high「碰頭」了：他們都指向了下標 2。於是，第一遍比較結束。得到結果如下，凡是 $pivot(=6) 左邊的數都比它小，凡是 $pivot 右邊的數都比它大。

然後，將 、$pivot 兩邊的資料 {3，2} 和 {7，8，9}，再分組分別進行上述的過程，直到不能再分組為止。

注意：第一遍快速排序不會直接得到最終結果，只會把比k大和比k小的數分到k的兩邊。為了得到最後結果，需要再次對下標2兩邊的陣列分別執行此步驟，然後再分解數組，直到數組不能再分解為止（只有一個資料），才能得到正確結果。

演算法實作：

//交换函数
function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

//主函数：
function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

主函數中，由於第一遍快速排序是對整個陣列排序的，因此開始是$low=0,$high=count($arr)- 1。
然後QSort() 函數是個遞歸呼叫過程，因此對它封裝了一下：

function QSort(array &$arr,$low,$high){
    //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);	//对低子表（$pivot左边的记录）进行递归排序
        QSort($arr,$pivot + 1,$high);	//对高子表（$pivot右边的记录）进行递归排序
    }
}

從上面的QSort（）函數中我們看出，Partition（）函數才是整段程式碼的核心，因為函數的功能是：選取當中的一個關鍵字，例如選擇第一個關鍵字。然後想盡辦法將它放到某個位置，使得它左邊的值都比它小，右邊的值都比它大，我們將這樣的關鍵字成為樞軸（pivot）。

直接上程式碼：

//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴
//使枢轴记录到位，并返回其所在位置
function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端

        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

組合起來的整個程式碼如下：

function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端
        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

function QSort(array &$arr,$low,$high){
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);   //对低子表进行递归排序
        QSort($arr,$pivot + 1,$high);  //对高子表进行递归排序
    }
}

function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

我們呼叫演算法：

$arr = array(9,1,5,8,3,7,4,6,2);
QuickSort($arr);
var_dump($arr);

複雜度分析：

在最優的情況下，也就是選擇數軸處於整個數組的中間值的話，則每一次就會不斷將數組平分為兩半。因此最優情況下的時間複雜度是 O(nlogn) （跟堆排序、歸併排序一樣）。

最壞的情況下，待排序的序列是正序或逆序的，那麼在選擇樞軸的時候只能選到邊緣數據，每次劃分得到的比上一次劃分少一個記錄，另一個分為空，這樣的情況的最終時間複雜度為O(n^2).

綜合最適與最差情況，平均的時間複雜度是O(nlogn).

快速排序是一種不穩定排序方法。

由於快速排序是個比較進階的排序，而且被列為20世紀十大演算法之一。 。 。 。如此牛掰的演算法，我們還有什麼理由不去學他呢！

儘管這個演算法已經很牛了，但是上面的演算法程式依然有改進的地方。

#

以上是php如何實現快速排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！