1. 基本原理

歸并排序建立在歸并操作上的一種算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。歸并排序是將兩

個已經有序的序列合成一個有序的序列的過程。

因此，對于一個待排序的序列來說，首先要將其進行分割，得到有序的子序列，再進行歸并操作，最終得到有序的序列。

歸并的基本思想

假設有兩個有序的序列，需要合成一個序列。其實就是不斷的比較兩個序列開頭的元素大小就可以。

if a[0] > b[0]

將a[0]存入另一個設置好的空序列C中

else

將b[0]存入另一個設置好的空序列C中

if length（a）==0 或者length（b）==0

上述操作結束

總體的思想就是不斷的比較兩個序列的第一個元素并存入第三個序列中，再釋放原序列中的第一個元素。

分割的基本思想

分割就是將原序列不斷的進行分割，以便得到有序的子序列，進行歸并操作。整理介紹二分割。就是在序列的中間進行分割。

顯然，對于比較長的序列需要進行多次的分割操作，使得每個子序列的元素個數只有一個。只有這樣，才能得到有序的子序列，進

行歸并操作。

這樣話就需要對原序列進行一個遞歸的分割操作。得到最終的我們需要的子序列。

一個例子

這里有一個隨機生成的包含了10個元素的待排序的序列

[92,79,37,39,98,62,64,33,9,5]

按照上述的基本思想，其分割和歸并的流程為：

從上面可以很清楚的看到，首先需要進行分割，然后對分割的子序列進行一個歸并操作，最終得到排序完成
的新序列。

2. Python實現

歸并操作實現

def mergeTwoArray(a,b):m=a.__len__()n=b.__len__()c=[]while m>0 and n>0:if a[0]<b[0]:c.append(a[0])a.pop(0)m=a.__len__()#k+=1else:c.append(b[0])b.pop(0)n=b.__len__()while m>0 and n==0:c.append(a[0])a.pop(0)m=a.__len__()while n>0 and m==0:c.append(b[0])b.pop(0)n=b.__len__()return c

歸并排序實現

def myMergeSort(a):if a.__len__()<=1:return amiddleIndex=a.__len__()//2leftArray=myMergeSort(a[:middleIndex])#左邊有序#print('左邊序列有序的過程：')print(leftArray)#print()rightArray=myMergeSort(a[middleIndex:])#右邊有序#print('右邊序列有序的過程：')print(rightArray)return mergeTwoArray(leftArray,rightArray)#再合并兩個有序的小數組，實現歸并的思想

輸出結果

3. 時間復雜度分析

并排序的效率是比較高的，設數列長為N，將數列分開成小數列一共要log2N步，每步都是一個合并有序數列的過程，時間復雜

度可以記為O(N)，故一共為O(Nlog2N)。因為歸并排序每次都是在相鄰的數據中進行操作，所以歸并排序在O(N?log2N)

的幾種排序方法（快速排序，歸并排序，希爾排序，堆排序）也是效率比較高的。

總結

以上是生活随笔為你收集整理的排序算法四：归并排序基本原理以及Python实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。