八十、歸并排序及其分而治之思想

「@Author：Runsen」

?

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

分治算法

分治法是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題 直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。（百度百科）

利用分治策略求解時(shí)，所需時(shí)間取決于分解后子問題的個(gè)數(shù)、子問題的規(guī)模大小等因素，而二分法，由于其劃分的簡單和均勻的特點(diǎn)，是經(jīng)常采用的一種有效的方法，例如二分法檢索。

分治算法的基本思想：是將一個(gè)規(guī)模為N的問題分解為K個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。即一種分目標(biāo)完成程序算法，簡單問題可用二分法完成。

分治法所能解決的問題一般具有以下幾個(gè)特征：

原問題于分解成的小問題具有相同的模式，原問題分解成的小問題可以獨(dú)立求解，子問題之間沒有相關(guān)性。

具有分解終止條件，當(dāng)問題足夠小時(shí)，可以之間求解，分解出的子問題的解可以合并為該問題的解

基本步驟

• 分解，將要解決的問題劃分成若干規(guī)模較小的同類問題；
• 求解，當(dāng)子問題劃分得足夠小時(shí)，用較簡單的方法解決；
• 合并，按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。

具體偽代碼如下：

if?(問題不可分):
????返回解
else:
????從原問題中劃出含一半運(yùn)算對象的子問題1；
????遞歸調(diào)用分治法過程，求出解1；
????從原問題中劃出含另一半運(yùn)算對象的子問題2；???
????遞歸調(diào)用分治法過程，求出解2；
????將解1、解2組合成整個(gè)問題的解；??

歸并排序

分治算法問題求解，一個(gè)是二分搜索，一個(gè)就是歸并排序。

歸并排序其實(shí)要做兩件事：

「拆分」：核心問題是確定拆分位置即可，我們利用左右元素索引之和除2即可，也就是：mid = (left + right)/2，指導(dǎo)拆分到子序列僅僅存在一個(gè)元素的基本情形。

「合并」：merge 是歸并排序的核心，將兩個(gè)已排序子序列合并為一個(gè)排序序列的過程。當(dāng)子序列中僅存在一個(gè)元素時(shí)，可視為子序列已經(jīng)排序，因此我們的合并是從兩個(gè)單一元素子序列開始的。

當(dāng)子序列存在多個(gè)元素時(shí)，我們需要逐個(gè)得到當(dāng)前最小元素，進(jìn)而完成整體排序，過程中我們需要一個(gè)臨時(shí)區(qū)來存儲已排序的部分。

最后將兩個(gè)區(qū)間合并為一個(gè)有序的區(qū)間，你會(huì)怎么思考呢？

這個(gè)非常簡單，只要從比較二個(gè)數(shù)列的第一個(gè)數(shù)，誰小就先取誰，取了后就在對應(yīng)數(shù)列中刪除這個(gè)數(shù)。然后再進(jìn)行比較，如果有數(shù)列為空，那直接將另一個(gè)數(shù)列的數(shù)據(jù)依次取出即可。

'''
@Author：Runsen
@WeChat：RunsenLiu
@微信公眾號：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/12/21
'''
def?merge(left,?right):??#?合并兩個(gè)有序數(shù)組
????l,?r?=?0,?0
????result?=?[]
????while?l?and?r?????????if?left[l]?<=?right[r]:
????????????result.append(left[l])
????????????l?+=?1
????????else:
????????????result.append(right[r])
????????????r?+=?1
????result?+=?left[l:]
????result?+=?right[r:]
????return?result


def?merge_sort(nums):
????if?len(nums)?<=?1:
????????return?nums
????num?=?len(nums)?>>?1??#位運(yùn)算取中間
????left?=?merge_sort(nums[:num])
????right?=?merge_sort(nums[num:])
????return?merge(left,?right)
????
????
if?__name__?==?'__main__':
????nums?=?[54,?26,?93,?17,?77,?31,?44,?55,?20]
????print(merge_sort(nums))????

[17,?20,?26,?31,?44,?54,?55,?77,?93]

歸并排序的運(yùn)行時(shí)間最差、最好和平均都是 O(NlogN)，但是歸并排序并沒有像快排那樣，應(yīng)用廣泛，這是為什么呢？因?yàn)樗幸粋€(gè)致命的“弱點(diǎn)”，那就是歸并排序不是原地排序算法。它需要額外的存儲空間，空間復(fù)雜度為 O(N)。

「這世上沒有天才，你若對得起時(shí)間，時(shí)間便對得起你。關(guān)注我們，每天進(jìn)步一點(diǎn)點(diǎn)，利用碎片化時(shí)間學(xué)習(xí)。」

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。

?

Reference