前言

上一章節,博主講述了時間復雜度為O(n2)的排序演算法,今天博主要介紹的主要是四個 堆排序,快排,歸并排序和希爾排序,他們的共同點是,前三者的時間復雜度為O(n*logn),后面為O(n^1.3),都是接近線性的復雜度.

堆排序

堆排序的內容博主在講解二叉樹部分時候就已經詳細闡述了

所以,為了方便,這里就直接放鏈接了堆排序

快速排序

在講解快速排序之前,我們先做一個荷蘭國旗問題

荷蘭國旗問題:

有一無序陣列,要求把陣列劃分成三個區域,左邊區域小于某個值,中間區域等于某個值,右邊區域大于某個值

示例1

輸入:

[6,2,4,9,8,5,7,5,3,6,5,7,8,5,9];
k = 5;

輸出:

[2,4,3,5,5,5,5,7,6,8,7,8,9,9,6]

可以清晰的看到,小于5的在左邊,等于5的在中間,大于5的在右邊.

演算法實作:

• 初始化小于區域less<=-1,大于區域more>=n
• 設定當前指標cur,從索引0開始出發.
• 如果cur指向的值小于k,則cur的值和less下一個值交換,然后less++,cur++;
• 如果cur指向的值等于k,啥都不管,cur++;
• 如果cur指向的值大于k,則cur的值和more前一個值交換,然后more++,cur不變,為什么不變?因為和more區域前一個交換后,cur指向的值仍可能大于k.;

圖解:

所以代碼為:

int less = -1,more = n,cur = 0,k = 5;
while(cur<more)
{
    if(num[cur] < k) swap(&num[cur++],&num[++less]); //如果小于k,就和less下一個位置交換,然后less加加,cur加加
    else if(num[cur] > k) swap(&num[cur],&num[--more]);//如果大于k,就和more前一個位置交換,然后more減減,cur不變
    else cur++; //如果等于k,啥都不管,cur后移
}

既然荷蘭國旗問題已經解決,那么快速排序代碼怎么些呢?

我們知道荷蘭國旗問題完成一次后,左邊是小于k的,右邊是大于k的,中間等于k,那么說明中間已經有序,則不需要再管理,相反,所需要排序的部分是less區域和more區域.

所以,快速排序內容就是,先執行一次荷蘭國旗問題,然后繼續遞回排序less區域和more區域,只是k值是我們選擇

其中,如果陣列元素只剩下一個,則說明不需要排序

void QuickSort(int num[],int l,int r)  //l是陣列左邊區域,r是陣列右邊區域
{
    if(l>=r) return ;
    
    int less = l-1,more = r+1,cur = l,k = num[(l+r)>>1]; //選中間的為k值 (l+r)>>1等價于(l+r)/2
 
    while(cur<more)
    {
        if(num[cur] < k) swap(&num[cur++],&num[++less]); //如果小于k,就和less下一個位置交換,然后less加加,cur加加
        else if(num[cur] > k) swap(&num[cur],&num[--more]);//如果大于k,就和more前一個位置交換,然后more減減,cur不變
        else cur++; //如果等于k,啥都不管,cur后移
    }
    
    QuickSort(num,l,less);  //對l到less區域再進行荷蘭國旗問題
    QuickSort(num,more,r);  //對more到r區域再進行荷蘭國旗問題
}

測驗:

歸并排序

歸并排序的思想是,把陣列分成兩份,對左邊排序,然后對右邊排序,然后比較已排序左右兩邊的數,按照大小依次放到臨時陣列里面,然后放回原陣列.

下面是歸并動圖(即對已有順序陣列,比較左右兩邊大小,放入臨時陣列,然后回傳原陣列),其步驟是:

• 對于左邊部分用一個指標從頭開始指向(l)
• 對于右邊部分用一個指標從頭開始指向?
• 如果左邊arr[l]小于等于右邊arr[r],把左邊arr[l]放入臨時陣列,然后l++
• 如果左邊arr[l]大于右邊arr[r],把右邊arr[r]放入臨時陣列,然后r++
• 如果l或者r走到邊界,就停止,然后依次檢查哪部分還有剩余的元素,全部放進臨時陣列

上面動圖的前提是左右部分有序,那怎么讓左右部分有序呢?

如果只有兩個資料,左邊一個,右邊一個,可不可以認為左右兩邊分別有序?

然后我們按照上圖思路歸并兩個元素,對于整個陣列來說,我們先拆分,然后歸并,那么整體就變成有序,如下圖

代碼該怎樣寫呢?我們從簡到繁,先寫歸并代碼,按照歸并步驟,代碼如下:

int tmp[1000] = {0}
int i,j,k,mid;
mid  = (l+r)>>1;
//由于原陣列是先被劃分兩半,然后再歸并的,所以mid是左右陣列分界線,即mid是原陣列的中點
for(i = l,j = mid + 1,k = 0;i<=mid && j<=r;k++)   //無論是左邊還是右邊,一方走到邊界,就停止
{
    if(num[i]<=num[j]) tmp[k] = num[i++]; //左邊小于右邊,把num[i]放進tmp陣列,然后i++
    else tmp[k] = num[j++];               //左邊大于右邊,把num[j]放進tmp陣列,然后j++
}

while(i<=mid) tmp[k++] = num[i++];  //如果右邊先到邊界,左邊還有剩余,則依次全部放進tmp陣列

while(j<=r) tmp[k++] = num[j++];  //如果左邊先到邊界,右邊還有剩余,則依次全部放進tmp陣列

for(i = 0,j = l;i<k;i++,j++) num[j] = tmp[i];      //把臨時陣列的值放回原陣列

歸并代碼我們已經寫出來了,那么歸并排序呢?其實博主上面就已經說了,歸并排序其實不存在排序這一說法,其之所以會有序,是因為我們在遞回劃分陣列時候,最終一定會劃分為左邊和右邊都只有一個數的情況,這時候歸并就開始發揮作用,等此層遞回結束,就會回傳到上層遞回,上層就不是左右只有一個數了,而是左右有兩個數,但是在之前左右兩個數由于歸并已經有序,所以再次歸并,周而復始…最后有序,就如上圖,所以我們可以得出結論:歸并排序并未排序,核心只是不斷向下劃磁區域,到達底線后,不斷向上歸并,最終有序.

遞回劃分代碼:

void MergeSort(int num[],int l,int r)
{
    if(l>=r) return ;             //如果只剩下一個元素,停止遞回劃分,回傳上一層遞回
    
    int mid = (l+r)>>1;           //先對原陣列左右劃分成兩份
    MergeSort(num,l,mid);         //對劃分后的左陣列(l到mid區域),在進行同樣劃分
    MergeSort(num,mid+1,r);       //對劃分后的右陣列(mid+1到r區域),在進行同樣劃分
    
    //大家看遞回的時候,一定要弄清楚遞回定義,比如MergeSort,就是劃磁區域,逐漸回傳的時候形成有序.
    //所以上面對左右兩邊劃磁區域后,左右已經有序.下面我們就進行歸并
    int i = 0,j = 0,k = 0;    
    int tmp[1000] = {0};
    for(i = l,j = mid + 1,k = 0;i<=mid && j<=r;k++)   //無論是左邊還是右邊,一方走到邊界,就停止
    {
        if(num[i]<=num[j]) tmp[k] = num[i++]; //左邊小于右邊,把num[i]放進tmp陣列,然后i++
        else tmp[k] = num[j++];               //左邊大于右邊,把num[j]放進tmp陣列,然后j++
    }
    while(i<=mid) tmp[k++] = num[i++];  //如果右邊先到邊界,左邊還有剩余,則依次全部放進tmp陣列
    while(j<=r) tmp[k++] = num[j++];  //如果左邊先到邊界,右邊還有剩余,則依次全部放進tmp陣列
    for(i = 0,j = l;i<k;i++,j++) num[j] = tmp[i];      //把臨時陣列的值放回原陣列
}

測驗:

希爾排序

希爾排序是進階版本的插入排序,我們先回顧下插入排序適合哪種資料進行排序?答案是資料部分有序,而希爾排序的程序是,在插入排序之前進行一部分調整,讓資料盡可能的達到部分有序.

那么是怎么讓資料部分有序的呢?這就是一個牛逼的人–希爾想出來的.他把資料間隔成多塊,舉例為gap,然后按照gap距離進行插入排序.

比如有資料[9,8,7,6,5,4,3,2,1,5,4,3],我們用3個資料距離進行劃分,然后依次插入排序,如下圖:

• 對于藍線來說,其上的資料有9 6 3 5,這4個資料進行排序后為3 5 6 9,原資料變成[3 8 7 5 5 4 6 2 1 9 4 3]
• 對于橙線來說,其上的資料有8 5 2 4,這4個資料進行排序后為2 4 5 8,原資料變成[3 2 7 5 4 4 6 5 1 9 8 3]
• 對于黑線來說,其上的資料有7 4 1 3,這4個資料進行排序后為1 3 4 7,原資料變成[3 2 1 5 4 3 6 5 4 9 8 7]

可以看見,資料已經部分有序 3 2 1 5 4 3 6 5 4 9 8 7

而倘若我們繼續把gap變成2,然后仍然進行相關操作,最后gap變成1,也就是真的插入排序,這些整個操作合在一起就是希爾排序

寫任何一段代碼,我們都應該遵循從簡到繁,所以希爾排序的內容比較簡單的步驟是什么呢? 沒錯,就是相隔gap距離的資料進行排序

按照上面的步驟我們是先讓**整個藍線有序,然后橙線,最后黑線,**但是這樣寫代碼將會是一個及其耗費時間和精力的作業,其實我們可以更換一個簡單的思路,最后也可以進行達到上述效果,那思路是什么呢?

我們直接挨著陣列進行遍歷,然后交換gap距離的數,什么意思呢?

• 我們直接從藍線的第二個資料(索引為gap)開始,也就是6,然后6和藍線上的第一個資料交換,變成6 9
• 緊接著我們從橙線的第二個資料(索引為gap+1)開始,也就是5,然后5和橙線的第一個資料交換,變成 5 8
• 緊接著我們從黑線的第二個資料(索引為gap+2)開始,也就是4,然后4和黑線的第一個資料交換,變成4 7
• 然后又從藍線的第三個資料開始,也就是3,然后3和藍線的前兩個資料排序,變成3 6 9…
• 然后又從橙線的第三個資料開始,也就是2,然后2和橙線的前兩個資料排序,變成2 5 8…
• 然后又從黑線的第三個資料開始,也就是2,然后1和黑線的前兩個資料排序,變成1 4 7…

也就是我們直接從索引gap處開始,然后向后遍歷,在遍歷的程序中,進行相隔距離gap的資料排序,而這個程序所操作的一直在回圈藍線橙線黑線,又藍線橙線黑線...進而達到了先整體藍線,整體橙線,整體黑線的效果.

同理,寫代碼怎么寫呢?我們還是從簡到繁,先給gap賦一個值,以3為例.

int gap = 3;
for(int i = gap;i<n;i++)
{
    int min_index = i;
    int target = num[i];
    for(int j = i;j>=0;j-=gap)    //插入是按照gap距離來算的,所以j-=gap
    {
        if(num[j] < num[j-gap]) num[j] = num[j-gap],min_index = j-gap; //這里和插入排序一樣,只是插入排序減去的是1
    }
	num[min_index] = target;      //插入到正確位置.
}

既然最簡單的步驟寫完以后,那么我們開始進行完整的希爾排序代碼了,既然說希爾是進階版本的插入排序,那么希爾的核心在哪里呢?沒錯,核心就是gap的取值,因為我們要保證預處理一部分值以后,最后進行真正的插入排序,即gap等于1,那么gap的值該怎樣取呢?這就感謝我們的前輩們辛苦努力了,他們經過大量實驗得出gap取值最好用 gap = gap/3+1

所以完整的希爾代碼如下:

void ShellSort(int num[],int n)
{
    int  gap = n;
    while(gap>1)
    {
        gap = gap/3 + 1;
        for(int i = gap;i<n;i++)
        {
            int min_index = i;
            int target = num[i];
            for(int j = i;j>=gap;j-=gap)    //插入是按照gap距離來算的,所以j-=gap,之所以j>=gap因為j-gap不可越界
            {
                if(target < num[j-gap]) 
                    num[j] = num[j-gap],min_index = j-gap; //這里和插入排序一樣,只是插入排序減去的是1
            }
            num[min_index] = target;      //插入到正確位置.
        }
    }
}

測驗: