資訊專(zhuān)欄INFORMATION COLUMN
摘要：快速排序定義一個(gè)基準(zhǔn)數(shù)，用于做參照。此輪一直與的位置相遇，當(dāng)兩者相遇的時(shí)候，則將相遇位置的數(shù)與基準(zhǔn)數(shù)進(jìn)行互換。左側(cè)數(shù)組為右側(cè)數(shù)組為左側(cè)數(shù)組用上述方法進(jìn)行排列，變成。利用遞歸，將的數(shù)組參數(shù)左側(cè)進(jìn)行判斷歸位，右側(cè)進(jìn)行判斷歸位，最終返回結(jié)果。
快速排序
定義一個(gè)基準(zhǔn)數(shù)，用于做參照。
定義左右兩側(cè)的起始數(shù)和終止數(shù)，一般是以數(shù)組起始值0，以及數(shù)組長(zhǎng)度-1為開(kāi)始
數(shù)組【0】開(kāi)始，與基準(zhǔn)數(shù)X進(jìn)行判斷，如果比X大，則停止，保留數(shù)組【0】；比X小，則數(shù)組【0】變成數(shù)組【1】（即向右移動(dòng)一位），再與基準(zhǔn)數(shù)X判斷，如此循環(huán)，到符合前面條件停止。
數(shù)組【長(zhǎng)度-1】開(kāi)始，與基準(zhǔn)數(shù)X進(jìn)行判斷，如果比X小，則停止，保留數(shù)組【長(zhǎng)度-1】；
比X大，則數(shù)組【長(zhǎng)度-1】變成數(shù)組【長(zhǎng)度-2】（即向左移動(dòng)一位），再與基準(zhǔn)數(shù)X判斷，如此循環(huán)，到符合前面條件停止。
現(xiàn)在有數(shù)組$arr = [12, 6, 5, 35, 64, 78, 11, 85, 43,46];
我們?nèi)?b>$arr[0]=12為基準(zhǔn)數(shù)$temp。（這邊如果設(shè)置基準(zhǔn)數(shù)是最左邊的，則讓右側(cè)先開(kāi)始判斷值，如果基準(zhǔn)數(shù)設(shè)置是最右邊的數(shù)，則讓左側(cè)開(kāi)始先判斷）
定義變量$i=0; $j=9(數(shù)組長(zhǎng)度-1);
然后從$arr[$j]先開(kāi)始進(jìn)行判斷，如果不符合條件則$j--; $j會(huì)在$arr[6]=11位置停下。
$arr[$i]開(kāi)始進(jìn)行判斷，如果不符合條件則$i--; $i會(huì)在$arr[3]=35位置停下。
$arr[3]與$arr[6]互換。
更換完，數(shù)組是$arr = [12, 6, 5, 11, 64, 78, 35, 85, 43,46];
更換完以后，右側(cè)的$j繼續(xù)先判斷,從$j=6開(kāi)始往左走,此時(shí)$i=3。
$j此輪一直與$i=3的位置相遇，當(dāng)兩者相遇的時(shí)候，則將相遇位置($i=$j)的數(shù)與基準(zhǔn)數(shù)$temp=12進(jìn)行互換。
更換完，數(shù)組是$arr = [11, 6, 5, 12, 64, 78, 35, 85, 43,46];
此時(shí)，基于$arr[3]這個(gè)位置，將數(shù)組拆分為左右兩次數(shù)組，進(jìn)行相同的方式判斷（這里會(huì)用到遞歸的方法）。
左側(cè)數(shù)組為 $left_arr=[11,6,5]; 右側(cè)數(shù)組為 $right_arr=[64,78,35,85,43,46];
左側(cè)數(shù)組用上述方法進(jìn)行排列，變成 $left_arr=[5,6,11];。
右側(cè)數(shù)組用上述方法進(jìn)行排列，首先變成$right_arr=[43,46,35,64,85,78];
這時(shí)，左側(cè)已經(jīng)不需要排列了，因?yàn)?b>$temp=11基準(zhǔn)數(shù)歸位后，右側(cè)沒(méi)有數(shù)組，左側(cè)5<6
右側(cè)還要進(jìn)行排列,$temp=64基準(zhǔn)數(shù)歸位后，左邊數(shù)組為[43,46,35]，右邊數(shù)組[85,78]。
最終右側(cè)會(huì)變成$right_arr=[35,43,46,64,78,85];
最終數(shù)組$arr=[5,6,11,12,35,43,46,64,78,85];
= $right) {
return;
}
//設(shè)置基準(zhǔn)數(shù)，作為比較用的參數(shù)
$temp = $arr[$left];
//$i是左邊起的起始數(shù)值，$j是右邊起的起始數(shù)值
$i = $left;
$j = $right;
//只要兩個(gè)參數(shù)不相等，即兩者不是指向同一個(gè)數(shù)組內(nèi)參數(shù) 則繼續(xù)循環(huán)
while ($i != $j) {
//從數(shù)組右側(cè)開(kāi)始，判斷是否比基準(zhǔn)數(shù)小并且($j>$i)確保從右往左且還未與$i相遇
while ($arr[$j] >= $temp && $j > $i) {
$j--;
}
//從數(shù)組左側(cè)開(kāi)始，判斷是否比基準(zhǔn)數(shù)大并且($j>$i)確保從左往右且還未與$j相遇
while ($arr[$i] <= $temp && $i < $j) {
$i++;
}
/**上述兩個(gè)判斷條件停止時(shí)，$i,$j都會(huì)指向數(shù)組內(nèi)的某個(gè)數(shù)$arr[$i]，$arr[$j]
*并且$arr[$i]是比基準(zhǔn)數(shù)大的，$arr[$j]是比基準(zhǔn)數(shù)小的
*兩者的值進(jìn)行互換
*/
if ($i < $j) {
$t = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $t;
}
}
//當(dāng)$i,$j兩個(gè)參數(shù)相等時(shí)候，則跳出循環(huán)，并且將基準(zhǔn)數(shù)與數(shù)組中（當(dāng)$j=$i的）$arr[$i]內(nèi)的值進(jìn)行互換。
$arr[$left] = $arr[$i];
$arr[$i] = $temp;
//利用遞歸，將$i=$j的數(shù)組參數(shù)左側(cè)進(jìn)行判斷歸位，右側(cè)進(jìn)行判斷歸位，最終返回結(jié)果。
quickSort($left, $i - 1);
quickSort($i + 1, $right);
return;
}
quickSort(0, count($arr) - 1);
//輸出結(jié)果
print_r($arr);
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/22463.html
摘要：快速排序的介紹來(lái)源百度百科快速排序由在年提出。快速排序是面試出現(xiàn)的可能性比較高的，也是經(jīng)常會(huì)用到的一種排序，應(yīng)該重點(diǎn)掌握。前面一個(gè)章節(jié)已經(jīng)講了遞歸了，那么現(xiàn)在來(lái)看快速排序就非常簡(jiǎn)單了。 快速排序就這么簡(jiǎn)單 從前面已經(jīng)講解了冒泡排序、選擇排序、插入排序了，本章主要講解的是快速排序，希望大家看完能夠理解并手寫(xiě)出快速排序的代碼，然后就通過(guò)面試了！如果我寫(xiě)得有錯(cuò)誤的地方也請(qǐng)大家在評(píng)論下指出。 ...
摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時(shí)間復(fù)雜度為?？焖倥判蚍ǖ脑砜焖倥判蚴且环N劃分交換排序，它采用分治的策略，通常稱(chēng)其為分治法。 HTML5學(xué)堂-碼匠：前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法，它們都屬于時(shí)間復(fù)雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法—— 快速排序法 [ 平均時(shí)間復(fù)雜度為O (n l...
摘要：實(shí)現(xiàn)快速排序介紹通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 冒泡排序 介紹 重復(fù)遍歷要排序的元素列，依次比較兩個(gè)相鄰的元素，前一個(gè)元素若比后一個(gè)元素大則互換位置。以升序排序?yàn)槔?，最大的元素?huì)在第一次遍歷后冒泡到數(shù)組的末端。假如數(shù)組...
標(biāo)準(zhǔn)庫(kù)中的sort函數(shù)，是快速排序算法的典型實(shí)現(xiàn)。算法將含有n個(gè)元素的序列排序，平均需要 O(n log n) 時(shí)間。 上周，我提出了測(cè)試一個(gè)程序的性能比測(cè)試其功能更難這個(gè)觀點(diǎn)。確認(rèn)程序的性能達(dá)到標(biāo)準(zhǔn)以及確定標(biāo)準(zhǔn)的含義都十分困難。 接下來(lái)，我會(huì)繼續(xù)討論標(biāo)準(zhǔn)庫(kù)中的sort(排序)函數(shù)。sort函數(shù)實(shí)現(xiàn)了快速排序算法，快速排序算法平均可以在 O(n log n) 時(shí)間內(nèi)對(duì)含有n個(gè)元素的序列進(jìn)行排序...
閱讀 1745·2021-10-18 13:30
閱讀 2637·2021-10-09 10:02
閱讀 2972·2021-09-28 09:35
閱讀 2099·2019-08-26 13:39
閱讀 3532·2019-08-26 13:36
閱讀 1960·2019-08-26 11:46
閱讀 1144·2019-08-23 14:56
閱讀 1703·2019-08-23 10:38
