• 快速排序

一次partion的過(guò)程.png

2.png

int Partion(vector<int> &vec, int lo, int hi)  
{
    int i = lo;
    int j = hi;
    int targetNum = vec[lo];
  
    while(true)
    {
        while(vec[i] <= targetNum && i < hi)      // 找到大于 targetNum
            i++;
        while(vec[j] >= targetNum && j > lo)      // 找到小于 targetNum
            j--;

        if (i < j)
            swap(vec[i], vec[j]);
        else
            break;
    }
    swap(vec[j], vec[lo]);

    return j;
}

void QuickSort(vector<int> &vec, int lo, int hi)  
{
    if (lo < hi)  
    {
        int j = Partion(vec, lo, hi);
        QuickSort(vec, lo, j-1);
        QuickSort(vec, j+1, hi);
    }
}

• 優(yōu)化

  • 三點(diǎn)中值
    快速排序的效率與切分有很大關(guān)系，在選擇樞軸時(shí)，我們可以采用取整 個(gè)序列的頭，尾，中央3個(gè)位置的元素，再以其中值最為樞軸，這種做法被稱為median-of-three partitioning。

  • 加入插入排序
    在快速排序塊要完成的時(shí)候，這時(shí)候序列已經(jīng)大部分已經(jīng)處于有序的狀態(tài)，這時(shí)候我們?cè)俨捎貌迦肱判蚴菚?huì)有更高的效率。STL中的sort即是采用此方法。

應(yīng)用1：數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字

數(shù)組中有1個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，那么假設(shè)把這個(gè)數(shù)組排序，那么排序之后的位于數(shù)組中間的數(shù)字一定就是那個(gè)出現(xiàn)次數(shù)超過(guò)數(shù)組長(zhǎng)度一半的數(shù)字。（中位數(shù)）

受快速排序partion的啟發(fā)，我們先選隨機(jī)選擇一個(gè)數(shù)執(zhí)行一次partion。
如果它的下標(biāo)等于n/2，那么它就是中位數(shù)。
如果它的下標(biāo)小于n/2，那么中位數(shù)一定在右半邊，繼續(xù)在它的右半邊查找。
如果它的下標(biāo)大于n/2，那么中位數(shù)一定在左半邊，繼續(xù)在它的左半邊查找。

圖示.png

/* 以下假定存在出現(xiàn)次數(shù)超過(guò)一半的數(shù)字 */
int MoreThanHalfNum(vector<int> vec, int middle) 
{
    int j = Partion(vec, 0, vec.size()-1);

    while(j != middle) 
    {
       if (j > middle)
           j = partion(vec, 0, j-1);
       else
           j = partion(vec, j+1, vec.size()-1);   
   }

   return vec[j];
}

應(yīng)用2：第k大的數(shù)

受上題的啟發(fā)，我們發(fā)現(xiàn)Partion之后，就可以確定第k大的數(shù)（j）。

 /* 從0開(kāi)始排名 */
int Knums(vector<int> vec, int k) 
{   
    if (k < 0 || k >= vec.size())
        throw ("參數(shù)超出范圍");
    
    int j = partion(vec, 0, vec.size()-1);
    if (k == j)
        return vec[j];

    while(j != k) 
    {
        if (j > k)
            j = partion(vec, 0, j-1);
        else
            j = partion(vec, j+1, vec.size()-1);
    }

    return vec[j];
}

應(yīng)用3：最小的k個(gè)數(shù)

同樣受上題的啟發(fā)，經(jīng)過(guò)一次Partion之后，樞軸前面的數(shù)比它小，樞軸后面的數(shù)比它大。