快捷導(dǎo)航

python排序算法之歸并排序

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

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

一、前言

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

二、算法描述

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

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

以升序排序?yàn)槔?，歸并算法的流程如圖2-21所示。

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

在這里插入圖片描述

三、代碼實(shí)現(xiàn)

歸并排序代碼：

  #歸并排序
nums = [5,3,6,4,1,2,8,7]
def MergeSort(num):
  if(len(num)<=1):　　　　　　　　#遞歸邊界條件
   return num　　　　　　　　　#到達(dá)邊界時(shí)返回當(dāng)前的子數(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)用于合并兩個(gè)有序數(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))

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

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

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

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

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

總結(jié)

以上就是本文要講的內(nèi)容，本文介紹了歸并排序的理論知識(shí)和代碼實(shí)現(xiàn)。歸并排序的平均時(shí)間復(fù)雜度是O(nlgn)，最好情況下的時(shí)間復(fù)雜度是O(nlgn)，最壞情況下的時(shí)間復(fù)雜度也是O(nlgn)。它的空間復(fù)雜度是O(1)。另外，歸并排序還是一個(gè)穩(wěn)定的排序算法。

到此這篇關(guān)于python排序算法之歸并排序的文章就介紹到這了,更多相關(guān)python歸并排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: