歸并排序
歸并排序是采用分治法的一個非常典型的應用。歸并排序的思想就是先遞歸分解數組，再合并數組
将數組分解到最小之後，合并兩個有序的數組，基本思路就是比較兩個數組最前面的數字，誰小就先取誰，取了後相應的指針就往後移動一位。然後再比較，知道一個數組為空，最後把一個數組的剩餘部分複制過來即可
文章目錄
- 歸并排序
-
-
-
- 基本實作
-
- 這個就是歸并算法的思想：把一組元素一直拆分到隻有一個子元素，之後開始合并，通過Left與Right進行排序。
- 歸并算法代碼實作
- 時間複雜度
-
-
基本實作
1.有一串數組如下，将其對半分成兩個數組。
2.左右繼續拆分到每一個子部分隻有一個元素，如下，拆分到隻有一個子元素的之後拆分結束
3，拆分完之後進行合并，56跟26是上面綠色框拆出來的，合并的時候采用小的在前，大的在後。
4.把兩個綠色塊進行合并，這個時候就要借助定義的遊标了，一個指的是左邊大部分Left ，一個是右邊的Right.合并的時候采用的方式是，對于左邊的部分有一個遊标，右邊的部分也有一個遊标，然後對于所指的兩個部分進行比較換位。
5.經過比較17比較小，拿出來，之後Right向後移動一位。
6.之後繼續比較Right的指向比26大，取出26，Left繼續向後移動一位。之後比較發現Right指向比Left大，取出54，最後把Right放到後面，得到下面的一個有序數列。
7.右邊繼續采用相同的方式，的得到兩個部分，之後現在對于整個序列來說就隻有兩個部分了。
8.按照上面相同的方式對兩個綠色框的資料進行合并。依舊是左邊的遊标Left，右邊的右邊Right對比。得到了一個有序的數列
這個就是歸并算法的思想：把一組元素一直拆分到隻有一個子元素，之後開始合并，通過Left與Right進行排序。
那麼對于奇數個也是一樣的，隻不過拆分的時候最後的的一組多出來一個。合并的時候也是，先把最後那個灰色框那兩個合并到一起，再跟44合并成3個，怎麼拆的就怎麼合并。
歸并算法代碼實作
'''
Create by YO
@Time: 2020/4/22
'''
#相除的時候兩個斜杠無小數部分。向下取整
def merge_sort(alist):
'''歸并排序'''
n=len(alist)
if n<=1:
return alist
mid=n//2 #中間值
left_li=merge_sort(alist[:mid])
#right 采用歸并排序後形成的新的清單
right_li=merge_sort(alist[mid:])
#将兩個有序的子序列合并成一個新的整體 merge(left,right) 左邊的指針跟右邊的指針都指向兩個子序列的第一個元素
left_pointer,right_pointer=0,0
result=[]
while left_pointer<len(left_li) and right_pointer<len(right_li):
if left_li[left_pointer]<right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer+=1 #移動完向後一位移動
else:
result.append(right_li[right_pointer])
right_pointer+=1
result+=left_li[left_pointer:]
result+=right_li[right_pointer:]
return result
if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
sorted_li=merge_sort(li)
print(li)
print(sorted_li)
輸出：
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93] 複制
時間複雜度
最優時間複雜度：O(nlogn)
最壞時間複雜度：O(nlogn)
穩定性：穩定