使用 Python 解釋歸併排序

歸併排序是一種排序技術。它是一種有效的排序演算法，其時間複雜度為 (n logn)，其中 n 為要排序的陣列長度。

歸併排序是一種遵循分而治之正規化的演算法。它不斷地將陣列分成兩半。然後，它開始對每個元素都為一個元素的列表進行排序，並不斷合併已排序的列表以形成完整排序的列表。

因此，我們得到一個排序好的陣列。

示例

紫色方框和黑色箭頭顯示了將列表分成兩半的方式。

綠色方框和紅色箭頭顯示了兩個已排序列表的合併方式。

實現歸併排序

將列表分成兩半非常容易，並且我們會遞迴地執行這項操作，直到只剩下一個元素。然後進行合併過程，我們實際上是在該過程中應用將兩個已排序列表合併在一起的邏輯。

示例

merge 函式將兩個要合併的已排序陣列收錄進去。將 a1 中的最前面元素與 a2 中的最前面元素進行比較。兩個元素中較小的一個新增到列表 c 中，並且會增加該陣列的指標。

 動態演示

def merge(a1,a2):
   c=[]
   x=0
   y=0
   while(x<len(a1) and y<len(a2)):
      if(a1[x]<a2[y]):
         c.append(a1[x])
         x+=1
      else:
         c.append(a2[y])
         y+=1
   while(x<len(a1)):
      c.append(a1[x])
      x+=1
   while(y<len(a2)):
      c.append(a2[y])
      y+=1
   return c

def mergesort(array):
   if(len(array)==1):
      return array
   mid=(len(array))//2
   a1=mergesort(array[:mid])
   a2=mergesort(array[mid:])
   return merge(a1,a2)
array=[2,3,1,5,4,6,8,10,7,9]
print(mergesort(array))

輸出

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

更新於: 2021 年 3 月 11 日

878 次觀看

開啟你的職業生涯

透過完成課程，取得認證

開始
廣告