6 堆排序
步骤：
建立堆
得到堆顶元素，为最大元素
去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。
堆顶元素为第二大元素。
重复步骤3，直到堆变空。
def sift(array, left, right):
"""调整"""
i = left # 当前调整的小堆的父节点
j = 2*i + 1 # i的左孩子
tmp = array[i] # 当前调整的堆的根节点
while j <= right: # 如果孩子还在堆的边界内
if j < right and array[j] < array[j+1]: # 如果i有右孩子,且右孩子比左孩子大
j = j + 1 # 大孩子就是右孩子
if tmp < array[j]: # 比较根节点和大孩子，如果根节点比大孩子小
array[i] = array[j] # 大孩子上位
i = j # 新调整的小堆的父节点
j = 2*i + 1 # 新调整的小堆中I的左孩子
else: # 否则就是父节点比大孩子大，则终止循环
break
array[i] = tmp # 最后i的位置由于是之前大孩子上位了，是空的，而这个位置是根节点的正确位置。
def heap(array):
n = len(array)
# 建堆，从最后一个有孩子的父亲开始，直到根节点
for i in range(n//2 - 1, -1, -1):
# 每次调整i到结尾
sift(array, i, n-1)
# 挨个出数
for i in range(n-1, -1, -1):
# 把根节点和调整的堆的最后一个元素交换
array[0], array[i] = array[i], array[0]
# 再调整，从0到i-1
sift(array, 0, i-1)
时间复杂度：O(nlogn)，
稳定性：不稳定
特点：通常都比快排慢
7 为什么堆排比快排慢？
回顾一下堆排的过程：
1. 建立最大堆（堆顶的元素大于其两个儿子，两个儿子又分别大于它们各自下属的两个儿子... 以此类推）
2. 将堆顶的元素和最后一个元素对调（相当于将堆顶元素（最大值）拿走，然后将堆底的那个元素补上它的空缺），然后让那最后一个元素从顶上往下滑到恰当的位置（重新使堆最大化）。
3. 重复第2步。
这里的关键问题就在于第2步，堆底的元素肯定很小，将它拿到堆顶和原本属于最大元素的两个子节点比较，它比它们大的可能性是微乎其微的。实际上它肯定小于其中的一个儿子。而大于另一个儿子的可能性非常小。于是，这一次比较的结果就是概率不均等的，根据前面的分析，概率不均等的比较是不明智的，因为它并不能保证在糟糕情况下也能将问题的可能性削减到原本的1/2。可以想像一种极端情况，如果a肯定小于b，那么比较a和b就会什么信息也得不到——原本剩下多少可能性还是剩下多少可能性。
在堆排里面有大量这种近乎无效的比较，因为被拿到堆顶的那个元素几乎肯定是很小的，而靠近堆顶的元素又几乎肯定是很大的，将一个很小的数和一个很大的数比较，结果几乎肯定是“小于”的，这就意味着问题的可能性只被排除掉了很小一部分。
这就是为什么堆排比较慢（堆排虽然和快排一样复杂度都是O(NlogN)但堆排复杂度的常系数更大）。
MacKay也提供了一个修改版的堆排：每次不是将堆底的元素拿到上面去，而是直接比较堆顶（最大）元素的两个儿子，即选出次大的元素。由于这两个儿子之间的大小关系是很不确定的，两者都很大，说不好哪个更大哪个更小，所以这次比较的两个结果就是概率均等的了
8 归并排序
思路：
一次归并：将现有的列表分为左右两段，将两段里的元素逐一比较，小的就放入新的列表中。比较结束后，新的列表就是排好序的。
然后递归。