参考资料：
[1]啊哈！算法 第3节 最常用的排序--快速排序（特别形象）
[2]http://www.cnblogs.com/skywang12345/p/3596746.html
#include<iostream>
using namespace std;
void QuickSort(int *a, int nLeft, int nRight)
{
if (a == nullptr || nLeft > nRight)
return;
//定义1个基准点，然后从右往左找第一个小于基准点的数，再从左往右找第一个大于基准点的数
//如果两个哨兵相遇，那么就和基准值相换
int nTmp = a[nLeft];
int i = nLeft;
int j = nRight;
while (i != j)
{
while (a[j] >= nTmp && i < j)
{
j--;
}
while (a[i] <= nTmp && i < j)
{
i++;
}
if (i != j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
a[nLeft] = a[i];
a[i] = nTmp;
QuickSort(a,nLeft,i-1);
QuickSort(a,i+1,nRight);
}
int main()
{
int a[10] = {10,9,8,6,5,3,2,1,4,7};
int nLen = sizeof(a) / sizeof(a[0]);
cout << nLen<<endl;
for (int i = 0; i < nLen; i++)
{
cout << a[i] << " ";
}
cout << endl;
//BubbleSort(a,nLen);
QuickSort(a,0,nLen-1);
for (int i = 0; i < nLen; i++)
{
cout << a[i] << " ";
}
system("pause");
}
快速排序的复杂度最坏情况下和冒泡排序是一样的，为O(N^2)。平均时间复杂度为O(N*logN)。
