归并排序

归并排序

这个系列是回顾之前所学，是用python商量着完成的。

路过的大佬就当看个乐，实现算法的方式不一，也有讨巧的做法。

我只讲讲我的思路，希望大家浏览的时候能多多提建议，共同学习共同进步。

--------------------------------------------------------------------------------------------------------

归并排序的基本思想:

　　归并也称之为合并，是将两个或两个以上的有序子表合并成一个有序表的过程，合并两个子表也称为二路合并。

举个例子：

[5, 2, 1, 3, 6, 7]

地板除，向下取整

[5, 2, 1] 和 [3, 6, 7]

在此基础上继续二分

[5, 2] [1] [3] [6, 7]

将这些细分的数组进行排序，然后将其一步步向上合并，最终得到有序的原序列

以下是具体实现：

 1 def merge_sort(list):
 2     n = len(list)
 3     if n <= 1:
 4         return list
 5     # 1.先找到数组中的中心点的位置，以此作为二分的基础
 6     pivot_index = n // 2
 7     # 2.既然是不断的往下细分，就自然会想到用递归，而每次二分的依据便是上面的中心点
 8     first_list = merge_sort(list[:pivot_index])
 9     second_list = merge_sort(list[pivot_index:])
10 
11     first_index = 0
12     second_index = 0
13     res = []
14     while first_index < len(first_list) and second_index < len(second_list):
15         if first_list[first_index] < second_list[second_index]:
16             res.append(first_list[first_index])
17             first_index += 1
18         else:
19             res.append(second_list[second_index])
20             second_index += 1
21     res += first_list[first_index:]
22     res += second_list[second_index:]
23 
24     return res