思想

1. 快速排序之所以快，一個重要原因就是其每一次遍歷，都把本輪要排序的數字（稱為軸）放到了最終的位置上
2. 快排使用分治思想，所以一般采用遞歸實現，非遞歸版本可以用棧
3. 根據第一點，我們需要一個函數 Partition，用于快速排序中獲得軸的最終位置
4. 根據第二點，在一次遍歷中兩次遞歸調用排序函數，輸入軸兩邊的序列進行排序即可

代碼

• 快速排序本體函數：

//快速排序的本體函數
void QuickSort(int arr[], int low, int high)
{if(low<high){int pivotpos = Partition(arr, low, high);QuickSort(arr, low, pivotpos-1);QuickSort(arr, pivotpos+1, high);}
}

• 獲得軸位置的函數

//此函數用于快速排序中獲得軸的最終位置
int Partition(int arr[], int low, int high)
{int pivot = arr[low];while(low<high){//指針碰撞時軸的左右子序列都排序完成while(low<high && arr[high]>=pivot) high--;arr[low] = arr[high];while(low<high && arr[low]<=pivot) low++;arr[high] = arr[low];}arr[low] = pivot;return low;
}

要點

其中，Partition 很重要，有幾個書寫的要點：

1. 在外循環中指針碰撞時視為排序完成
2. 內循環中，由于兩個指針在遍歷時可能會越界，故需檢測是否碰撞
3. 如果軸選擇了 low 處的元素，那么 low 處可以視為空閑，所以此時要從 high 處開始遍歷，直到找到需要放在軸左邊的元素為止，將這個元素放入 low 處
4. high 處的元素放到 low 處后，high 處可以視為空閑，此時從 low 處開始遍歷，直到找到應該放在軸右邊的元素，將其插入 high 處
5. 指針碰撞后，low == high，將軸放到指針碰撞的位置，并返回此時軸的位置