php實作快速排序的程式碼範例

這篇文章帶給大家的內容是關於php實現快速排序的程式碼範例，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

快速排序

快速排序（英文：Quicksort），又稱分割交換排序（partition-exchange sort），簡稱快排，一種排序演算法，最早由東尼·霍爾提出。在平均狀況下，排序 n 個項目要 O(n log n) 次比較。在最壞狀況下則需要 O(n2) 次比較，但這種狀況並不常見。事實上，快速排序 O(n log n) 通常明顯比其他演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地達成。

步驟為：

從數列中挑出一個元素，稱為"基準"（pivot），

重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（相同的數可以到任何一邊）。在這個分區結束之後，該基準就處於數列的中間位置。這個稱為分割區（partition）操作。

遞歸地（recursively）將小於基準值元素的子數列和大於基準值元素的子數列排序。

遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個演算法一定會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

維基百科中的介紹。核心的想法是使用遞迴，下面的動圖很形象。

動圖示範

#實例

<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function quickSort($arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    $leftArray = $rightArray = array();
    $middle = $arr[0];// 基准值

    for ($i = 1; $i < $count; $i++) {
        // 小于基准值，存入左边；大于基准值，存入右边
        if ($arr[$i] < $middle) {
            $leftArray[] = $arr[$i];
        } else {
            $rightArray[] = $arr[$i];
        }
    }

    $leftArray = quickSort($leftArray);
    $rightArray = quickSort($rightArray);

    return array_merge($leftArray, array($middle), $rightArray);
    // 倒序
    // return array_merge($rightArray, array($middle), $leftArray);
}

print_r(quickSort($arr));
// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33

以上是php實作快速排序的程式碼範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！