Python算法解析：堆排序的娴熟应用，数据排序高手进阶！堆排序

测试开发囤货

发布于 2023-08-08 09:30:18

1680

发布于 2023-08-08 09:30:18

文章被收录于专栏：测试开发囤货

Python算法解析：堆排序的娴熟应用，数据排序高手进阶！

堆排序

堆排序是一种基于二叉堆数据结构的排序算法，它通过构建最大堆或最小堆来进行排序。

堆排序算法的原理和实现步骤

构建最大堆（Max Heap）：将待排序的列表构建成一个最大堆。最大堆是一个完全二叉树，其中每个节点的值都大于或等于其子节点的值。构建最大堆的过程可以从列表的中间位置开始，从下往上对每个节点进行堆化操作，保证父节点的值大于或等于子节点的值。
排序：将最大堆的根节点（最大值）与堆的最后一个节点交换，并将堆的大小减1。然后对根节点进行堆化操作，使其保持最大堆的性质。重复这个步骤，直到堆的大小减为1，即完成排序。

示例

用Python编写堆排序算法示例

下面是用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[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

# 测试示例
nums = [64, 25, 12, 22, 11]
heap_sort(nums)
print("排序后的数组:", nums)

在这个示例中，我们定义了两个函数：heapify和heap_sort。函数heapify用于对指定节点进行堆化操作，保持最大堆的性质。函数heap_sort用于执行堆排序算法，首先构建最大堆，然后逐步将最大值交换到列表的末尾，最后得到排序好的列表。

可视化

可视化展示堆排序算法的执行过程

以下是堆排序算法的可视化示例：

原始数组: [64, 25, 12, 22, 11]

构建最大堆:
        64
       /  \
     25    12
    /  \
  22    11

交换根节点和最后一个节点:
        11
       /  \
     25    12
    /  \
  22    64

         12
       /  \
     25    11
    /
  22

交换根节点和最后一个节点:
        11
       /  \
     22    12
    /
  25

         12
       /  \
     22    11

交换根节点和最后一个节点:
        11
       /  \
     12    22

排序后的数组: [11, 12, 22, 25, 64]

通过这个可视化示例，你可以看到堆排序算法是如何构建最大堆，并逐步将最大值交换到列表的末尾来完成排序的。