快排及优化

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),

快速排序优化

1. 优化选取的枢轴：
   选取三个数，取中间大小的数作为枢轴，一般选取最左边，中间和最右边的三个数

2. 优化不必要的交换：
   如代码上 // 的代码

3. 当数组较小时候，采用插入排序算法