快速排序

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

1.hoare版本

簡單來說就是選某個元素為基準值（這里先默認第一個），然后把比基準值小的都放到基準值的左邊，比基準值大的都放到基準值的右邊

以下圖為例

先以6為基準

然后左邊找大，右邊找小，之后互換

進行這么一趟后，6左邊就都比它小，右邊都比它大

然后以6為分界線，再分成兩個區間，類似于二叉樹

void QuickSort(int* a, int left, int right) {if (left >= right) return;//區間不存在時直接返回int keyi=left;int begin=left,end=right;while (begin < end) {// 從右向左找小于基準的值while (begin < end && a[end] >= a[keyi]){end--;}// 從左向右找大于基準的值while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}// 將基準放到正確位置Swap(&a[keyi], &a[end]);// 遞歸排序子數組QuickSort(a, left, end - 1);QuickSort(a, end + 1, right);}
}

算法優化

雖然基本快速排序已經很快，但在某些情況下性能會下降，特別是當輸入數組已經有序或接近有序時。以下是兩種常見的優化策略：

三數取中法

當數組已經有序或接近有序時，選擇第一個元素作為基準會導致分區極度不平衡，從而使算法退化為 O(n2) 的時間復雜度。三數取中法通過選擇左端、中間和右端三個元素的中值作為基準，可以有效避免這種最壞情況。

三數取中代碼如下

int GetMidi(int* a, int left, int right)//左邊作key 右邊先走
{int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right]){//說明midi是中間值return midi;}//走到這說明midi最大，所以剩下兩個數中大的就是中間值else if(a[left]>a[right]){return left;}else//剩下最后一種情況 不必多說{return right;}}else//走到這說明 a[left]>a[midi]{if (a[midi] > a[right]){return midi;}//到這說明midi最小 所以找剩下兩個小的else if (a[left] < a[right]){return left;}else{return right;}}

小區間優化

區間比較小時，遞歸代價比較大，所以要進行小區間優化

對于遞歸來說

最后一層遞歸次數占總體的50%，倒數第二層25% ，所以進行小區間優化可以減少遞歸次數

	//區間比較小時。進行小區間優化，不再遞歸分割排序。減少遞歸次數if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);}

完整代碼如下

#include<stdio.h>void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void InsertSort(int* a, int n) 
{for (int i = 1; i < n; i++) {int key = a[i];int j = i - 1;while (j >= 0 && a[j] > key) {a[j + 1] = a[j];j--;}a[j + 1] = key;}
}
//面試手撕快排 不用寫小區間優化和三數取中 后續講一下思路即可 不然會覺得你寫的慢
//避免有序情況下效率降低
//1.隨機數
//2。三數取中
int GetMidi(int* a, int left, int right)//左邊作key 右邊先走
{int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right]){//說明midi是中間值return midi;}//走到這說明midi最大，所以剩下兩個數中大的就是中間值else if(a[left]>a[right]){return left;}else//剩下最后一種情況 不必多說{return right;}}else//走到這說明 a[left]>a[midi]{if (a[midi] > a[right]){return midi;}//到這說明midi最小 所以找剩下兩個小的else if (a[left] < a[right]){return left;}else{return right;}}
}
void QuickSort(int* a, int left, int right) {if (left >= right) return;//小區間優化，不再遞歸分割排序。減少遞歸次數if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);}else{//三數取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left + 1;  // 從基準下一個開始int end = right;while (begin <= end) {// 從右向左找小于基準的值while (begin <= end && a[end] >= a[keyi])end--;// 從左向右找大于基準的值while (begin <= end && a[begin] <= a[keyi])begin++;// 交換找到的不符合元素if (begin < end)Swap(&a[begin], &a[end]);}// 將基準放到正確位置Swap(&a[keyi], &a[end]);// 遞歸排序子數組QuickSort(a, left, end - 1);QuickSort(a, end + 1, right);}
}int main() {int arr[3] = { 2, 1, 3 };QuickSort(arr, 0, 2);for (int i = 0; i < 3; i++) {printf("%d ", arr[i]);  // 輸出：1 2 3}return 0;
}

為什么要右邊先走呢

分析如下圖

算法分析

時間復雜度

O(n log n)：一共有logn層遞歸 每一層都是所有子數組加起來都是n

空間復雜度

• 最佳情況：O(log n) - 遞歸調用的棧空間
• 最壞情況：O(n) - 當分區極度不平衡時

2.前后指針法

前后指針法是快速排序的另一種常見實現方式，通過兩個指針prev和cur來遍歷數組，將小于基準值的元素移動到前面。

排序過程

• 定義兩個指針prev和cur，prev指向left，cur指向prev+1。
• cur指針向右移動，如果a[cur]小于基準值，則prev++并交換a[prev]和a[cur]。
• 最后將基準值交換到prev位置。

排序一趟的代碼如下

int prev = left;
int cur = prev+1;
while(cur<=right)
{if(a[cur]<a[keyi]&&++prev!=cur)//cur比基準小就交換Swap(&a[prev],&a[cur])//cur不管交換還是不交換，都要繼續走cur++
}
Swap(&a[prev],&a[keyi]);
return prev;

完整代碼

int PartSort2(int* a, int left, int right)
{// 三數取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int prev = left;int cur = prev+1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);cur++;}Swap(&a[prev], &a[keyi]);return prev;
}
void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort1(a, left, right);// [left, keyi-1] keyi [keyi+1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

3.非遞歸（棧模擬）

遞歸實現雖然簡潔，但在處理大規模數據時可能導致棧溢出。非遞歸實現通過顯式棧來模擬遞歸過程，避免遞歸帶來的棧開銷。

實現思路

1. 初始化一個棧，將初始左右下標入棧（先右后左）。
2. 循環取出棧頂的左右下標，進行分區操作。
3. 將分區后的左右子數組下標入棧，繼續處理直到棧為空。

void QuickSortNonR(int* a, 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 = PartSort2(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi+1);}if (begin < keyi-1){STPush(&st, keyi-1);STPush(&st, begin);}}STDestroy(&st);
}

總結

快速排序是一種高效且應用廣泛的排序算法，通過分治策略將問題分解為子問題處理。其性能取決于基準值的選擇是否合理，因此在實際應用中常采用三數取中等優化策略來避免最壞情況的發生。

無論是遞歸還是非遞歸實現，快速排序都能在平均情況下達到O(n log n)的時間復雜度，使其成為處理大規模數據的理想選擇之一