python排序算法之歸并排序怎么實現

這篇文章主要介紹“python排序算法之歸并排序怎么實現”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“python排序算法之歸并排序怎么實現”文章能幫助大家解決問題。

算法描述

本節中的第一種高級排序算法是歸并排序。“歸并”一詞，意為“合并”。顧名思義，歸并排序算法就是一個先把數列拆分為子數列，對子數列進行排序后，再把有序的子數列合并為完整的有序數列的算法。它實際上采用了分治的思想。

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

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

原始數組是一個有8個數的無序數組。一次操作后，把8個數的數組分成兩個4個數組成的無序數組。接下來的每次操作都是把無序數組不停分成兩半，直到每個最小的數組里都只有一個元素為止。當數組里只有一個元素時，這個數組必定是有序的。然后，程序開始把小的有序數組每兩個合并成為大的有序數組。先是從兩個1個數的數組合并成2個數的數組，再到4個數然后8個數。這時，所有的有序數組全部合并完成，最后產生的最長的有序數組就排序完成了。

代碼實現

歸并排序代碼：

  #歸并排序
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時，每一個數獨立存在于一個數組中，因此數組已經被分到最小。這時候，遞歸分解數組的任務已經完成，只需要把分解后的數組返回到上一層遞歸就可以了。

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

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

關于“python排序算法之歸并排序怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。