堆排序 - 算法实现 - 堆排序的代码实现

堆排序 - 算法实现 - 堆排序的代码实现

一、引言

在计算机科学的世界里，排序算法就像是一把神奇的钥匙，能够将杂乱无章的数据变得井井有条。堆排序作为一种高效的排序算法，以其独特的优势在众多排序算法中脱颖而出。它的时间复杂度稳定在 $O(n log n)$，并且不需要额外的大量存储空间。接下来，我们将深入探究堆排序的原理，并给出其代码实现。

二、堆排序的基本概念

2.1 堆的定义

堆是一种特殊的完全二叉树，分为最大堆和最小堆。

• 最大堆：每个节点的值都大于或等于其子节点的值。
• 最小堆：每个节点的值都小于或等于其子节点的值。

2.2 堆排序的原理

堆排序的核心思想是利用堆这种数据结构的特性。首先，将待排序的数组构建成一个最大堆（或最小堆），此时堆顶元素就是数组中的最大值（或最小值）。然后，将堆顶元素与数组的最后一个元素交换位置，这样最大值（或最小值）就被放到了正确的位置。接着，将剩余的元素重新调整为一个最大堆（或最小堆），重复上述步骤，直到整个数组有序。

三、堆排序的代码实现（Python 语言）

def heapify(arr, n, i):
    # 初始化根节点
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    # 如果左子节点大于根节点
    if left < n and arr[left] > arr[largest]:
        largest = left
    # 如果右子节点大于当前最大节点
    if right < n and arr[right] > arr[largest]:
        largest = right
    # 如果最大节点不是根节点
    if largest!= i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # 递归调整受影响的子树
        heapify(arr, n, largest)
def heap_sort(arr):
    n = len(arr)
    # 构建最大堆
    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)
    return arr
# 测试代码
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
print("排序后的数组:", sorted_arr)

3.3 代码解释

• heapify 函数：该函数用于将以索引 i 为根节点的子树调整为最大堆。它首先找到根节点、左子节点和右子节点中的最大值，然后将最大值与根节点交换位置。如果发生了交换，还需要递归地调整受影响的子树。
• heap_sort 函数：该函数实现了堆排序的整个过程。首先，通过循环调用 heapify 函数将整个数组构建成一个最大堆。然后，依次将堆顶元素与数组的最后一个元素交换位置，并重新调整剩余的元素为最大堆，直到整个数组有序。

四、复杂度分析

五、总结

堆排序是一种高效的排序算法，它结合了堆这种数据结构的特性，通过构建最大堆和不断调整堆的方式实现排序。其时间复杂度稳定，空间复杂度低，适用于处理大规模数据。通过本文的介绍和代码实现，相信你已经对堆排序有了更深入的理解，可以在实际应用中灵活运用堆排序算法。