PHP快速排序演算法實現的原理及程式碼介紹

這篇文章帶給大家的內容是關於PHP快速排序演算法實現的原理及程式碼介紹，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

演算法原理

下列動圖來自五分鐘學演算法，示範了快速排序演算法的原理與步驟。

步驟:

• #從陣列中選個基準值
• 將陣列中大於基準值的放同一邊、小於基準值的放另一面，基準值位於中間位置
• 遞歸的對分列兩邊的陣列再排序

程式碼實作

function quickSort($arr)
{
    $len = count($arr);
    if ($len  $v) {
            $up[] = $arr[$i];
        } else {
            $low[] = $arr[$i];
        }
    }
    $low = quickSort($low);
    $up = quickSort($up);

    return array_merge($low, array($v), $up);
}

測試程式碼:

$startTime = microtime(1);

$arr = range(1, 10);
shuffle($arr);

echo "before sort: ", implode(', ', $arr), "\n";
$sortArr = quickSort($arr);
echo "after sort: ", implode(', ', $sortArr), "\n";

echo "use time: ", microtime(1) - $startTime, "s\n";

測試結果:

before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8
after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
use time: 0.0009009838104248s

時間複雜度

快速排序的時間複雜度在最壞情況下是O (N2)，平均的時間複雜度是O(N*lgN)。

這句話很好理解：假設被排序的數列中有N個數。遍歷一次的時間複雜度是O(N)，需要遍歷多少次呢？至少lg(N 1)次，最多N次。

1) 為什麼最少是lg(N 1)次？快速排序是採用的分治法進行遍歷的，我們將它看作一棵二元樹，它需要遍歷的次數就是二元樹的深度，而根據完全二元樹的定義，它的深度至少是lg(N 1)。因此，快速排序的遍歷次數最少是lg(N 1)次。

2) 為什麼最多是N次？這個應該非常簡單，還是將快速排序看作一棵二元樹，它的深度最大是N。因此，快讀排序的遍歷次數最多是N次。

【相關推薦：PHP影片教學】

#

以上是PHP快速排序演算法實現的原理及程式碼介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！