算法子目录：//www.greatytc.com/p/02492be3c5f5

堆排序

堆排序依赖堆的向下调整性质。

流程示意图

流程

流程1

流程2

流程3

流程4

流程5

流程6

我们提取根节点上的元素，并把它删除，那么堆会自动把最大的放在根节点上，然后周而复始，直至堆没有元素。

代码

from cat_time import cal_time
import random

def sift(li,low,high):
    #li表示树，low表示high的父节点，high表示树的最后一个节点
    tmp = li[low]
    i = low
    j = 2 * i + 1  #初始j指向左子节点
    # i 指向空位，j指向子节点
    while j <= high: #退出的第二种情况：j大于high，说明空
        if j + 1 <= high and li[j] < li [j+1]:#如果右子节点存在，且大于左子节点
            j += 1   #则使用右子节点
        if li[j] > tmp:
            #这里比较 li[j] 与 li[j] 的父节点 li[i] 的大小，如果 li[j] 大于 li[i] ，则交换。
            li[i] = li[j]
            # 同时，让i保存j的位置，j再保存相应的左子节点。 接着到while进行判断 j还在不在堆的范围中。
            i = j
            j = 2 * i + 1
        else: #退出的第一种情况：j的位置比tmp小，说明两个子节点都比tmp小。
            break
    li[i] = tmp  #把拿出来的那个值放在空位上面。
@cal_time
def heap_sort(li):
    n = len(li)
    # 构造堆
    for low in range(n//2-1,-1,-1):
        sift(li,low,n-1)
    #挨个出数
    for high in range(n-1,-1,-1):
        #将根和high换位，这样就可以将空间复杂度降到O(1)
        li[0],li[high] = li[high],li[0]
        #high-1是划分出堆区与有序区
        sift(li,0,high-1)

li = list(range(10000))
random.shuffle(li)
heap_sort(li)
print(li)

heapq

这是一个堆排序的内置库，但是很不方便，只有小根堆排序。

import heapq

li = list(range(10))
random.shuffle(li)

#排序
heapq.heapify(li)

#按顺序将一个元素入队
heapq.heappush(li,0.1)
print(li)

#将最小的元素出队
item = heapq.heappop(li)
print(li)

def heapsort(li):
    h = []
    for value in li:
        heapq.heappush(h,value)
    return [heapq.heappop(h) for i in range(len(h))]

print(heapsort(li))

总结

稳定性：堆排是一种不稳定排序。

比较性：因为排序时元素之间需要比较，所以是比较排序

时间复杂度：时间复杂度为O(nlogn)

空间复杂度：空间复杂度可以是O(1)，可以是O(n)