快速排序，也是一種二分的思想，選取一個基準數(shù)，然后將大于和小于基準的元素分別放置于基準數(shù)兩邊，然后繼續(xù)按此方法分治基準數(shù)的兩側(cè)，直至最后一個元素。
那么快排的實現(xiàn)需要解決以下幾個問題：
- 基準數(shù)的選擇
- 元素的查找
- 遞歸調(diào)用
- 基準數(shù)的歸位
對應(yīng)處理：
- 通常選取頭或者尾元素
- 一組一組的查找需要交換位置的元素
- 既然是遞歸，就一定要有終止遞歸的臨界條件，要不然肯定會導致調(diào)用堆棧溢出
- 歸位，查找相遇的位置和基準位元素互換
對于第二點，需要注意元素查找的先后順序，以從小到大排序為例：
- 如果 基準數(shù)選取的為arr[low] ， 那么必須先從高位high查找到小于pivot的數(shù)，然后再從低位low尋找大于pivot的數(shù)，交換；
- 如果 基準數(shù)選取的為arr[high] ， 那么必須先從低位low查找到大于pivot的數(shù)，然后再從高位high尋找小于pivot的數(shù)，交換；
原因是， 當兩側(cè)的查找相遇時候，需要將基準數(shù)pivot 和相遇點元素的值交換以正確歸位基準數(shù)pivot； 也就是pivot = arr[low] 這種情況 相遇點的元素值必須要小于pivot的值，如果先從低位low查找大于pivot的元素，最終停止的元素大于pivot的話 就會導致歸位失??；
要更清晰的看具體的差別，可以交換下面代碼中的 查找順序，然后斷點一步步查看差別； 其實我們寫代碼，思路有了，輸入輸出的條件限制清晰后代碼實現(xiàn)可能只需要花20%的時間，還有80%的時間則花在一步步的驗證邊界情形上； 這邊查找順序的差別個人就斷點調(diào)試了很多遍，也在紙上畫出反例會出現(xiàn)的情況才得以印象深刻。
/* 快速排序 */
function quickSortUnit(arr,low,high){
var temp,
pivot = arr[high];
while(low < high){
/* 查找順序要和基準選取相反；
pivot = arr[high] 則必須先從low開始；
反之 pivot = arr[low]; 則必須先從high開始查找 */
while(arr[low] <= pivot && low < high)
low++;
arr[high] = arr[low];
while(arr[high] >= pivot && low < high)
high--;
arr[low] = arr[high];
}
// 校準，將基準移至正確位置
arr[low] = pivot;
return low;
}
function quickSort(arr,low,high){
if(low >= high) return;
var index = quickSortUnit(arr,low,high);
quickSort(arr,low,index-1);
quickSort(arr,index+1,high);
}
附上一個網(wǎng)站 https://visualgo.net/sorting 可視化排序的過程
圖片.png
