七大排序之快速排序

<QuickSort> 不稳定排序
相比于冒泡排序，每次交换是跳跃式的，总的比较和交换次数少。
基本思路：确定一个轴点pivot（通常选取第一个元素），其左半边元素都比pivot小，右半边元素都比pivot大。
算法实现：二分式递归，将所有元素逐个转换成pivot的过程。（挖坑填数+分治法）
平均性能：T(n)=O(nlogn)

void QuickSort(int a[],int lo,int hi)
{
    if(hi-lo<2) return;
    int mi=Partition(a,lo,hi);
    QuickSort(a,lo,mi);
    QuickSort(a,mi+1,hi);
}

int Partition(int a[],int lo,int hi)
{
    Swap(a[lo],a[lo+rand()%(hi-lo)]);
    int pivot = a[lo];  //以首元素为候选轴点（挖出第一个坑），经以上交换，等效于随机选取
    //哨兵i从左往右找比pivot大的数，哨兵j从右往左找比pivot小的数
    int i=lo;
    int j=hi;
    while(i<j)
    {
        //j先出动，从右往左找比pivot小的数来填a[i]
        while(i<j && a[j]>= pivot)
            j--;
        if(i<j)
        {
            a[i]=a[j]; //找到a[i]比轴点小，将a[j]填到a[i]中，a[j]就形成了一个新的坑
            i++;
        }
        // 从左向右找大于或等于x的数来填a[j]
        while(i<j && a[i]<= pivot)
            i++;
        if(i<j)
        {
            a[j]=a[i];  //将a[i]填到a[j]中，a[i]就形成了一个新的坑
            j--;
        }
    }
//退出时，两哨兵相遇，有个空坑，将pivot填入其中
    a[i]=pivot;

    return i;
}

---

快速排序还有很多改进版本，如随机选择基准数(已实现)，区间内数据较少时直接用别的方法排序以减小递归深度。