python程式實作歸併排序的方法介紹

這篇文章主要為大家詳細介紹了python程式實現歸併排序的具體程式碼，具有一定的參考價值，有興趣的小夥伴們可以參考一下

因為上個星期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的程式碼

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 c


def 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)

以上是python程式實作歸併排序的方法介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！