排序算法 -堆排序

文章目录

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;// 如果右子节点存在且大于largestif (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)$ 。