堆排序原理及算法代码详解

堆排序原理及算法代码详解

堆排序属于一种选择排序，它的基本思想是利用堆这种数据结构来进行排序。

堆的概念

堆（Heap）是一个特殊的树形数据结构，它有以下两种类型：

• 大根堆：每个节点的值都大于或等于其左右孩子节点的值。
• 小根堆：每个节点的值都小于或等于其左右孩子节点的值。

通过对堆进行操作，可以得到堆排序算法。

堆排序的基本思想

• 将待排序序列构造成一个大根堆。
• 此时，整个序列的最大值就是堆顶的根节点。
• 将它和堆数组的末尾元素交换，这样末尾就是最大值了。
• 然后将剩余的n-1个元素重新构造成一个堆，这样就会得到n个元素中的次大值。
• 如此反复进行交换、重建大根堆的操作，直到整个序列有序。

堆排序的算法实现

下面是基于python语言实现的堆排序算法代码：

# heapify函数为创建大根堆的过程
# 功能：将序列转化为大根堆
# i：表示一个根节点的下标
# n：表示序列的长度，保证待调整的左、右子树都已经是大根堆
def heapify(arr, n, i):
    largest = i  # 初始化根节点为最大值
    l = 2 * i + 1   # 左子节点的下标
    r = 2 * i + 2   # 右子节点的下标

    # 如果左子树下标在序列中 and
    # 左子树的值大于根节点的值
    if l < n and arr[i] < arr[l]:
        largest = l

    # 如果右子树下标在序列中 and
    # 右子树的值大于根节点和左子树的值
    if r < n and arr[largest] < arr[r]:
        largest = r

    # 如果最大值不是根节点，就交换它们
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换根节点和最大值
        heapify(arr, n, largest)

# heapSort函数为堆排序函数
# 功能：对整个序列进行排序
def heapSort(arr,n):

    # 构建大根堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 从末尾开始排序
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]    # 交换根节点和末尾元素
        heapify(arr, i, 0)    # 重新构造大根堆

堆排序示例说明：

将以下序列进行排序：[12, 11, 13, 5, 6, 7]

• 构造大根堆，序列变为[13, 11, 12, 5, 6, 7]，堆顶元素为13
• 交换堆顶元素13和末尾元素7，此时序列变为[7, 11, 12, 5, 6, 13]，排除末尾元素7后重新构造大根堆，序列变为[12, 11, 7, 5, 6]，堆顶元素为12
• 交换堆顶元素12和末尾元素6，此时序列变为[6, 11, 7, 5, 12]，排除末尾元素6后重新构造大根堆，序列变为[11, 5, 7, 6]，堆顶元素为11
• 交换堆顶元素11和末尾元素5，此时序列变为[5, 6, 7, 11]，排除末尾元素5后重新构造大根堆，序列变为[7, 6, 5]，堆顶元素为7
• 交换堆顶元素7和末尾元素5，此时序列变为[5, 6, 7]，排除末尾元素5后重新构造大根堆，序列变为[6, 5]，堆顶元素为6
• 交换堆顶元素6和末尾元素5，此时序列变为[5, 6]，排除末尾元素5后重新构造大根堆，序列变为[5]，堆顶元素为5
• 排序完成，最终序列为[5, 6, 7, 11, 12, 13]

以上是堆排序原理及算法代码的详细讲解，如有不明白的地方，可随时进行提问。