堆排序(Heapsort)是一种在时间复杂度上达到了最优的基于比较的排序算法。堆排序算法是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。
堆排序的基本思想是:
- 首先将待排序的序列构造成一个大顶堆(或小顶堆)。
- 此时,整个序列的最大值(或最小值)就是堆顶的根节点。
- 将其与末尾元素进行交换,此时末尾就为最大值(或最小值)。
- 然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值(或次大值)。
- 如此反复执行,便能得到一个有序序列了。
堆排序的时间复杂度是O(n log n)。文章来源:https://uudwc.com/A/qR3kJ
#include <stdio.h>
// 将以k为根的子树调整为最大堆
void heapify(int arr[], int n, int k) {
int largest = k; // 初始化根节点最大
int left = 2 * k + 1; // 左子节点
int right = 2 * k + 2; // 右子节点
// 如果左子节点比根节点大,则更新最大节点
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点比最大节点大,则更新最大节点
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大节点不是根节点,则交换根节点和最大节点,并继续调整子树
if (largest != k) {
int temp = arr[k];
arr[k] = arr[largest];
arr[largest] = temp;
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);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
heapSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
该代码中,heapify
函数将以k
为根的子树调整为最大堆,heapSort
函数则先构建最大堆,然后从堆顶开始取出元素并重新调整堆,最终得到排序后的数组。文章来源地址https://uudwc.com/A/qR3kJ