快捷導航

python排序算法之歸并排序

更新時間：2023年04月23日 09:58:30 作者：i阿極

這篇文章主要介紹了python排序算法之歸并排序,歸并排序算法就是一個先把數(shù)列拆分為子數(shù)列，對子數(shù)列進行排序后，再把有序的子數(shù)列合并為完整的有序數(shù)列的算法,需要的朋友可以參考下

一、前言

相關(guān)知識來自《python算法設(shè)計與分析》。初級排序算法是指幾種較為基礎(chǔ)且容易理解的排序算法。初級排序算法包括插入排序、選擇排序和冒泡排序3種。相比起初級排序算法，高級排序算法往往有更加復雜的邏輯，但也會有更高的時間或空間效率。其中有些高級排序算法是由一些初級排序算法優(yōu)化而來的。

二、算法描述

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

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

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

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

在這里插入圖片描述

三、代碼實現(xiàn)

歸并排序代碼：

  #歸并排序
nums = [5,3,6,4,1,2,8,7]
def MergeSort(num):
  if(len(num)<=1):　　　　　　　　#遞歸邊界條件
   return num　　　　　　　　　#到達邊界時返回當前的子數(shù)組
  mid = int(len(num)/2)　　　　　 #求出數(shù)組的中位數(shù)
  llist,rlist = MergeSort(num[:mid]),MergeSort(num[mid:])#調(diào)用函數(shù)分別為左右數(shù)組排序
  result = []
  i,j = 0,0
  while i < len(llist) and j < len(rlist): #while循環(huán)用于合并兩個有序數(shù)組
   if rlist[j]<llist[i]:
     result.append(rlist[j])
     j += 1
   else:
     result.append(llist[i])
     i += 1
  result += llist[i:]+rlist[j:]　 #把數(shù)組未添加的部分加到結(jié)果數(shù)組末尾
  return result　　　　　　　　　#返回已排序的數(shù)組
print(MergeSort(nums))

運行程序，輸出結(jié)果為：

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

在MergeSort()函數(shù)中，首先進行的是邊界條件判斷。當傳入函數(shù)的數(shù)組長度只有1時，每一個數(shù)獨立存在于一個數(shù)組中，因此數(shù)組已經(jīng)被分到最小。這時候，遞歸分解數(shù)組的任務(wù)已經(jīng)完成，只需要把分解后的數(shù)組返回到上一層遞歸就可以了。

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

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