因為上個星期leetcode的一道題(Median of Two Sorted Arrays)所以想仔細了解一下歸并排序的實現。
還是先闡述一下排序思路：
首先歸并排序使用了二分法，歸根到底的思想還是分而治之。拿到一個長數組，將其不停的分為左邊和右邊兩份，然后以此遞歸分下去。然后再將她們按照兩個有序數組的樣子合并起來。這樣說起來可能很難理解，于是給出一張我畫的圖。
這里顯示了歸并排序的第一步，將數組按照middle進行遞歸拆分，最后分到最細之后再將其使用對兩個有序數組進行排序的方法對其進行排序。
兩個有序數組排序的方法則非常簡單，同時對兩個數組的第一個位置進行比大小，將小的放入一個空數組，然后被放入空數組的那個位置的指針往后 移一個，然后繼續和另外一個數組的上一個位置進行比較，以此類推。到最后任何一個數組先出棧完，就將另外i一個數組里的所有元素追加到新數組后面。
由于遞歸拆分的時間復雜度是logN 然而，進行兩個有序數組排序的方法復雜度是N該算法的時間復雜度是N*logN 所以是NlogN。
根據這波分析，我們可以看看對上圖的一個行為。
當最左邊的分到最細之后無法再劃分左右然后開始進行合并。
第一次組合完成[4, 7]的合并
第二次組合完成[4, 7, 8]的合并
第三次組合完成[3, 5]的合并
第四次組合完成[3, 5, 9]的合并
第五次組合完成[3, 4, 5, 7, 8, 9]的合并結束排序。
下面放上python的代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
def merge(a, b): c = [] h = j = 0 while j < len(a) and h < len(b): if a[j] < b[h]: c.append(a[j]) j += 1 else: c.append(b[h]) h += 1 if j == len(a): for i in b[h:]: c.append(i) else: for i in a[j:]: c.append(i) return cdef merge_sort(lists): if len(lists) <= 1: return lists middle = len(lists)/2 left = merge_sort(lists[:middle]) right = merge_sort(lists[middle:]) return merge(left, right)if __name__ == '__main__': a = [4, 7, 8, 3, 5, 9] print merge_sort(a) |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
