PHP快速排序算法實(shí)現(xiàn)的原理介紹-創(chuàng)新互聯(lián)
這篇文章主要講解了“PHP快速排序算法實(shí)現(xiàn)的原理介紹”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“PHP快速排序算法實(shí)現(xiàn)的原理介紹”吧！
算法原理
下列動(dòng)圖來(lái)自五分鐘學(xué)算法，演示了快速排序算法的原理和步驟。
步驟:
從數(shù)組中選個(gè)基準(zhǔn)值
將數(shù)組中大于基準(zhǔn)值的放同一邊、小于基準(zhǔn)值的放另一邊，基準(zhǔn)值位于中間位置
遞歸的對(duì)分列兩邊的數(shù)組再排序
代碼實(shí)現(xiàn)
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);
}測(cè)試代碼:
$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";測(cè)試結(jié)果:
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
時(shí)間復(fù)雜度
快速排序的時(shí)間復(fù)雜度在最壞情況下是O(N2)，平均的時(shí)間復(fù)雜度是O(N*lgN)。
這句話很好理解：假設(shè)被排序的數(shù)列中有N個(gè)數(shù)。遍歷一次的時(shí)間復(fù)雜度是O(N)，需要遍歷多少次呢？至少lg(N+1)次，最多N次。
1) 為什么最少是lg(N+1)次？快速排序是采用的分治法進(jìn)行遍歷的，我們將它看作一棵二叉樹(shù)，它需要遍歷的次數(shù)就是二叉樹(shù)的深度，而根據(jù)完全二叉樹(shù)的定義，它的深度至少是lg(N+1)。因此，快速排序的遍歷次數(shù)最少是lg(N+1)次。
2) 為什么最多是N次？這個(gè)應(yīng)該非常簡(jiǎn)單，還是將快速排序看作一棵二叉樹(shù)，它的深度較大是N。因此，快讀排序的遍歷次數(shù)最多是N次。
感謝各位的閱讀，以上就是“PHP快速排序算法實(shí)現(xiàn)的原理介紹”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)PHP快速排序算法實(shí)現(xiàn)的原理介紹這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司，，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！
分享名稱：PHP快速排序算法實(shí)現(xiàn)的原理介紹-創(chuàng)新互聯(lián)
分享地址：http://m.jiaotiyi.com/article/ecejc.html