快速排序（终极版）

1.思路
基本快速排序程序有两种写法，双指针法和选定某一方向以此遍历法，这两种方法在代码中分别对应PartitionDownSTD函数和PartitionUp函数。
在基本快速排序的基础上可以进行优化，其中包括“三数取中确定key值”、“数组较小时选用插入排序”、“聚集相等元素”、“尾递归优化”等。

2.代码

#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

const int K = 3;

void InitArr(int *nArr, int nLen) {     //初始化数组
    srand(10); //确保每次初始化的数组相同
    for(int i = 0; i < nLen; ++i) {
        nArr[i] = rand() % 10;
        //nArr[i] = i;
    }
}

void PrintArr(int *nArr, int nLen) {
    for(int i = 0; i < nLen; ++i) {
        cout << nArr[i] << " ";
    }
    cout << endl;
}

void Swape(int *p1, int *p2) {
    int nTmp = *p1;
    *p1 = *p2;
    *p2 = nTmp;
}

void RandomSort(int *nArr, int nLen) {
    srand(10);
    for(int i = 0; i < nLen; ++i) {
        int nIndex = rand() % nLen;
        Swape(&nArr[i], &nArr[nIndex]);
        //Sleep(2000);                       //等待2s，更新随机种子
    }
}



//递增排序
int PartitionUp(int *nArr, int nLeft, int nRight) {
    int nKey = nArr[nRight];
    int i = nLeft - 1;

    for(int j = nLeft; j < nRight; ++j) {
        if(nArr[j] < nKey) {    //反正不稳定，就用<代替≤，省取相等情况下多余的交换运行时间
            i++;
            Swape(&nArr[j], &nArr[i]);     //不稳定排序的原因 eg:1 5 8 8 6 11 7
        }
    }
    Swape(&nArr[i + 1], &nArr[nRight]); //将主元素插入到中间
    return i + 1;
}

//递增排序，双指针实现
int PartitionDownSTD(int *nArr, int nLeft, int nRight) {
    int i = nLeft;
    int j = nRight + 1;

    while(true) {
        while(nArr[++i] < nArr[nLeft]) {
            if(i == nRight) break;
        }
        while(nArr[--j] > nArr[nLeft]) {
            if(j == nLeft) break;
        }
        if(i >= j) break;
        Swape(&nArr[i], &nArr[j]);
    }
    Swape(&nArr[nLeft], &nArr[j]);
    return j;
}


//递减排序
int PartitionDown(int *nArr, int nLeft, int nRight) {
    int nKey = nArr[nRight];
    int i = nLeft - 1;

    for(int j = nLeft; j < nRight; ++j) {
        if(nArr[j] > nKey) {
            ++i;
            Swape(&nArr[i], &nArr[j]);          //不稳定排序的原因
        }
    }
    Swape(&nArr[i + 1], &nArr[nRight]);       //将主元素插入到中间
    return i + 1;
}

void SelectIndex(int *nArr, int nLeft, int nRight) {
    /*引入的原因：虽然随机选取枢轴时，减少出现不好分割的几率，
      但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中选取枢轴*/
    int nMid = nLeft + ((nRight - nLeft) >> 1);
    if(nArr[nMid] > nArr[nRight]) {  //目标:nArr[nMid] <= nArr[nRight]
        Swape(&nArr[nMid], &nArr[nRight]);
    }
    if(nArr[nLeft] > nArr[nRight]) { //目标:nArr[nLeft] <= nArr[nRight]
        Swape(&nArr[nLeft], &nArr[nRight]);
    }
    if(nArr[nLeft] > nArr[nMid]) {   //目标:nArr[nLeft] <= nArr[nMid]
        Swape(&nArr[nLeft], &nArr[nMid]);
    }
    /*此时：nArr[nLeft] <= nArr[nMid] <= nArr[nRight]
      将选择的数与nArr[nRight]交换，即将选择的数作为Key值进行排序
      该方法对升序数组的排序时间优化明显，但对于降序数组，由于Swape执行的次数较多，相比于随机选取法耗时较多*/
    Swape(&nArr[nMid], &nArr[nRight]);

}

int RandomPartition(int *nArr, int nLeft, int nRight) {

    SelectIndex(nArr, nLeft, nRight);
    return PartitionUp(nArr, nLeft, nRight);
}

void InsertSort(int *nArr, int nLeft, int nRight) {
    for(int i = nLeft + 1; i <= nRight; ++i) {
        int nTmp = nArr[i];
        int j;
        for(j = i - 1; j >= nLeft && nArr[j] > nTmp; --j) {
            nArr[j + 1] = nArr[j];
        }
        nArr[j + 1] = nTmp;
    }
}

void QuickSortSTD(int *nArr, int nLeft, int nRight) {
    if(nLeft >= nRight) return;

    //分解
    int nTmpPos = PartitionDownSTD(nArr, nLeft, nRight);

    //解决、合并
    QuickSortSTD(nArr, nLeft, nTmpPos - 1);
    QuickSortSTD(nArr, nTmpPos + 1, nRight);

}

void QuickSortRandom(int *nArr, int nLeft, int nRight) {
    if(nLeft < nRight) {
        int nTmpPos = RandomPartition(nArr, nLeft, nRight);
        QuickSortRandom(nArr, nLeft, nTmpPos - 1);
        QuickSortRandom(nArr, nTmpPos + 1, nRight);
    }
}

void QuickInsertSortRandom(int *nArr, int nLeft, int nRight) {
    if(nLeft < nRight) {
        if(nRight - nLeft > K) {
            int nTmpPos = RandomPartition(nArr, nLeft, nRight);
            QuickInsertSortRandom(nArr, nLeft, nTmpPos - 1);
            QuickInsertSortRandom(nArr, nTmpPos + 1, nRight);
        } else {
            InsertSort(nArr, nLeft, nRight);
        }
    }
}

//尾递归优化
void QuickInsertSortRandomTail(int *nArr, int nLeft, int nRight) {
    if(nRight - nLeft <= K) {
        InsertSort(nArr, nLeft, nRight);
        return;
    }

    while(nLeft < nRight) {
        int nTmpPos = RandomPartition(nArr, nLeft, nRight);
        QuickInsertSortRandom(nArr, nLeft, nTmpPos - 1);
        nLeft = nTmpPos + 1;
    }
}

//带聚集相等元素的递增快速排序
void QuickInsertSameSortRandom(int *nArr, int nLeft, int nRight) {
    if(nRight - nLeft <= K) {             //数组较短，采用插入排序
        InsertSort(nArr, nLeft, nRight);
        return;
    }

    int i = nLeft - 1, j = nRight;
    int p = nLeft - 1, q = nRight;

    SelectIndex(nArr, nLeft, nRight);    //3 Random Choose Key Value
    int key = nArr[nRight];

    while(true) {
        while(nArr[++i] < key)
            if(i == nRight) break;
        while(nArr[--j] > key)
            if(j == nLeft) break;

        //pointers cross
        if(i == j && nArr[i] == key)
            Swape(&nArr[++p], &nArr[i]);
        if(i >= j) break;

        Swape(&nArr[i], &nArr[j]);

        if(nArr[i] == key)
            Swape(&nArr[i], &nArr[++p]);
        if(nArr[j] == key)
            Swape(&nArr[j], &nArr[--q]);
    }

    //将相等元素交换到中间，结束时j指向较小数组集的末尾，i情况不定
    i =  j + 1;
    for(int k = nLeft; k <= p; ++k)
        Swape(&nArr[k], &nArr[j--]);
    for(int k = nRight; k >= q; --k)
        Swape(&nArr[k], &nArr[i++]);

    QuickInsertSameSortRandom(nArr, nLeft, j);
    QuickInsertSameSortRandom(nArr, i, nRight);

}


int main() {
    int Len = 50000;
    int Arr1[Len], Arr2[Len], Arr3[Len], Arr4[Len], Arr5[Len];
    time_t t1, t2, t3, t4, t5, t6;

    InitArr(Arr1, Len);
    InitArr(Arr2, Len);
    InitArr(Arr3, Len);
    InitArr(Arr4, Len);
    InitArr(Arr5, Len);




//    PrintArr(Arr, Len);
//    RandomSort(Arr, Len);
//    PrintArr(Arr, Len);

    t1 = clock();
    QuickSortSTD(Arr1, 0, Len - 1);
    t2 = clock();
    QuickInsertSortRandom(Arr2, 0, Len - 1);
    t3 = clock();
    QuickInsertSameSortRandom(Arr3, 0, Len - 1);
    t4 = clock();
    InsertSort(Arr4, 0, Len - 1);
    t5 = clock();
    sort(Arr5, Arr5 + 100000);
    t6 = clock();


    cout << "QuickSortSTD costs: " << double(t2 - t1)/CLOCKS_PER_SEC << "s" << endl;
    cout << "QuickInsertSortRandom costs: " << double(t3 - t2)/CLOCKS_PER_SEC << "s" << endl;
    cout << "QuickInsertSameSortRandom costs: " << double(t4 - t3)/CLOCKS_PER_SEC << "s" << endl;
    cout << "InsertSort costs: " << double(t5 - t4)/CLOCKS_PER_SEC << "s" << endl;
    cout << "STL_Sort costs: " << double(t6 - t5)/CLOCKS_PER_SEC << "s" << endl;
//    PrintArr(Arr, Len);
    return 0;
}

3.运行结果

该待排序数组包含极多重复数据，从结果中可以看出，三数取中+插排+聚集相等元素的方法效果最佳，其次为基本快排（因为裸的快排比较函数运行较少），再后面依次为：STL库sort函数、三数取中+插入、插入排序。在网上找到的其他人做的实验结果如下：

这里效率最好的快排组合 是：三数取中+插排+聚集相等元素,它和STL中的Sort函数效率差不多。注意：由于测试数据不稳定，数据也仅仅反应大概的情况。如果时间上没有成倍的增加或减少，仅仅有小额变化的话，我们可以看成时间差不多。

补充：
快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化
优点：如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。

void QSort(int arr[],int low,int high)
{ 
    int pivotPos = -1;
    if (high - low + 1 < 10)
    {
        InsertSort(arr,low,high);
        return;
    }
    while(low < high)
    {
        pivotPos = Partition(arr,low,high);
        QSort(arr,low,pivot-1);
        low = pivot + 1;
    }
}

递归调用函数，当调用次数太多时，真的很容易卡死……