Python實(shí)現(xiàn)歸并排序算法

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

分治法的基本思想

將原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。遞歸地解這些子問(wèn)題，然后將這些子問(wèn)題的解組合為原問(wèn)題的解。

歸并排序的基本思想

排序一個(gè)數(shù)組，我們先把數(shù)組從中間分成前后兩部分，然后對(duì)前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了。

動(dòng)畫

（請(qǐng)?jiān)诎l(fā)表文章時(shí)插入 ms.webp 這張圖片）

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

```python

def merge(left, right):

'''合并和排序'''

i = 0

j = 0

result = []

length_left = len(left)

length_right = len(right)

while i < length_left and j < length_right:

# 逐個(gè)比較兩個(gè)列表的元素

# 小的添加進(jìn)新列表，大的留下繼續(xù)比較

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

result.append(left[i])

i += 1

else :

result.append(right[j])

j += 1

# 最后加上未比較的元素

result.extend(left[i:])

result.extend(right[j:])

return result

def merge_sort(lists):

'''歸并排序入口，拆分列表'''

# 遞歸退出條件判斷

length = len(lists)

if length <= 1 :

return lists

# 遞歸拆分，取整，兼容py3

mid = length // 2

left = merge_sort(lists[:mid])

right = merge_sort(lists[mid:])

# 合并排序（歸并排序）

return merge(left, right)

numbers = [ 4 , 0 , 7 , 9 , 2 , 8 , 1 , 3 , 6 , 5 ]

assert merge_sort(numbers) == [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]

```