快速排序（三数中值、三向切分、转插入排序）

再次优化快速排序，三数中值取理想的pivot，三向切分忽略与pivot相同的元素，小数组转插入排序

（唯一不足递归实现，不过是尾递归，编译器可以优化掉）

代码很短，而且可读性很好，记录于此以供参考

const int cutoff = 3;

void insertSort(int a[], int len)
{
    for (int i = 1; i < len; ++i)
    {
        int j;
        int temp = a[i];
        for (j = i - 1; j >= 0; --j)
        {
            if (a[j] <= temp)
                break;
            a[j + 1] = a[j];
        }
        a[j + 1] = temp;
    }
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quickSort(int a[], int left, int right)
{
    // 转插入排序
    if (left + cutoff > right)
        return insertSort(a + left, right - left + 1);
    // 三数中值 让left为中值
    int center = (left + right) >> 1;
    if (a[left] < a[center])
        swap(&a[left], &a[center]);
    if (a[center] > a[right])
        swap(&a[center], &a[right]);
    if (a[left] > a[right])
        swap(&a[left], &a[right]);
    // 三向切分
    int lt = left, i = left + 1, rt = right;
    int temp = a[left];
    while (i <= rt)
    {
        if (a[i] < temp)
            swap(&a[lt++], &a[i++]);
        else if (a[i] > temp)
            swap(&a[i], &a[rt--]);
        else
            i++;
    }
    quickSort(a, left, lt - 1);
    quickSort(a, rt + 1, right);
}