Python排序算法之堆排序

思路

    Step1: 构建堆
        从最后一个非叶子结点开始向下调整，使其成为一个堆
    Step2: 挨个出数
        堆构建完后，得到堆顶，即为最大的元素
        1) 将堆顶和堆的最后一个元素互换
        2) 再使用向下调整，使其成为一个新堆
        3) 调整完成后，得到第二大的元素
        4) 从 1) 开始重复，直到堆为空

时间复杂度

    最坏情况：O(nlogn)
    平均情况：O(nlogn)
    最好情况：O(nlogn)

空间复杂度

O(1)

稳定性

不稳定

复杂度

复杂

代码示例

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""堆排序

思路：
    Step1: 构建堆
        从最后一个非叶子结点开始向下调整，使其成为一个堆
    Step2: 挨个出数
        堆构建完后，得到堆顶，即为最大的元素
        1) 将堆顶和堆的最后一个元素互换
        2) 再使用向下调整，使其成为一个新堆
        3) 调整完成后，得到第二大的元素
        4) 从 1) 开始重复，直到堆为空

时间复杂度：
    最坏情况：O(nlogn)
    平均情况：O(nlogn)
    最好情况：O(nlogn)

空间复杂度：O(1)

稳定性：不稳定

复杂性：复杂
"""
import random


# 向下调整
def sift(ls, low, high):
    """向下调整函数

    如果一个堆的根节点左右子树都是堆，但其本身不是堆，
    则通过向下调整使其成为堆

    Args:
        :param ls: list, 待调整的列表
        :param low: int, 当前堆的根节点
        :param high: int, 当前堆的最后一个元素
    """

    i = low
    j = 2 * i + 1  # 默认指向左孩子
    tmp = ls[low]

    while j <= high:  # 只要j位置上有数
        if j + 1 <= high and ls[j + 1] > ls[j]:  # 右孩子存在且比较大
            j += 1  # j指向右孩子

        if ls[j] > tmp:
            ls[i] = ls[j]  # 更新堆顶
            # 往下走一层，决定tmp去哪
            i = j
            j = 2 * i + 1
        else:
            ls[i] = tmp
            break
    else:
        ls[i] = tmp


# 堆排序
def heap_sort(ls):
    """堆排序

    完成构建堆以及挨个出数两个功能

    Args:
        :param ls: list, 待排序的列表
    """

    # 构建堆
    # 从最后一个非叶子节点开始调整
    # 最后一个非叶子节点 (n - 1) // 2
    # 注意: 这里的n代表的是列表最后一个元素的下标
    # n = len(ls) - 1; (n - 1) // 2
    # 所以经整合以及化简得到 n // 2 - 1
    n = len(ls)
    for i in range(n // 2 - 1, -1, -1):
        sift(ls, i, n - 1)

    # 挨个出数
    for i in range(n - 1, -1, -1):
        ls[0], ls[i] = ls[i], ls[0]
        sift(ls, 0, i - 1)


ls = [_ for _ in range(20)]

random.shuffle(ls)
heap_sort(ls)
print(ls)