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

算法原理

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

步驟:

代碼實現

function quickSort($arr) $len = count($arr); if ($len = 1) { return $arr; $v = $arr[0]; $low = $up = array(); for ($i = 1; $i $len; ++$i) { if ($arr[$i] $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, 8after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10use 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教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。