排序：归并排序

一、归并

li=[2,4,5,7,//1,3,6,8]#归并的前提是必须两部分排好序

def merge(li,low,mid,high):i=lowj=mid+1ltmp=[]while i<=mid and j<=high: #只要左右两边都有数if li[i]<li[j]:ltmp.append(li[i])i+=1else:ltmp.append(li[j])j+=1#while执行完，肯定有一部分没数了while i<=mid:ltmp.append(li[i])i+=1while j<=high:ltmp.append(li[j])j+=1li[low:high+1]=ltmpli=[2,4,5,7,1,3,6,8]
merge(li,0,3,7)
print(li)

二、归并排序

1.分解:将列表越分越小，直至分成一个元素。
2.终止条件:一个元素是有序的。
3.合并:将两个有序列表归并，列表越来越大。

def merge(li,low,mid,high):i=lowj=mid+1ltmp=[]while i<=mid and j<=high: #只要左右两边都有数if li[i]<li[j]:ltmp.append(li[i])i+=1else:ltmp.append(li[j])j+=1#while执行完，肯定有一部分没数了while i<=mid:ltmp.append(li[i])i+=1while j<=high:ltmp.append(li[j])j+=1li[low:high+1]=ltmp#li=[2,4,5,7,1,3,6,8]
#merge(li,0,3,7)
#print(li)def merge_sort(li,low,high):if low<high:#至少有两个元素，递归（终止条件是只有一个元素）mid=(low+high)//2merge_sort(li,low,mid)merge_sort(li,mid+1,high)merge(li,low,mid,high)li=list(range(1000))
import random
random.shuffle(li)
print(li)
merge_sort(li,0,len(li)-1)
print(li)

时间复杂度：O(nlogn)（logn层，每一层为n）
空间复杂度：O(n)

归并、快速、堆排序

1.三种排序算法的时间复杂度都是0(nlogn)
2.一般情况下，就运行时间而言:
快速排序<归并排序<堆排序.
3.三种排序算法的缺点:
快速排序:极端情况下排序效率低
归并排序:需要额外的内存开销
堆排序:在快的排序算法中相对较慢

（隔着换不稳定）