归并排序

算法思想：

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

 1 [54, 26, 93, 17, 77, 31, 44, 55]  #升序排序
 2 #分解  n//2
 3 # [54, 26, 93, 17]   [77, 31, 44, 55]
 4 #
 5 # [54, 26]  [93, 17]   [77, 31]  [44, 55]
 6 #
 7 # [54]  [26]  [93] [17]   [77]  [31]  [44] [55]
 8 
 9 #合并
10 # [26,54] [17,93] [31,77] [44,55]
11 #
12 # [17,26,(54,1),93]   [31,44,(54,2),55,77]
13 #
14 # [17,26,31,44,54,55,77,93]
15 
16 def merg_sort(alist):
17     #分解
18     n=len(alist)
19     #递归的出口 分解到最小
20     if n<=1:
21         return alist
22     mid=n//2
23     left_li=merg_sort(alist[0:mid])
24     right_li=merg_sort(alist[mid:])
25 
26     #合并
27     #排序结果列表
28     result=[]
29     left_pointer,right_pointer=0,0
30     while left_pointer<len(left_li) and right_pointer<len(right_li):
31         if left_li[left_pointer] <=right_li[right_pointer]:
32             result.append(left_li[left_pointer])
33             left_pointer += 1
34         else:
35             result.append(right_li[right_pointer])
36             right_pointer += 1
37 
38     #退出循环后，将不为空的列表剩余元素添加到result中
39     # result+=left_li[left_pointer:]
40     result.extend(left_li[left_pointer:])
41     result+=right_li[right_pointer:]
42 
43     #将最后排序的结果列表返回
44     return result
48 if __name__ =='__main__':
49     alist=[54, 26, 93, 17, 77, 31, 44, 55]
50     print('原来的数组：')
51     print(alist)
52     result=merg_sort(alist)
53     print('排序后：')
54     print(result)

1 原来的数组：
2 [54, 26, 93, 17, 77, 31, 44, 55]
3 排序后：
4 [17, 26, 31, 44, 54, 55, 77, 93]

正是江南好风景