题目
我们可以优化快速排序的Pivot的选择。
随机选择？随机选择的开销也不小。
可以考虑用三取样切分，序列的头、尾、当中各取一个元素，用大小居中的元素切分
Pivot的不同取法对运行速度有多大影响？
对于小规模的数据，例如N不到100，快速排序的效率可能还不如插入排序
所以可以设置一个CutOff的阈值，当递归的数据规模充分小，则停止递归，直接调用简单排序
试比较不同的CutOff对效率的影响
思路
- 采用三数中值分割法，将
a[eft],a[center],a[right]中的最小值放在a[left],中值放在a[center]，最大值放在a[right]，再将a[center]放进a[right-1]使pivot离开要分割的数据段 - 由于数据规模较小的时候，插入排序比快排（递归）的效率更高，考虑采用不同的
CUTOFF（截至范围）以提高效率，经尝试，CUTOFF取2000左右效率较佳
代码
#include<bits/stdc++.h>
using namespace std;
#define CUTOFF 2000void Swap(int* a, int* b)
{
int tmp = *a;*a = *b;*b = tmp;
}void insertionSort(int* a, int left, int right)
{
for (int i = left+1; i <= right; i++){
int tmp = a[i];int j = i;for (; j >= left && a[j-1] > tmp; j--){
a[j] = a[j - 1];}a[j] = tmp;}}int Median3(int* a, int left, int right) // 返回pivot
{
/*将三点中的最小值放在left，中位数放在center，最大值放在right*/int center = (left + right) / 2;if (a[left] > a[center])Swap(&a[left], &a[center]);if (a[left] > a[right])Swap(&a[left], &a[right]);if (a[center] > a[right])Swap(&a[center], &a[right]);/*将pivot放在right-1处*/Swap(&a[center], &a[right - 1]);return a[right - 1];
}void quickSort(int* a, int left, int right)
{
if (left + CUTOFF <= right) // 大数组，用快排{
int pivot = Median3(a, left, right);int i = left, j = right - 1;for (;;){
while (a[++i] < pivot);while (a[--j] > pivot);if (i < j) // 需要交换Swap(&a[i], &a[j]);else break; // 本次分割结束}Swap(&a[i], &a[right - 1]);quickSort(a, left, i - 1);quickSort(a, i + 1, right);}else // 小数组，用插入排序insertionSort(a, left, right);
}int main()
{
int n; cin >> n;int* a = new int[n];for (int i = 0; i < n; i++)cin >> a[i];quickSort(a, 0, n - 1);for (int i = 0; i < n-1; i++)cout << a[i] << ' ';cout << a[n - 1] << endl;return 0;
}