排序算法----归并排序

归并排序

　　归并排序采用分而治之的原理：

　　　　- 将一个序列从中间位置分成两个序列；

　　　　- 在将这两个子序列按照第一步继续二分下去；

　　　　- 直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。　　

下图中的倒数第三行表示为第一次合并后的数据。其中一组数据为 4 8 ， 5 7。该两组数据合并方式为：每一小组数据中指定一个指针，指针指向每小组数据的第一个元素，通过指针的偏移指定数据进行有序排列。排列情况如下：

　　　　　　1. p1指向4，p2指向5，p1和p2指向的元素4和5进行比较，较小的数据归并到一个新的列表中。经过比较p1指向的4会被添加到新的列表中，则p1向后偏移一位，指向了8，p2不变。

　　　　　　2.p1和p2指向的元素8，5继续比较，则p2指向的5较小，添加到新列表中，p2向后偏移一位，指向了7。

　　　　　　3.p1和p2指向的元素8，7继续比较，7添加到新列表中，p2偏移指向NULL，比较结束。

　　　　　　4.最后剩下的指针指向的数据（包含该指针指向数据后面所有的数据）直接添加到新列表中即可。

 1 def merge_sort(alist):
 2     n = len(alist)
 3     #结束递归的条件
 4     if n <= 1:
 5         return alist
 6     #中间索引
 7     mid = n//2
 8 
 9     left_li = merge_sort(alist[:mid])
10     right_li = merge_sort(alist[mid:])
11 
12     #指向左右表中第一个元素的指针
13     left_pointer,right_pointer = 0,0
14     #合并数据对应的列表：该表中存储的为排序后的数据
15     result = []
16     while left_pointer < len(left_li) and right_pointer < len(right_li):
17         #比较最小集合中的元素，将最小元素添加到result列表中
18         if left_li[left_pointer] < right_li[right_pointer]:
19             result.append(left_li[left_pointer])
20             left_pointer += 1
21         else:
22             result.append(right_li[right_pointer])
23             right_pointer += 1
24     #当左右表的某一个表的指针偏移到末尾的时候，比较大小结束，将另一张表中的数据（有序）添加到result中
25     result += left_li[left_pointer:]
26     result += right_li[right_pointer:]
27 
28     return result
29 
30 alist = [3,8,5,7,6]
31 print(merge_sort(alist))