python 堆排序（保姆级教程）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

def heapify(arr, n, i):
    largest = i  # 初始化最大值为根节点
    l = 2 * i + 1  # 左子节点的索引
    r = 2 * i + 2  # 右子节点的索引

    # 如果左子节点存在且大于根节点
    if l < n and arr[i] < arr[l]:
        largest = l

        # 如果右子节点存在且大于当前最大值
    if r < n and arr[largest] < arr[r]:
        largest = r

        # 如果最大值不是根节点
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换
        print(arr,'@')  # 对每次处理过程进行输出并标记

        # 递归地调整受影响的子堆
        heapify(arr, n, largest)


def heap_sort(arr):
    n = len(arr)  # 获取列表长度

    # 构建最大堆，将数据调整为最大堆结构
    for i in range(n//2-1, -1, -1):
        heapify(arr, n, i)
        print(arr,'*')

    # 一个个从堆中取出元素
    print('--------------------')
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)  # 将交换数据后的arr列表调整为最大堆，确保每一步都是最大堆数据结构
        print(arr,'-')


# 测试堆排序函数
arr = [1, 2, 3, 5, 6, 7]
heap_sort(arr)
print("排序后的数组:")
print(arr)

数据处理过程：

原始列表：

arr = [1, 3, 2, 5, 4, 7]

堆型数据结构为：

构建最大堆第一步处理：

1、第一个for循环中，i =2, heapify(arr, 6, 2)，运行后

2、第一个for循环中，i =1, heapify(arr, 6, 1)，运行后

3、第一个for循环中，i =0, heapify(arr, 6, 0)，运行后

到此第一个for循环完成，已经完成了最大堆数据的构建

开启第二个for循环，对数据进行排序的程序

1、第二个for循环 分别是5,4,3,2,1,进行遍历，

     i = 5,此时最大值的索引为0，将索引5和索引值为0的项进行交换

    heapify(arr, 5, 0)对arr列表的对数据进行调整，确保为最大堆

   1）heapify(arr, 5, 0)

  2） heapify(arr, 5, 1)-自调用

   已经是最大堆数据结构

2、第二个for循环 i=4 对索引是0和4的项进行交换

  1） heapify(arr, 4, 0)-递归

  2）  heapify(arr, 4, 1)-递归

  已经完成对结构的调整，是最大堆数据结构

3、第二个for循环 i=3 对索引是0和3的项进行交换

  1） heapify(arr, 3, 0)-递归

  已经条整对大堆形式的数据结构

4、第二个for循环 i=2 对索引是0和2的项进行交换

  1） heapify(arr, 2, 0)-递归

  已经调整为最大堆形式的数据

5、4、第二个for循环 i=1 对索引是0和1的项进行交换

完成所有数据排序

输出排序完成的列表

arr[1,2,3,4,5,7]