快速排序，平均运行时间O(N log N)，最坏运行时间O(N^2)。
我觉得先看Python版的快排算法(http://www.cnblogs.com/fcyworld/p/6160558.html)比较容易理解。
整体思路：
首先从数组中选出一个值pivot，然后依据这个值pivot，把数组分成大小两部分，然后再分别对这两部
分利用快排。
具体细节：
1.在具体的实现中，因为pivot的选择会对数组的划分产生很大的影响，若划分的不均衡，严重影响排序效率。
为了尽可能消除这种影响，同时取数组中的索引为0，n-1,和中值中的中间值作为pivot。产生pivot的时候，0,n-1
位置上的值已经满足pivot的要求，所以排序时候不需要再考虑，所以把pivot的值保存再n-2位置上。
2.为了把数组划分为两部分，利用双指针i,j。i从前往后掠过小于pivot的值，j从后往前掠过大于pivot的
值，当i,j停止的时候，如果i<j，交换i，j所指位置上的值，否则break；
3.在小的数组中(数组的大小<cutoff)，快排的效率并不高，所以小数组时候利用插入排序
void quicksort(int *nums,int n)
{
qs(nums,,n-);
}
void qs(int*nums,int left,int right)
{
int pv;
int i,j;
int cutoff=;
if(left+cutoff<=right)
{
pv=mid3(nums,left,right);
i=left;
j=right-;
while()
{
while(nums[++i]<pv);
while(nums[--j]>pv);
if(i<j)
swap(nums[i],nums[j]);
else
break;
}
swap(nums[i],nums[right-]);
qs(nums,left,i);
qs(nums,i+,right);
}
else
intersort(nums+left,right-left+);
}
int mid3(int *nums,int left,int right)
{
int center=(left+right)/;
if(nums[left]>nums[center])
swap(nums[left],nums[center]);
if(nums[left]>nums[right])
swap(nums[left],nums[right]);
if(nums[center]>nums[right])
swap(nums[center],nums[right]);
swap(nums[center],nums[right-]);
return nums[right-];
}
void swap(int &m,int &n)
{
m^=n;
n^=m;
m^=n;
}
void intersort(int *nums,int n)
{
int i,j;
int tmp;
for(i=;i<n;i++)
{
tmp=nums[i];
for(j=i;j>&&tmp<nums[j-];j--)
nums[j]=nums[j-];
nums[j]=tmp;
}
}