算法原理
下列動圖來自五分鐘學算法，演示了快速排序算法的原理和步驟。
步驟:
從數組中選個基準值
將數組中大于基準值的放同一邊、小于基準值的放另一邊，基準值位于中間位置
遞歸的對分列兩邊的數組再排序
代碼實現
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, 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排序算法之快速排序(Quick Sort)及其優化算法詳解
- PHP遞歸實現快速排序的方法示例
- php 二維數組快速排序算法的實現代碼
- PHP常用排序算法實例小結【基本排序，冒泡排序，快速排序，插入排序】
- PHP快速排序quicksort實例詳解
