# 一次归并
def merge(array, low, mid, high):
"""
两段需要归并的序列从左往右遍历，逐一比较，小的就放到
tmp里去，再取，再比，再放。
"""
tmp = []
i = low
j = mid +1
while i <= mid and j <= high:
if array[i] <= array[j]:
tmp.append(array[i])
i += 1
else:
tmp.append(array[j])
j += 1
while i <= mid:
tmp.append(array[i])
i += 1
while j <= high:
tmp.append(array[j])
j += 1
array[low:high+1] = tmp
def merge_sort(array, low, high):
if low < high:
mid = (low + high) // 2
merge_sort(array, low, mid)
merge_sort(array, mid+1, high)
merge(array, low, mid, high)
时间复杂度：O(nlogn)
稳定性：稳定
快排、堆排和归并的小结
三种排序算法的时间复杂度都是O(nlogn)
一般情况下，就运行时间而言：
快速排序 < 归并排序 < 堆排序
三种排序算法的缺点：
快速排序：极端情况下排序效率低
归并排序：需要额外的内存开销
堆排序：在快的排序算法中相对较慢
9 希尔排序
希尔排序是一种分组插入排序算法。
首先取一个整数d1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序；
取第二个整数d2=d1/2，重复上述分组排序过程，直到di=1，即所有元素在同一组内进行直接插入排序。希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。
def shell_sort(li):
"""希尔排序"""
gap = len(li) // 2
while gap > 0:
for i in range(gap, len(li)):
tmp = li[i]
j = i - gap
while j >= 0 and tmp < li[j]:
li[j + gap] = li[j]
j -= gap
li[j + gap] = tmp
gap //= 2
时间复杂度:O((1+τ)n)
不是很快，位置尴尬
10 排序小结
