快速排序的基本思想：快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該基準值將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后左右子序列重復該過程，直到所有元素都排列在相應位置上為止。

1、遞歸版本

遞歸版本實現的主要框架：

void QuickSort(int* arr, int left, int right)
{if(left >= right){return;}int keyi = _QuickSort(arr, left, right);QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi+1, right);
} 

（1）hoare方法

這個函數的作用在于將基準值移到數組正確的位置并返回此處的下標。

left從基準值后一個位置開始移動，當left<=right時進入循環，left循環向前移動找比基準值大的數據，找到跳出循環，left循環向后移動找比基準值小的數據，找到跳出循環，此時若left<=right，交換left和right的數據，right--，left++繼續循環。直到left>right跳出循環，此時right所在的位置就是基準值的正確位置，交換keyi和right的數據，返回right。

int _QuickSort(int* arr, int left, int right)
{int keyi = left;++left;while (left <= right){while (left <= right&&arr[left] < arr[keyi]){++left;}while (left <= right && arr[right] > arr[keyi]){--right;}if (left <= right){swap(&arr[right--], &arr[left++]);}}swap(&arr[keyi], &arr[right]); return right;}

上面代碼有一處需要注意：

以下圖為例：

若存在數組中有很多個相同的值的情況，加等于號的代碼會找到很多個相同的基準值，重復調用多次函數，而不加等于號的代碼可以在一次函數調用中多次交換，避免無效的分割排序

（2）挖坑法

將left所在的位置看作坑，并設為基準值，將基準值用key保存下來，當left<right時進入循環，由于初始的坑在左側，所以right先向后移動，找比基準值小的元素，找到后將right處的下標賦給hole，值也賦給hole，此時right所在的位置成為新的坑，再到left向后移動，找比基準值大的元素，找到后將left處的下標賦給hole，值也賦給hole，此時left所在的位置成為新的坑，繼續循環。

跳出循環后，此時left和right和hole指向同一個位置，這個位置就是基準值的正確位置，將key賦給arr[hole],返回hole。

int _QuickSort1(int* arr, int left, int right)
{int hole = left;int key = arr[hole];while (left < right){while (left <right && arr[right] > arr[key]){--right;}arr[hole] = arr[right];hole = right;while (left <right && arr[left] < arr[key]){++left;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}

（3）lomuto前后指針

定義基準值為left所在的位置，把left賦給prev，cur為prev的后一個位置，當cur<=right時，進入循環，cur在前探路，找比基準值小的元素，若找到了則prev++，將prev和cur所在位置的元素對調，為了避免將同一個元素對調，可以將++prev加入到循環中，寫成如下代碼的形式。

跳出循環后，此時prev所在的位置就是基準值的正確位置，將arr[prev]和arr[keyi]對調，返回prev。

int _QuickSort2(int* arr, int left, int right)
{int keyi = left;int prev = left, cur = prev + 1;while (cur <= right){if (arr[keyi] > arr[cur] && ++prev != cur){swap(&arr[prev], &arr[cur]);}cur++;}swap(&arr[keyi], &arr[prev]);return prev;
}

2、非遞歸版本（用棧實現）

棧的作用在于保存需要排序的序列。先將數組頭尾下標入棧，當棧不為空時進入循環，取兩次棧頂元素分別賦給begin和end，取完后出棧，基準值為begin所在位置的元素，prev為begin所在位置cur為prev后一個元素的下標，prev與cur的作用與雙指針法里的作用一樣，找到基準值的正確位置后將prev賦給keyi，若keyi+1<end則將keyi和end作為新序列的頭尾下標入棧，若begin<keyi-1則將begin和keyi-1作為新序列的頭尾下標入棧，繼續循環。

void QuickSortNonR(int* arr, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (arr[keyi] > arr[cur] && ++prev != cur){swap(&arr[prev], &arr[cur]);}cur++;}swap(&arr[keyi], &arr[prev]);keyi = prev;if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi+1);}if (begin < keyi-1){STPush(&st, keyi-1);STPush(&st, begin);}}STDestroy(&st);
}

快速排序的時間復雜度為