《C++從入門到入土》——歸 並 排 序


C++說要有順序,於是便誕生了眾多的排序演算法。

眾多排序演算法中有一個玄學演算法——歸併排序。

歸併排序有兩個步驟——先分而治之。歸併演算法的核心是分治,顧名思義,分,就是把問題簡化,分割成一個個容易計算的小問題;治,則是把求得子問題的所有答案彙總成整個問題的最終答案(為毛讓我想起了動歸?)。

首先,我們需要通過遞迴和二分的方法,將需要排序的原陣列分割成多個臨時陣列。每個臨時陣列都是(在該次遞迴中的)原陣列的一半長度,直至分割成無法再次分割的最小單位(在歸併排序中就是陣列中只有一個數,n=1), 這部分的時間複雜度是log2n;

接著是“並”,也通過遞迴來實現,將每兩個已有序的臨時陣列 合併成一個有序的臨時陣列(對於每個臨時陣列的區間來說都是有序的),將這部分有序的數還原到原陣列中,最終將所有子陣列合併成有序的原陣列,這部分的時間複雜度是n(每個數掃一遍)。

最終的時間複雜度就是n*log2n。

詳細的見程式碼描述。

延伸閱讀  C語言裡面的typedef為什麼反彙編之後找不到相關的編碼呢?

有疑問評論區歡迎留言。


練習完的可以去洛谷P1177快速排序 提交(https://www.luogu.com.cn/problem/P1177),所有的排序題目都可以在上面提交。

如果覺得太簡單的可以嘗試洛谷P1908逆序對(https://www.luogu.com.cn/problem/P1908),雖然不是排序,但需要用到歸併排序的思想(分治yyds)。

最後,老師的任務已經完成了,祝願我原神胡桃二十抽直接出金!

QwQ Orz QaQ

延伸閱讀  PS又 叒更新了,看完我再也不相信自己的眼睛了……
Scroll to Top