原理:
快速排序,說白了就是給基準資料找其正确索引位置的過程.
如下圖所示,假設最開始的基準資料為數組第一個元素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的位置就是該基準資料在數組中的正确索引位置.
代碼：
#includevoid Swap(int arr[], int low, int high){ int temp; temp = arr[low]; arr[low] = arr[high]; arr[high] = temp;} int Partition(int arr[], int low, int high){ int base = arr[low]; while(low < high) { while(low < high && arr[high] >= base) { high --; } Swap(arr, low, high); while(low < high && arr[low] <= base) { low ++; } Swap(arr, low, high); } return low;} void QuickSort(int arr[], int low, int high){ if(low < high) { int base = Partition(arr, low, high); QuickSort(arr, low, base - 1); QuickSort(arr, base + 1, high); }} int main(){ int n; scanf("%d