数据结构与算法-快速排序

快速排序在实际应用中使用广泛，效果也高。快排使用的是分治策略，一组序列基于某一个基准值分成两个大小的子序列，递归排序子序列，最终得到有序的序列。快排的平均时间复杂度为O(nlogn)。

---

算法的实现步骤：

1. 在序列中挑选一个基准值，我们可以默认第一个数为基准值

2. 从两边的数值跟基准值作对比，数值小的放在基准值左边，数值大的放在基准值右边

3. 递归将小于基准值的子序列和大于基准值的子序列排序

例子：

步骤图

乱序序列：4，3，9，7，5，6，8，1

圆圈1:原始序列

圆圈2:以第一个数4为基准值

圆圈3:分成两个子序列，3、1小于基准值4，7、5、6、8、9大于基准值4，进行递归

圆圈4:子序列3、1的基准值为3，子序列7、5、6、8、9的基准值为7

圆圈5:子序列3、1排序后是1、3，递归子序列1，只有一个值直接结束；子序列7、5、6、8、9再分成子序列5、6小于基准值7，子序列8、9大于基准值7，进行递归

圆圈6:子序列5、6的基准值为5，子序列8、9的基准值为8

圆圈7:子序列5、6排序后5、6，递归子序列6，只有一个值直接结束；子项8、9排序后8、9，递归子序列9，只有一个值直接结束

实现代码：

void QuickSort(int nLeft, int nRight, int* pArrayNum) {

    if(nLeft >= nRight) {

        return ;

    }

    int nValue = pArrayNum[nLeft];

    int nMiddle = nLeft;

    int nL = nLeft;

    int nR = nRight;

    nL++;

    while(nL < nR) {

        while((nL != nR) && (pArrayNum[nL] <= nValue)) {

            nL++;

        }

        while((nR != nL) && (pArrayNum[nR] >= nValue)) {

            nR--;

        }

        int nTmpNum = pArrayNum[nL];

        pArrayNum[nL] = pArrayNum[nR];

        pArrayNum[nR] = nTmpNum;

    }

    if(pArrayNum[nR] > nValue) {

        pArrayNum[nMiddle] = pArrayNum[nR-1];

        pArrayNum[nR-1] = nValue;

        QuickSort(nLeft, nR-2, pArrayNum);

        QuickSort(nR, nRight, pArrayNum);

    }

    else {

        pArrayNum[nMiddle] = pArrayNum[nR];

        pArrayNum[nR] = nValue;

        QuickSort(nLeft, nR-1, pArrayNum);

        QuickSort(nR+1, nRight, pArrayNum);

    }

}