優化策略
- 三數取樣選樞軸：取
left, mid, right 中位數，避免有序/逆序最壞情況。
- 小區間插入排序：元素數 < 10 時改用插入排序，減少遞歸開銷。
- 迭代式分區：
Hoare 分區雙向掃描，i++/j-- 交換。
完整代碼（含性能測試）
#include <iostream>
#include <functional>
#include <windows.h>
using namespace std;
void quickSort(int* arr, int cnt) {
function getPivot = [&](int* a, int l, int r) {
int m = (l+r)/2;
if (a[l] > a[m]) swap(a[l], a[m]);
if (a[l] > a[r]) swap(a[l], a[r]);
if (a[m] > a[r]) swap(a[m], a[r]);
swap(a[m], a[r-1]);
return a[r-1];
};
function insertSort = [&](int* a, int l, int r) {
for (int i=l+1;i<=r;++i){
int tmp=a[i], j=i;
for(;j>l && a[j-1]>tmp;--j) a[j]=a[j-1];
a[j]=tmp;
}
};
function qk = [&](int* a, int l, int r) {
if (l+9 <= r) {
int pivot = getPivot(a,l,r);
int i=l, j=r-1;
while (true) {
while (a[++i] < pivot);
while (a[--j] > pivot);
if (i < j) swap(a[i],a[j]); else break;
}
swap(a[i], a[r-1]);
qk(a,l,i-1); qk(a,i+1,r);
} else insertSort(a,l,r);
};
qk(arr,0,cnt-1);
}
int main() {
int arr[1000];
for(int i=0;i<500;++i) arr[i] = (i%2)? -i : i;
for(int i=500;i<1000;++i) arr[i] = (i%2)? -i : i;
LARGE_INTEGER f,q1,q2; QueryPerformanceFrequency(&f);
QueryPerformanceCounter(&q1);
quickSort(arr,1000);
QueryPerformanceCounter(&q2);
printf("耗時 %lf ms\n", (q2.QuadPart-q1.QuadPart)*1000.0/f.QuadPart);
return 0;
}
關鍵點解析
