本文共 3446 字，大约阅读时间需要 11 分钟。

堆排序

    前面讲了堆的向下调整，今天来讲讲怎么利用堆进行排序即堆排序！

1. 步骤

1. 先根据完全二叉树建立堆(农村包围城市)
2. 得到堆顶元素，为最大元素
3. 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整使堆有序
4. 堆顶元素为第二大元素
5. 重复步骤3，直到堆变空

简单点概括就是先建立堆，再根据前面所学的向下调整函数，将堆从下到上、从小到大依次调整就变为一个大根堆或者小根堆，最后挨个出数，就能排序了！

2. 演示

1. 建立堆

拿以下这个完全二叉树举例:

2. 挨个出数

第一步已经建立好堆，那么现在堆的根结点为最大的数，先把根结点取出，放在列表中，再将堆的最后一个放到堆顶，再进行向下调整，调整后，堆的根结点又是最大数，再次将根结点放入列表，再次将堆的最后一个放到堆顶，重复这些步骤，知道所有的数都放入了列表。

3. 代码

'''TOP: 堆排序author: Bluetime: 2020-07-24QQ: 2458682080'''# 堆排序没有递归# 针对大根堆的调整函数def sift(li, root, last):    """    :param li: 列表    :param root: 二叉树的根结点的下标    :param last: 二叉树的最后一个元素的下标    :return:    """    temp = li[root]   # 将根结点暂时储存起来    i = root  # i最开始指的是根结点    child = i * 2 + 1  # 先指向左孩子    while child <= last:   # 只要不到最后一个叶结点        if child+1 <= last and li[child+1] > li[child]:  #当右孩子>左孩子            child += 1  # 就把要换上去(要变为空位)的节点变为右孩子        if li[child] > temp:            li[i]  = li[child]            i = child  # 向下看一层            child = i * 2 + 1  # 继续指向左孩子        else:    # li[child] > temp 如果目前空位的最大的孩子都比tmep小，那temp就可以放这里            li[i] = temp            break     else:  # 当目前节点在叶结点时        li[i] = temp# 堆排序def heap_sort(li):    n = len(li)    # 第一步: 建立堆    for i in range((n - 2) // 2, -1, -1):    # 因为是从后往前，所以第一个-1是指i可以到列表第一个0 ，第二个-1是步长是        # i表示建堆的时候调整的部分的根下标        sift(li, i, n-1)    # 第二步: 堆建立完成后，开始挨个出数    for i in range(n - 1, -1, -1):        # i指向当前堆的最后一个元素        li[0], li[i] = li[i], li[0]  # 这里为了节省空间，直接将堆后面不要的空间进行储存，实在不理解的读者可以自己新建一个列表储存拿出来的值        sift(li, 0, i - 1)   # i-1是新的lastli = [i for i in range(100)]import randomrandom.shuffle(li)print(li)heap_sort(li)print(li)

结果为:

[33, 74, 48, 29, 37, 7, 77, 68, 97, 17, 90, 98, 87, 28, 30, 70, 53, 63, 4, 3, 92, 94, 14, 10, 47, 22, 57, 59, 36, 56, 1, 44, 26, 84, 18, 82, 43, 51, 21, 15, 69, 72, 64, 78, 58, 52, 55, 49, 61, 45, 60, 40, 23, 50, 31, 13, 25, 91, 9, 83, 71, 86, 20, 62, 75, 5, 88, 67, 38, 73, 32, 76, 24, 35, 96, 93, 81, 8, 39, 85, 79, 6, 99, 42, 12, 54, 0, 89, 65, 46, 27, 2, 95, 80, 41, 11, 66, 16, 19, 34][0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]

时间复杂度为: O(nlog(n))

import heapq    # q——>queue  优先队列import randomli = list(range(100))random.shuffle(li)print(li)heapq.heapify(li)  # 建堆heapq.heappop(li)  # 每次弹出一个最小的元素print(li)

结果为:

[75, 10, 74, 1, 32, 54, 20, 21, 52, 66, 24, 51, 35, 14, 46, 2, 49, 57, 96, 79, 99, 25, 94, 73, 26, 30, 70, 31, 18, 41, 64, 58, 81, 40, 91, 9, 0, 5, 19, 83, 33, 63, 80, 60, 89, 67, 29, 27, 55, 72, 97, 36, 4, 42, 71, 98, 45, 87, 3, 17, 11, 53, 28, 8, 85, 47, 88, 76, 39, 65, 86, 23, 50, 59, 6, 62, 61, 44, 15, 90, 37, 12, 68, 7, 78, 95, 22, 56, 38, 16, 82, 34, 43, 69, 92, 48, 77, 84, 13, 93][1, 2, 3, 5, 7, 4, 11, 8, 6, 12, 16, 13, 30, 14, 17, 21, 39, 9, 10, 32, 22, 24, 29, 27, 26, 35, 42, 31, 18, 41, 28, 58, 47, 40, 65, 23, 52, 61, 15, 37, 33, 63, 66, 38, 25, 34, 69, 48, 55, 72, 97, 36, 54, 70, 71, 98, 45, 87, 20, 46, 74, 53, 64, 75, 85, 81, 88, 76, 49, 91, 86, 93, 50, 59, 57, 62, 96, 44, 19, 90, 83, 79, 68, 99, 78, 95, 80, 56, 60, 89, 82, 67, 43, 94, 92, 51, 77, 84, 73]

转载地址：http://efiwi.baihongyu.com/