快速排序在抛，也是一種二分的思想，選取一個基準數谅将，然后將大于和小于基準的元素分別放置于基準數兩邊，然后繼續(xù)按此方法分治基準數的兩側重慢，直至最后一個元素饥臂。
那么快排的實現需要解決以下幾個問題：
- 基準數的選擇
- 元素的查找
- 遞歸調用
- 基準數的歸位
對應處理：
- 通常選取頭或者尾元素
- 一組一組的查找需要交換位置的元素
- 既然是遞歸，就一定要有終止遞歸的臨界條件似踱，要不然肯定會導致調用堆棧溢出
- 歸位隅熙，查找相遇的位置和基準位元素互換
對于第二點，需要注意元素查找的先后順序核芽，以從小到大排序為例：
- 如果 基準數選取的為arr[low] 囚戚， 那么必須先從高位high查找到小于pivot的數，然后再從低位low尋找大于pivot的數轧简，交換驰坊；
- 如果 基準數選取的為arr[high] ， 那么必須先從低位low查找到大于pivot的數哮独，然后再從高位high尋找小于pivot的數拳芙，交換；
原因是皮璧， 當兩側的查找相遇時候舟扎，需要將基準數pivot 和相遇點元素的值交換以正確歸位基準數pivot； 也就是pivot = arr[low] 這種情況 相遇點的元素值必須要小于pivot的值悴务，如果先從低位low查找大于pivot的元素睹限，最終停止的元素大于pivot的話 就會導致歸位失敗惨寿；
要更清晰的看具體的差別邦泄，可以交換下面代碼中的 查找順序删窒，然后斷點一步步查看差別裂垦； 其實我們寫代碼，思路有了肌索，輸入輸出的條件限制清晰后代碼實現可能只需要花20%的時間蕉拢，還有80%的時間則花在一步步的驗證邊界情形上； 這邊查找順序的差別個人就斷點調試了很多遍，也在紙上畫出反例會出現的情況才得以印象深刻晕换。
/* 快速排序 */
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);
}
附上一個網站 https://visualgo.net/sorting 可視化排序的過程
圖片.png
