归并排序
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组
将数组分解到最小之后，合并两个有序的数组，基本思路就是比较两个数组最前面的数字，谁小就先取谁，取了后相应的指针就往后移动一位。然后再比较，知道一个数组为空，最后把一个数组的剩余部分复制过来即可
文章目录
- 归并排序
-
-
-
- 基本实现
-
- 这个就是归并算法的思想：把一组元素一直拆分到只有一个子元素，之后开始合并，通过Left与Right进行排序。
- 归并算法代码实现
- 时间复杂度
-
-
基本实现
1.有一串数组如下，将其对半分成两个数组。
2.左右继续拆分到每一个子部分只有一个元素，如下，拆分到只有一个子元素的之后拆分结束
3，拆分完之后进行合并，56跟26是上面绿色框拆出来的，合并的时候采用小的在前，大的在后。
4.把两个绿色块进行合并，这个时候就要借助定义的游标了，一个指的是左边大部分Left ，一个是右边的Right.合并的时候采用的方式是，对于左边的部分有一个游标，右边的部分也有一个游标，然后对于所指的两个部分进行比较换位。
5.经过比较17比较小，拿出来，之后Right向后移动一位。
6.之后继续比较Right的指向比26大，取出26，Left继续向后移动一位。之后比较发现Right指向比Left大，取出54，最后把Right放到后面，得到下面的一个有序数列。
7.右边继续采用相同的方式，的得到两个部分，之后现在对于整个序列来说就只有两个部分了。
8.按照上面相同的方式对两个绿色框的数据进行合并。依旧是左边的游标Left，右边的右边Right对比。得到了一个有序的数列
这个就是归并算法的思想：把一组元素一直拆分到只有一个子元素，之后开始合并，通过Left与Right进行排序。
那么对于奇数个也是一样的，只不过拆分的时候最后的的一组多出来一个。合并的时候也是，先把最后那个灰色框那两个合并到一起，再跟44合并成3个，怎么拆的就怎么合并。
归并算法代码实现
'''
Create by YO
@Time: 2020/4/22
'''
#相除的时候两个斜杠无小数部分。向下取整
def merge_sort(alist):
'''归并排序'''
n=len(alist)
if n<=1:
return alist
mid=n//2 #中间值
left_li=merge_sort(alist[:mid])
#right 采用归并排序后形成的新的列表
right_li=merge_sort(alist[mid:])
#将两个有序的子序列合并成一个新的整体 merge(left,right) 左边的指针跟右边的指针都指向两个子序列的第一个元素
left_pointer,right_pointer=0,0
result=[]
while left_pointer<len(left_li) and right_pointer<len(right_li):
if left_li[left_pointer]<right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer+=1 #移动完向后一位移动
else:
result.append(right_li[right_pointer])
right_pointer+=1
result+=left_li[left_pointer:]
result+=right_li[right_pointer:]
return result
if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
sorted_li=merge_sort(li)
print(li)
print(sorted_li)
输出：
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93] 复制
时间复杂度
最优时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
稳定性：稳定