八大排序算法的Python实现__7__堆排序

环境

Python 3.5.2

原理

  • 将列表构造成最大堆或最小堆
  • 将堆的根节点,即最大值或最小值与堆的末尾对调
  • 将末尾元素(即之前得到的堆的根节点)移除后,重构堆,如此循环

源码

def heap_sort(l):
    def max_heapify(root_index, end_index):
        """函数用于构造最大堆"""
        # 减一是因为堆的下标从1开始
        max_child_index = root_index*2-1

        # 在该二叉树有两个子节点的情况下,将两个子节点比较大小
        if max_child_index + 1 < end_index:
            if l[max_child_index+1] > l[max_child_index]:
                max_child_index += 1

        # 将最大的子节点与根节点做比较
        if l[max_child_index] > l[root_index-1]:
            l[max_child_index], l[root_index-1] = l[root_index-1], l[max_child_index]


    # 循环构造最大堆,而后将最大堆的根节点与末节点调换
    for end_index in range(len(l), 1, -1):
        # 每次要构造的最大堆大小与末节点有关
        max_root_index = end_index//2

        # 构造一个最大堆
        for root_index in range(max_root_index, 0, -1):
            max_heapify(root_index, end_index)

        # 将最大堆的根节点与末节点调换
        l[0], l[end_index-1] = l[end_index-1], l[0]


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    heap_sort(l)
    print(l)

时间复杂度

  • 最优时间复杂度:O(nlogn)
  • 最坏时间复杂度:O(nlogn)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):不稳定

说点什么

  Subscribe  
提醒