python排序演算法之歸併排序怎麼實現

演算法描述

本節中的第一種高階排序演算法是歸併排序。 「歸併」一詞，意為「合併」。顧名思義，歸併排序演算法就是一個先把數列拆分為子數列，對子數列進行排序後，再把有序的子數列合併為完整的有序數列的演算法。它實際上採用了分治的思想。

歸併排序的平均時間複雜度是O(nlgn)，最好情況下的時間複雜度是O(nlgn)，最糟情況下的時間複雜度也是O(nlgn)。它的空間複雜度是O(1)。另外，歸併排序還是一個穩定的排序演算法。

以升序排序為例，歸併演算法的流程如圖2-21所示。

原始數組是一個有8個數字的無序數組。一次操作後，把8個數的陣列分成兩個4個數字組成的無序數組。每個操作都將無序數組分成兩半，直到所有最小的子數組僅包含一個元素。當數組裡只有一個元素時，這個數組必定是有順序的。然後，程式開始把小有序的數組每兩個合併成為一個大的有序數組。首先是將兩個包含一個數的數組合併成一個包含兩個數的數組，然後再把兩個包含兩個數的數字組合併成一個包含四個數的數組，最後合併成一個包含八個數的數組。當所有有序數組合併完畢時，形成的最長有序數組就完成排序。

程式碼實作

歸併排序程式碼：

  #归并排序
nums = [5,3,6,4,1,2,8,7]
def MergeSort(num):
  if(len(num)<=1):　　　　　　　　#递归边界条件
   return num　　　　　　　　　#到达边界时返回当前的子数组
  mid = int(len(num)/2)　　　　　 #求出数组的中位数
  llist,rlist = MergeSort(num[:mid]),MergeSort(num[mid:])#调用函数分别为左右数组排序
  result = []
  i,j = 0,0
  while i < len(llist) and j < len(rlist): #while循环用于合并两个有序数组
   if rlist[j]<llist[i]:
     result.append(rlist[j])
     j += 1
   else:
     result.append(llist[i])
     i += 1
  result += llist[i:]+rlist[j:]　 #把数组未添加的部分加到结果数组末尾
  return result　　　　　　　　　#返回已排序的数组
print(MergeSort(nums))

執行程序，輸出結果為：

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

在MergeSort ()函數中，首先進行的是邊界條件判斷。當一個只包含一個元素的陣列作為函數參數時，該元素單獨存在於數組中，因此該數組已經達到了最小大小。完成遞歸分解數組的任務後，只需將分解的陣列返回到上一層遞歸即可。

如果未排序數組的長度仍然大於1，那麼使用變數mid來儲存數組最中間的下標，把未排序數組分成左右兩個子數組。然後，新建兩個數組，用來儲存排好序的左右子數組。這裡使用了遞歸的思想。我們只把MergeSort()函數視為一個為列表排序的函數，儘管在MergeSort()函數內部，也可以呼叫函數本身對兩個子數組進行排序。

隨後，使用while循環合併兩個已經有順序的陣列。由於無法確定兩個數組中元素的相對大小，所以我們採用i和j兩個變數分別標記在左子數組和右子數組中等待加入的元素的位置。當while循環結束時，可能一個子數組的末尾還剩餘一些最大的元素沒有被添加到result列表中，所以result =llist[i:] rlist[j:]語句是為了防止漏掉這些元素。數字組合併完成後，函數輸出有序數組。

以上是python排序演算法之歸併排序怎麼實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！