簡(jiǎn)介：

歸并排序（英語：Merge sort，或mergesort），是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為n*log n。

1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，且各層分治遞歸可以同時(shí)進(jìn)行。

采用分治法:

• 分割：遞歸地把當(dāng)前序列平均分割成兩半。

• 集成：在保持元素順序的同時(shí)將上一步得到的子序列集成到一起（歸并）。

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

def merge(left,right):#合并兩個(gè)列表

? ? merge_arr=[]

? ? i=0

? ? j=0

? ? l=len(left)

? ? r=len(right)

#i分別作為left和right的下標(biāo),分別獲取左右子列表的長(zhǎng)度

? ? while i<l and j<r:#循環(huán)歸并左右子列表元素

? ? ? ? if left[i]<right[j]:

? ? ? ? ? ? merge_arr.append(left[i])

? ? ? ? ? ? i+=1

? ? ? ? else:

? ? ? ? ? ? merge_arr.append(right[j])

? ? ? ? ? ? j+=1

? ? merge_arr.extend(left[i:])

? ? merge_arr.extend(right[j:])

? ? #歸并左子列表剩余元素

? ? #歸并右子列表剩余元素

? ? #返回歸并好的列表

? ? # print('左數(shù)組為：{}'.format(left),'右數(shù)組為{}'.format(right),'合并數(shù)組為{}'.format(merge_arr))

? ? return merge_arr

def RealSortQuick(input_arr):#拆分+合并

? ? if len(input_arr)<=1:

? ? ? ? return input_arr

? ? else:

? ? ? ? mid=int(len(input_arr)/2)

? ? ? ? left=RealSortQuick(input_arr[0:mid])

? ? ? ? right=RealSortQuick(input_arr[mid:])

? ? ? ? #合并排好序的左右兩個(gè)子列表

? ? ? ? return merge(left,right)

myarr=[24,34,2,3,567,34,65,78,863,421,23]

RealSortQuick(myarr)

? ? ? ?

? ?