排序算法 -堆排序

1. 堆排序（Heap Sort）

1.1 简介

堆是一种特殊的完全二叉树，分为最大堆（Max Heap）和最小堆（Min Heap）。在最大堆中，每个节点的值都大于或等于其子节点的值；在最小堆中，每个节点的值都小于或等于其子节点的值。堆排序通常使用最大堆来实现升序排序，本文使用最大堆。

1.2 堆排序的步骤

1. 构建最大堆：

   • 将数组视为完全二叉树，从最后一个非叶子节点开始，自底向上进行堆化（heapify）操作，使得每个子树都满足最大堆的性质。

2. 排序过程：

   • 将堆顶元素（最大值）与数组的最后一个元素交换，此时数组的最后一个元素就是最大值。
   • 将堆的大小减1（排除已排定的最大元素），然后重新对堆顶元素进行堆化，使其满足最大堆的性质。
   • 重复上述步骤，直到堆的大小为1，此时数组已完全排序。

1.3 堆排序C语言实现

#include <stdio.h>
 
// 堆化函数，用于维护最大堆的性质
void heapify(int arr[], int n, int i) {
    int largest = i;    // 初始化largest为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点
 
    // 如果左子节点存在且大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;
 
    // 如果右子节点存在且大于largest
    if (right < n && arr[right] > arr[largest])
        largest = right;
 
    // 如果largest不是根节点
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
 
        // 递归堆化受影响的子树
        heapify(arr, n, largest);
    }
}
 
// 堆排序函数
void heapSort(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--) {
        // 移动当前根到数组末尾
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
 
        // 调整堆
        heapify(arr, i, 0);
    }
}
 
// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
// 主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printf("未排序数组: \n");
    printArray(arr, n);
 
    heapSort(arr, n);
 
    printf("已排序数组: \n");
    printArray(arr, n);
    return 0;
}

1.4 时间复杂度

1. 构建最大堆（或最小堆）：

   • 对于一个包含 $n$ 个元素的数组，构建最大堆的过程需要遍历数组中的每个非叶子节点，并对每个节点执行 heapify 操作。
   • 在最坏情况下，每个 heapify 操作需要 $O(\log n)$ 的时间（因为堆是一棵完全二叉树，其高度为 $\log n$）。
   • 由于数组中有 $O(n)$ 个节点，且每个节点最多被 heapify 一次（在构建堆的过程中），所以构建堆的时间复杂度为 $O(n\log n)$。

2. 排序过程：

   • 在排序过程中，我们反复执行以下操作：
     • 将堆顶元素（最大值或最小值）与数组的最后一个元素交换。
     • 减少堆的有效大小（即忽略已经排好序的部分）。
     • 对新的堆顶元素执行 heapify 操作，以维护堆的性质。
   • 这个过程需要执行 $n-1$ 次（因为我们需要将 $n-1$ 个元素移动到它们最终的位置上），每次 heapify 操作的时间复杂度为 $O(\log n)$。
   • 因此，排序过程的时间复杂度为 $O((n-1)\log n)$，这可以简化为 $O(n\log n)$。

综上所述，堆排序的总时间复杂度为 $O(n\log n)$。

1.5 空间复杂度

• 堆排序是原地排序算法（in-place sorting algorithm），它只需要一个常数级别的额外空间来存储临时变量（例如，用于交换元素的变量）。
• 与归并排序等需要额外数组空间的排序算法相比，堆排序的空间复杂度非常低。
• 因此，堆排序的空间复杂度为 $O(1)$（不考虑输入数组本身所占用的空间）。

总结：

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(1)$（原地排序）