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);
}

復雜度分析

快排最優(yōu)的復雜度為o(nlogn)
最差時的復雜度為正序或逆序時候，復雜度為o(n^2)
因為采用遞歸，造成?？臻g的使用，空間復雜度為o(nlogn),

快速排序優(yōu)化

1. 優(yōu)化選取的樞軸：
   選取三個數(shù)，取中間大小的數(shù)作為樞軸，一般選取最左邊，中間和最右邊的三個數(shù)

2. 優(yōu)化不必要的交換：
   如代碼上 // 的代碼

3. 當數(shù)組較小時候，采用插入排序算法