[算法] 归并排序（Python）

分为3个函数实现：

sort()：主排序函数

_sort()：分治函数，将排序数组不断分解为子数组进行排序

_merge()：归并函数，将两个有序数组合并成一个大的有序数组

 1 def sort(a):
 2     n = len(a)
 3     aux = [0]*n
 4     return _sort(a,0,n,aux)
 5 
 6 def _sort(a,lo,hi,aux):
 7     n = hi - lo
 8     if n <= 1:return
 9     mid = (lo + hi) // 2
10     _sort(a,lo,mid,aux)
11     _sort(a,mid,hi,aux)
12     return _merge(a,lo,mid,hi,aux)
13     
14 def _merge(a,lo,mid,hi,aux):
15     n = hi - lo
16     i = lo
17     j = mid
18     for k in range(n):
19         if i == mid:aux[k] = a[j];j += 1
20         elif j == hi:aux[k] = a[i];i += 1
21         elif a[j]<a[i]:aux[k] = a[j];j += 1
22         else:aux[k] = a[i];i += 1
23     a[lo:hi]=aux[0:n]
24     return a
25 
26 >>x = [1,3,2,5,4]
27 >>print(sort(x))

注意：每次_sort()都是对左闭右开区间进行排序

另一种写法：

 1 import random, time
 2 
 3 def merge_sort(lst):
 4     if len(lst) <= 1:
 5         return lst          # 从递归中返回长度为1的序列
 6 
 7     middle = len(lst) / 2
 8     left = merge_sort(lst[:middle])     # 通过不断递归，将原始序列拆分成n个小序列
 9     right = merge_sort(lst[middle:])
10     return merge(left, right)
11 
12 def merge(left, right):
13     i, j = 0, 0
14     result = []
15     while i < len(left) and j < len(right):  # 比较传入的两个子序列，对两个子序列进行排序
16         if left[i] <= right[j]:
17             result.append(left[i])
18             i += 1
19         else:
20             result.append(right[j])
21             j += 1
22     result.extend(left[i:])         # 将排好序的子序列合并
23     result.extend(right[j:])
24     return result
25 
26 if __name__ == "__main__":
27     start = time.clock()
28 
29     rand_lst = []
30     for i in range(6):
31         rand_lst.append(round(random.random()*100, 2))
32     lst = merge_sort(rand_lst)
33 
34     end = time.clock()
35     print lst
36     print "done  ", (end-start)