https://blog.csdn.net/nrsc272420199/article/details/82587933
原理:
快速排序,說白了就是給基準資料找其正确索引位置的過程.
如下圖所示,假設最開始的基準資料為數組第一個元素23,則首先用一個臨時變量去存儲基準資料,即tmp=23;然後分别從數組的兩端掃描數組，設兩個訓示标志:low指向起始位置，high指向末尾.
首先從後半部分開始，如果掃描到的值大于基準資料就讓high減1,如果發現有元素比該基準資料的值小(如上圖中18<=tmp)，就将high位置的值指派給low位置 ,結果如下:
然後開始從前往後掃描,如果掃描到的值小于基準資料就讓low加1,如果發現有元素大于基準資料的值(如上圖46=>tmp)，就再将low位置的值指派給high位置的值,指針移動并且資料交換後的結果如下:
然後再開始從後向前掃描,原理同上,發現上圖11<=tmp,則将low位置的值指派給high位置的值,結果如下:
然後再開始從前往後周遊,直到low=high結束循環,此時low或high的下标就是基準資料23在該數組中的正确索引位置.如下圖所示.
這樣一遍走下來,可以很清楚的知道,其實快速排序的本質就是把基準數大的都放在基準數的右邊,把比基準數小的放在基準數的左邊,這樣就找到了該資料在數組中的正确位置.
以後采用遞歸的方式分别對前半部分和後半部分排序，目前半部分和後半部分均有序時該數組就自然有序了。
一些小結論
從上面的過程中可以看到:
①先從隊尾開始向前掃描且當low < high時,如果a[high] > tmp,則high–,但如果a[high] < tmp,則将high的值指派給low,即arr[low] = a[high],同時要轉換數組掃描的方式,即需要從隊首開始向隊尾進行掃描了
②同理,當從隊首開始向隊尾進行掃描時,如果a[low] < tmp,則low++,但如果a[low] > tmp了,則就需要将low位置的值指派給high位置,即arr[low] = arr[high],同時将數組掃描方式換為由隊尾向隊首進行掃描.
③不斷重複①和②,知道low>=high時(其實是low=high),low或high的位置就是該基準資料在數組中的正确索引位置.
按照上訴理論我寫的代碼如下:
void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 找尋基準資料的正确索引
int index = getIndex(arr, low, high);
// 進行疊代對index之前和之後的數組進行相同的操作使整個數組變成有序
quickSort(arr, 0, index - 1);
quickSort(arr, index + 1, high);
}
}
int getIndex(int[] arr, int low, int high) {
// 基準資料
int tmp = arr[low];
while (low < high) {
// 當隊尾的元素大于等于基準資料時,向前挪動high指針
while (low < high && arr[high] >= tmp) {
high--;
}
// 如果隊尾元素小于tmp了,需要将其指派給low
arr[low] = arr[high];
// 當隊首元素小于等于tmp時,向前挪動low指針
while (low < high && arr[low] <= tmp) {
low++;
}
// 當隊首元素大于tmp時,需要将其指派給high
arr[high] = arr[low];
}
// 跳出循環時low和high相等,此時的low或high就是tmp的正确索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,是以需要将tmp指派給arr[low]
arr[low] = tmp;
return low; // 傳回tmp的正确位置
}