歸并排序
歸并排序用的是分而治之的方法。也就是把列表從中間分成兩個(gè)子列表，子列表又各自分為兩個(gè)子列表……這樣直到最后子列表中只有一個(gè)元素為止。然后再依次合并子列表。圖示如下。
排序算法分而治之
合并的過程用到的兩個(gè)子序列都是已經(jīng)排好序的。各自遍歷兩個(gè)子列表的當(dāng)前元素i和j，比較i和j，每次都選出比較小的數(shù)，分配到初始新列表的位置，注意要查看如果其中一個(gè)子序列遍歷完了，直接把另外一個(gè)子序列添加到新列表剩余位置即可。
依次填入較小的序列
偽代碼
merge_sort(nums)
if low>=high
return
middle=(low+high)//2
merge_sort(low, middle)
merge_sort(middle, high)
merge(nums, low, middle，high)
merge()
for i from low to high
tmp[i]=nums[i]
i=low
j=middle+1
k=low
while i<=middle and j<=high:
if tmp[i]<=tmp[j]:
nums[k]=tmp[i]
k++
i++
if tmp[i]>tmp[j]:
nums[k]=tmp[j]
k++
j++
while i<middle:
nums[k]=tmp[i]
k++
i++
while j<high:
nums[k]=tmp[j]
k++
j++
end
代碼如下：
def merge(a, b):
c=[]
i=j=0
while i<len(a) and j<len(b):
if a[i]<b[j]:
c.append(a[i])
i+=1
else:
c.append(b[j])
j+=1
if j==len(b):
for g in a[i:]:
c.append(g)
else:
for g in b[j:]:
c.append(g)
#最終返回的是這個(gè)合并了的列表
return c
def merge_sort(nums):
#如果最后只剩下一個(gè)元素就返回這個(gè)元素
if len(nums)<=1:
return nums
middle=len(nums)/2
left=nums[:middle]
right=nums[middle:]
left=merge_sort(left)
right=merge_sort(right)
return merge(left, right)
