当前位置：首页 > article >正文

排序算法 -堆排序

article 2024/12/27 8:37:26

文章目录

1. 堆排序（Heap Sort）
- 1.1 简介
- 1.2 堆排序的步骤
- 1.3 堆排序C语言实现
- 1.4 时间复杂度
- 1.5 空间复杂度

1. 堆排序（Heap Sort）

1.1 简介

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

1.2 堆排序的步骤

构建最大堆：
- 将数组视为完全二叉树，从最后一个非叶子节点开始，自底向上进行堆化（heapify）操作，使得每个子树都满足最大堆的性质。
排序过程：
- 将堆顶元素（最大值）与数组的最后一个元素交换，此时数组的最后一个元素就是最大值。
- 将堆的大小减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 时间复杂度

构建最大堆（或最小堆）：
- 对于一个包含 $n$ 个元素的数组，构建最大堆的过程需要遍历数组中的每个非叶子节点，并对每个节点执行 heapify 操作。
- 在最坏情况下，每个 heapify 操作需要 $O(\log n)$ 的时间（因为堆是一棵完全二叉树，其高度为 $\log n$ ）。
- 由于数组中有 $O (n)$ 个节点，且每个节点最多被 heapify 一次（在构建堆的过程中），所以构建堆的时间复杂度为 $\log n)$ 。
排序过程：
- 在排序过程中，我们反复执行以下操作：
  - 将堆顶元素（最大值或最小值）与数组的最后一个元素交换。
  - 减少堆的有效大小（即忽略已经排好序的部分）。
  - 对新的堆顶元素执行 heapify 操作，以维护堆的性质。
- 这个过程需要执行 $n - 1$ 次（因为我们需要将 $n - 1$ 个元素移动到它们最终的位置上），每次 heapify 操作的时间复杂度为 $O(\log n)$ 。
- 因此，排序过程的时间复杂度为 $\log n)$ ，这可以简化为 $\log n)$ 。