常見排序之近線性排序

捕獲一只小肚皮 2021-09-19 23:10:51 阅读数:635

排序 排序

前言

上一章節,博主講述了時間複雜度為O(n²)的排序算法,今天博主要介紹的主要是四個 堆排序,快排,歸並排序和希爾排序,他們的共同點是,前三者的時間複雜度為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區域再進行荷蘭國旗問題
}

測試:

image-20210919165440218

歸並排序

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

下面是歸並動圖(即對已有順序數組,比較左右兩邊大小,放入臨時數組,然後返回原數組),其步驟是:

  • 對於左邊部分用一個指針從頭開始指向(l)
  • 對於右邊部分用一個指針從頭開始指向
  • 如果左邊arr[l]小於等於右邊arr[r],把左邊arr[l]放入臨時數組,然後l++
  • 如果左邊arr[l]大於右邊arr[r],把右邊arr[r]放入臨時數組,然後r++
  • 如果l或者r走到邊界,就停止,然後依次檢查哪部分還有剩餘的元素,全部放進臨時數組
歸並

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

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

然後我們按照上圖思路歸並兩個元素,對於整個數組來說,我們先拆分,然後歸並,那麼整體就變成有序,如下圖

img

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

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]; //把臨時數組的值放回原數組
}

測試:

image-20210919165706648

希爾排序

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

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

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

image-20210919174604226

  • 對於藍線來說,其上的數據有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; //插入到正確比特置.
}
}
}

測試:

image-20210919210210765

版权声明:本文为[捕獲一只小肚皮]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210919231051342M.html