PHP快速排序算法實(shí)現(xiàn)的原理及代碼詳解
更新時(shí)間：2019年04月03日 08:29:04 投稿：laozhang
在本篇文章里小編給大家整理了關(guān)于PHP快速排序算法實(shí)現(xiàn)的原理及代碼相關(guān)知識點(diǎn)，需要的朋友們跟著學(xué)習(xí)下。
算法原理
下列動(dòng)圖來自五分鐘學(xué)算法，演示了快速排序算法的原理和步驟。
步驟:
從數(shù)組中選個(gè)基準(zhǔn)值
將數(shù)組中大于基準(zhǔn)值的放同一邊、小于基準(zhǔn)值的放另一邊，基準(zhǔn)值位于中間位置
遞歸的對分列兩邊的數(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);
}
測試代碼:
$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";
測試結(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ù)就是二叉樹的深度，而根據(jù)完全二叉樹的定義，它的深度至少是lg(N+1)。因此，快速排序的遍歷次數(shù)最少是lg(N+1)次。
2) 為什么最多是N次？這個(gè)應(yīng)該非常簡單，還是將快速排序看作一棵二叉樹，它的深度最大是N。因此，快讀排序的遍歷次數(shù)最多是N次。
相關(guān)文章
我PHP手工太菜了， 無奈只能補(bǔ)下PHP MYSQL手工注射，把收集總結(jié)的資料分享下。2009-10-10
目前來說，PHP防止刷票的判斷沒有太可行和完全防止的方法，需要的朋友可以參考下2012-02-02
php下按上下級層次關(guān)系輸出內(nèi)容，需要的朋友可以參考下。2010-07-07
PHP實(shí)現(xiàn)多進(jìn)程并行操作的詳解(可做守護(hù)進(jìn)程)
本篇文章是對PHP實(shí)現(xiàn)多進(jìn)程并行操作進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-06-06
Laravel中使用FormRequest進(jìn)行表單驗(yàn)證方法及問題匯總
Laravel 5.0 帶來了FormRequests, 這是一種特殊的類型, 用于在提交表單時(shí)進(jìn)行數(shù)據(jù)的檢查和驗(yàn)證. 每個(gè)FormRequest類至少包含一個(gè)rules()方法, 這個(gè)方法返回一組驗(yàn)證規(guī)則. 除此之外還必須包含一個(gè)authorize()方法, 該方法返回一個(gè)布爾值, 代表是否允許用戶執(zhí)行本次請求.2016-06-06
這篇文章主要介紹了詳解PHP中mb_strpos的使用，通過使用語法以及實(shí)例給大家詳細(xì)分析了用法，需要的朋友參考學(xué)習(xí)下。2018-02-02
海河寫的 Discuz論壇帖子調(diào)用js的php代碼
海河寫的 Discuz論壇帖子調(diào)用js的php代碼...2007-08-08
PHP實(shí)現(xiàn)登錄搜狐廣告獲取廣告聯(lián)盟數(shù)據(jù)的方法【附demo源碼】
這篇文章主要介紹了PHP實(shí)現(xiàn)登錄搜狐廣告獲取廣告聯(lián)盟數(shù)據(jù)的方法,涉及php基于curl的遠(yuǎn)程數(shù)據(jù)操作相關(guān)技巧,需要的朋友可以參考下2016-10-10
本文給大家分享的是如何把PHP應(yīng)用容器化，以及使用docker在服務(wù)器上部署PHP應(yīng)用，非常的簡單實(shí)用，有需要的小伙伴可以參考下2018-02-02
這篇文章主要給大家介紹了在Ubuntu 16.04系統(tǒng)下安裝PHP 7的全過程，文中介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考價(jià)值，需要的朋友們下面來一起看看吧。2017-03-03