使用python如何實現(xiàn)一個歸并排序-創(chuàng)新互聯(lián)

今天就跟大家聊聊有關(guān)使用python如何實現(xiàn)一個歸并排序，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

目前成都創(chuàng)新互聯(lián)公司已為上1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬空間、網(wǎng)站托管、服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計、岳西網(wǎng)站維護等服務(wù)，公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

1、歸并排序算法是什么？

冒泡排序(Bubble Sort)是一種建立在歸并操作上面的一種有效的排序算法，由John von neumann于1945年發(fā)明。采用分治法（Divide and Conquer）的經(jīng)典應(yīng)用??！將規(guī)模較大的排序問題化歸到較小的規(guī)模上解決。

基本實現(xiàn)包含下面的兩種方法：

自上而下的遞歸
自下而上的迭代

將已經(jīng)有的有序子序列合并，得到完全有序的子序列。就是先得到每個子序列有序，然后在使得兩個子序列合并成為一個有序的。如果是把兩個有序表合并成為一個有序表，成為二路歸并。

歸并排序的性能不受到輸入數(shù)據(jù)的影響，這一個和選擇排序是一樣的，但是性能比選擇排序要好，性能始終是O(n log n）。但是性能的優(yōu)越必定是額外的內(nèi)存空間作為巨大代價的！

2、算法過程圖解

3、代碼實現(xiàn)

代碼如下（示例01）：

"""
Merge_Sort 歸并排序
分治算法Divide and Conquer
時間復(fù)雜度：
"""

# 切割數(shù)組 的函數(shù)
def merge_sort(alist):
 # 如果長度小于等于1 ，不能再分割了
 if len(alist) <= 1:
  return alist

 # 根據(jù)列表長度確定拆分的中間位置
 mid_index = len(alist)//2

 # 使用切片實現(xiàn)對列表的切分
 # left_list = alist[:mid_index]
 # right_list = alist[mid_index:]

 # 遞歸調(diào)用，無限切割下去
 left_list = merge_sort(alist[:mid_index])
 right_list = merge_sort(alist[mid_index:])
 return merge(left_list, right_list)

# 排序的函數(shù)
def merge(left_list, right_list):
 l_index,r_index = 0,0
 merge_list = []
 # 判斷列表里面是否還有元素可以用
 while l_index < len(left_list) and r_index < len(right_list):
  # 哪邊的元素小于另外一邊的的元素就把哪邊的元素加入進去，對應(yīng)的索引加一
  if left_list[l_index] < right_list[r_index]:
   merge_list.append(left_list[l_index])
   l_index += 1
  else:
   merge_list.append(right_list[r_index])
   r_index += 1
 # 下面的這兩個就是，如果有一個列表全部添加了，另外一個列表直接添加到merge_list里面了
 merge_list += left_list[l_index:]
 merge_list += right_list[r_index:]
 return merge_list

if __name__ == '__main__':
 alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
 print(f'原列表的順序：{alist}')
 alist = merge_sort(alist)
 print(f'選擇排序之后的列表的順序：{alist}')

分享文章：使用python如何實現(xiàn)一個歸并排序-創(chuàng)新互聯(lián)
文章位置：http://muchs.cn/article14/ddccde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、靜態(tài)網(wǎng)站、網(wǎng)站營銷、定制網(wǎng)站、手機網(wǎng)站建設(shè)、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)