最好情况
最坏情况
平均情况
#include<iostream>
template<class Type>
void Swap(Type &a, Type &b) {
Type c = a;
a = b;
b = c;
}
//划分，返回划分基准索引
template<class Type>
int Partition(Type a[], int p, int r) {
int i = p, j = r + 1;
Type x = a[p];
while (true) {
//从左往右找到比x大的
while (a[++i] < x && i < r);
//从右往左找到比x小的
while (a[--j] > x);
//如果大数在小数右边，则已经划分完成
if (i >= j)break;
Swap(a[i], a[j]);
}
//将x放置到两堆的中间
a[p] = a[j];
a[j] = x;
return j;
}
template<class Type>
void QuickSort(Type a[], int p, int r) {
if (p < r) {//至少两个数才需要排序
//划分成两堆，两堆再分别划分
int q = Partition(a, p, r);
QuickSort(a, p, q - 1);
QuickSort(a, q + 1, r);
}
}
int main() {
std::cout << "quick sort:" << std::endl;
int a[10] = {9, 2, 4, 5, 6, 2, 1, 5, 0, 7};
QuickSort(a, 0, 9);
for (int i : a) {
std::cout << i << " ";
}
return 0;
}
