数据结构与算法-快速排序
快速排序在实际应用中使用广泛，效果也高。快排使用的是分治策略，一组序列基于某一个基准值分成两个大小的子序列，递归排序子序列，最终得到有序的序列。快排的平均时间复杂度为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);}}