前言

排序算法大致可以分为两类：比较型排序和非比较型排序。根据其功能又可以细分为交换类、选择类、归并类、插入类以及计数类。之前的文章中，我们已经探讨了交换排序中的快速排序、归并排序中的二路归并排序以及非比较排序中的基数排序。接下来，我们将重点介绍选择排序中的堆排序。

二叉树基础

堆可以被视作一种特殊的完全二叉树。完全二叉树是一种特殊的二叉树，其中每个节点除了最后一层外都填满了节点，并且最后一层的节点尽可能地靠左排列。二叉树的特点是每个节点最多有两个子节点。满二叉树则是每一层都填满的二叉树，而完全二叉树则是在满二叉树的基础上允许最后一层缺失一些连续的节点。

堆排序

堆排序是一种基于堆数据结构的选择排序算法。堆可以分为最大堆和最小堆，最大堆的特性是每个父节点的值都大于或等于其子节点的值，而最小堆则是每个父节点的值都小于或等于其子节点的值。

大根堆示例

下面我们以大根堆为例，介绍堆排序的具体过程。假设待排序序列为 [1, 8, 9, 3, 4, 6, 7]。

1. 构建初始大根堆：首先将初始无序序列构建成一个大根堆，使得每个父节点的值大于其子节点的值。

   

2. 交换根节点和最后一个节点：将堆顶元素（即最大值）与序列末尾元素交换，形成新的无序序列和有序序列。

   

3. 重复构建大根堆并交换：对新形成的无序序列再次构建大根堆，并将堆顶元素与序列末尾元素交换，逐步形成有序序列。

   

4. 最终排序结果：经过多次调整和交换后，最终得到有序序列 [1, 3, 4, 6, 7, 8, 9]。

代码实现

以下是堆排序的 Python 和 Java 实现。

Python 实现

```python def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2

if left < n and arr[i] < arr[left]:
    largest = left

if right < n and arr[largest] < arr[right]:
    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)

```

Java 实现

```java public class HeapSort { public static void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        heapify(arr, n, largest);
    }
}

public static void heap_sort(int[] arr) {
    int n = arr.length;

    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

} ```

复杂度分析

• 时间复杂度：O(n log n)。堆排序的时间复杂度是固定的，不受输入数据的影响。
• 空间复杂度：O(1)。堆排序是原地排序算法，不需要额外的空间。
• 稳定性：不稳定。堆排序在交换过程中可能会改变相同值元素的相对顺序。

总结

通过上述内容，我们可以看出堆排序是一种高效且实用的排序算法，特别是在处理大规模数据时。堆排序利用了二叉树的特性，能够有效地进行排序操作。掌握堆排序的关键在于理解如何构建和维护堆的结构。下一篇文章将对各种排序算法进行总结和对比。