資訊專欄INFORMATION COLUMN
摘要：快速排序定義一個基準數，用于做參照。此輪一直與的位置相遇，當兩者相遇的時候，則將相遇位置的數與基準數進行互換。左側數組為右側數組為左側數組用上述方法進行排列，變成。利用遞歸，將的數組參數左側進行判斷歸位，右側進行判斷歸位，最終返回結果。
快速排序
定義一個基準數，用于做參照。
定義左右兩側的起始數和終止數，一般是以數組起始值0，以及數組長度-1為開始
數組【0】開始，與基準數X進行判斷，如果比X大，則停止，保留數組【0】；比X小，則數組【0】變成數組【1】（即向右移動一位），再與基準數X判斷，如此循環，到符合前面條件停止。
數組【長度-1】開始，與基準數X進行判斷，如果比X小，則停止，保留數組【長度-1】；
比X大，則數組【長度-1】變成數組【長度-2】（即向左移動一位），再與基準數X判斷，如此循環，到符合前面條件停止。
現在有數組$arr = [12, 6, 5, 35, 64, 78, 11, 85, 43,46];
我們取$arr[0]=12為基準數$temp。（這邊如果設置基準數是最左邊的，則讓右側先開始判斷值，如果基準數設置是最右邊的數，則讓左側開始先判斷）
定義變量$i=0; $j=9(數組長度-1);
然后從$arr[$j]先開始進行判斷，如果不符合條件則$j--; $j會在$arr[6]=11位置停下。
$arr[$i]開始進行判斷，如果不符合條件則$i--; $i會在$arr[3]=35位置停下。
$arr[3]與$arr[6]互換。
更換完，數組是$arr = [12, 6, 5, 11, 64, 78, 35, 85, 43,46];
更換完以后，右側的$j繼續先判斷,從$j=6開始往左走,此時$i=3。
$j此輪一直與$i=3的位置相遇，當兩者相遇的時候，則將相遇位置($i=$j)的數與基準數$temp=12進行互換。
更換完，數組是$arr = [11, 6, 5, 12, 64, 78, 35, 85, 43,46];
此時，基于$arr[3]這個位置，將數組拆分為左右兩次數組，進行相同的方式判斷（這里會用到遞歸的方法）。
左側數組為 $left_arr=[11,6,5]; 右側數組為 $right_arr=[64,78,35,85,43,46];
左側數組用上述方法進行排列，變成 $left_arr=[5,6,11];。
右側數組用上述方法進行排列，首先變成$right_arr=[43,46,35,64,85,78];
這時，左側已經不需要排列了，因為$temp=11基準數歸位后，右側沒有數組，左側5<6
右側還要進行排列,$temp=64基準數歸位后，左邊數組為[43,46,35]，右邊數組[85,78]。
最終右側會變成$right_arr=[35,43,46,64,78,85];
最終數組$arr=[5,6,11,12,35,43,46,64,78,85];
= $right) {
return;
}
//設置基準數，作為比較用的參數
$temp = $arr[$left];
//$i是左邊起的起始數值，$j是右邊起的起始數值
$i = $left;
$j = $right;
//只要兩個參數不相等，即兩者不是指向同一個數組內參數 則繼續循環
while ($i != $j) {
//從數組右側開始，判斷是否比基準數小并且($j>$i)確保從右往左且還未與$i相遇
while ($arr[$j] >= $temp && $j > $i) {
$j--;
}
//從數組左側開始，判斷是否比基準數大并且($j>$i)確保從左往右且還未與$j相遇
while ($arr[$i] <= $temp && $i < $j) {
$i++;
}
/**上述兩個判斷條件停止時，$i,$j都會指向數組內的某個數$arr[$i]，$arr[$j]
*并且$arr[$i]是比基準數大的，$arr[$j]是比基準數小的
*兩者的值進行互換
*/
if ($i < $j) {
$t = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $t;
}
}
//當$i,$j兩個參數相等時候，則跳出循環，并且將基準數與數組中（當$j=$i的）$arr[$i]內的值進行互換。
$arr[$left] = $arr[$i];
$arr[$i] = $temp;
//利用遞歸，將$i=$j的數組參數左側進行判斷歸位，右側進行判斷歸位，最終返回結果。
quickSort($left, $i - 1);
quickSort($i + 1, $right);
return;
}
quickSort(0, count($arr) - 1);
//輸出結果
print_r($arr);
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/22463.html
摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時間復雜度為。快速排序法的原理快速排序是一種劃分交換排序，它采用分治的策略，通常稱其為分治法。 HTML5學堂-碼匠：前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法，它們都屬于時間復雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法—— 快速排序法 [ 平均時間復雜度為O (n l...
摘要：實現快速排序介紹通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 冒泡排序 介紹 重復遍歷要排序的元素列，依次比較兩個相鄰的元素，前一個元素若比后一個元素大則互換位置。以升序排序為例，最大的元素會在第一次遍歷后冒泡到數組的末端。假如數組...
標準庫中的sort函數，是快速排序算法的典型實現。算法將含有n個元素的序列排序，平均需要 O(n log n) 時間。 上周，我提出了測試一個程序的性能比測試其功能更難這個觀點。確認程序的性能達到標準以及確定標準的含義都十分困難。 接下來，我會繼續討論標準庫中的sort(排序)函數。sort函數實現了快速排序算法，快速排序算法平均可以在 O(n log n) 時間內對含有n個元素的序列進行排序...
閱讀 1740·2021-10-18 13:30
閱讀 2621·2021-10-09 10:02
閱讀 2969·2021-09-28 09:35
閱讀 2097·2019-08-26 13:39
閱讀 3529·2019-08-26 13:36
閱讀 1956·2019-08-26 11:46
閱讀 1139·2019-08-23 14:56
閱讀 1700·2019-08-23 10:38
