int Partition(int *a,int left,int right)
{
int pivotkey;
pivotkey=a[left];
while (left<right)
{
while (left<right && a[right]>=temp)
--right;
//a[left]=a[right];
swap(a[left], a[right]);
while (left<right && a[left]<=temp)
++left;
//a[right]=a[left];
swap(a[left],a[right]);
}
//a[left]=temp;
return left;
}
void QuickSort(int *a,int left,int right)
{
int pivot;
if (left>=right)
return;
pivot=Partition(a,left,right);
QuickSort(a,left,pivot-1);
QuickSort(a,pivot+1,right);
}
复杂度分析
快排最优的复杂度为o(nlogn)
最差时的复杂度为正序或逆序时候，复杂度为o(n^2)
因为采用递归，造成栈空间的使用，空间复杂度为o(nlogn),
快速排序优化
优化选取的枢轴：
选取三个数，取中间大小的数作为枢轴，一般选取最左边，中间和最右边的三个数优化不必要的交换：
如代码上 // 的代码当数组较小时候，采用插入排序算法
