跳到主要内容

堆排序

代码​

C语言代码：

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heap_sort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

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

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    heap_sort(arr, n);

    printf("\nSorted array is \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

代码解释​

  1. 初始化：数组 arr 是待排序的数组，n 是数组的长度。
  2. 交换函数：
    • swap 函数用于交换两个整数的值。
  3. 堆化函数：
    • heapify 函数用于将子树调整为最大堆。
    • largest 初始为根节点 i。
    • left 是左子节点，right 是右子节点。
    • 比较根、左子节点和右子节点，找到最大值。
    • 如果最大值不是根节点，交换并递归堆化受影响的子树。
  4. 堆排序函数：
    • heap_sort 首先构建最大堆。
    • 从最后一个非叶子节点开始，向上堆化每个节点。
    • 然后逐个将最大元素（根节点）移到数组末尾，并重新堆化剩余元素。

示例运行​

假设输入数组为 {12, 11, 13, 5, 6, 7}：

  1. 初始状态：{12, 11, 13, 5, 6, 7}
  2. 构建最大堆：
    • 堆化从最后一个非叶子节点开始（索引2）：{12, 11, 13, 5, 6, 7} -> {12, 11, 13, 5, 6, 7}
    • 堆化索引1：{12, 11, 13, 5, 6, 7} -> {12, 13, 11, 5, 6, 7}
    • 堆化索引0：{12, 13, 11, 5, 6, 7} -> {13, 12, 11, 5, 6, 7}
  3. 开始排序：
    • 交换根节点和最后一个元素：{13, 12, 11, 5, 6, 7} -> {7, 12, 11, 5, 6, 13}
    • 堆化根节点：{7, 12, 11, 5, 6, 13} -> {12, 7, 11, 5, 6, 13}
    • 交换根节点和倒数第二个元素：{12, 7, 11, 5, 6, 13} -> {6, 7, 11, 5, 12, 13}
    • 堆化根节点：{6, 7, 11, 5, 12, 13} -> {11, 7, 6, 5, 12, 13}
    • 继续上述过程直到数组排序完成。
  4. 最终结果：{5, 6, 7, 11, 12, 13}

时间复杂度分析​

堆排序的时间复杂度主要取决于构建堆和排序的过程。

  • 最优时间复杂度：O(nlog⁡n)O(n \log n)，因为每次堆化操作需要对数时间。
  • 最坏时间复杂度：O(nlog⁡n)O(n \log n)，无论输入数组的初始顺序如何，执行的步骤基本一致。
  • 平均时间复杂度：O(nlog⁡n)O(n \log n)，对于大多数输入数组，堆排序的性能都很稳定。

空间复杂度分析​

堆排序在原地排序，不需要额外的辅助空间，因此空间复杂度为 O(1)O(1)。

优缺点​

优点：

  • 时间复杂度稳定，适用于大规模数据排序。
  • 不需要额外的辅助空间，空间复杂度低。
  • 无论输入数组的初始顺序如何，时间复杂度保持一致。

缺点：

  • 不稳定排序算法，可能改变相同元素的相对顺序。
  • 实现复杂度相对较高，理解和编程上比简单排序算法复杂。

适用场景​

堆排序适用于以下场景：

  • 数据量较大的排序。
  • 需要一个高效且空间复杂度低的排序算法时。
  • 不需要稳定排序的场景。

总结​

堆排序是一种高效的排序算法，通过构建最大堆，将最大元素逐个移到数组末尾并重新堆化剩余元素。尽管其实现复杂度较高且不稳定，但在处理大规模数据时表现优异，是一种时间复杂度稳定且空间复杂度低的排序算法。