一.堆排序的概念
1.堆的思想
堆排序是一种常见的排序算法。它的基本思想是:
- 将待排序序列构建成一个大顶堆。大顶堆的特点是根节点的值大于或等于其左右子节点的值。
- 交换根节点(即当前最大值)与末尾元素。
- 减小堆的规模，重新调整结构，使其满足堆定义，然后再次交换根节点与当前末尾元素。
- 反复执行步骤2和步骤3，直到整个序列有序。
2.堆的实现步骤
具体实现步骤如下:
- 建立大顶堆:从最后一个非叶子节点开始调整，向上直到根节点。
- 交换堆顶元素(即当前最大值)与末尾元素,并减小堆的规模。
- 重新调整堆,使其满足堆定义。
- 重复步骤2和步骤3,直到整个序列有序。
堆排序的时间复杂度为O(nlogn)。空间复杂度为O(1),因为它在原数组上进行排序,不需要额外的内存空间。
堆排序的优势是能够在一个数组上就地完成排序,不需要额外的空间。缺点是对于小规模的数据,不如简单的插入排序和冒泡排序快。
3.堆的优点
优点:
- 时间复杂度为O(nlogn),是比较高效的排序算法之一。
- 在原数组上进行排序,不需要额外的内存空间,即空间复杂度为O(1)。
- 相比于其他基于比较的排序算法,如快速排序和归并排序,堆排序能够避免最坏情况下的性能下降。
- 堆排序算法的关键操作是堆的构建和堆的调整,可以利用堆这种数据结构的性质来快速完成排序。
- 堆排序算法的实现相对简单,容易编码实现。
4.堆的缺点
缺点:
- 对于小规模的数据,堆排序并不一定是最优选择,因为相比于简单的插入排序和冒泡排序,堆排序有较大的常数时间因子。
- 堆排序算法不是原地排序,需要利用原始数组的空间来存储中间结果。
- 在某些情况下,堆排序的性能可能不如其他算法,如快速排序和归并排序。这取决于输入数据的特点。
- 堆排序算法需要利用堆这种特殊的数据结构,对程序员的要求相对较高,实现起来也相对复杂一些。
二.堆排序的功能
堆排序的主要功能是对一个给定的数组进行升序或降序排序。具体来说,堆排序有以下几个主要功能:
1.构建大顶堆或小顶堆
- 堆排序算法首先需要将输入数组构建成一个大顶堆或小顶堆。
- 大顶堆的根节点是数组中的最大值,左右子节点都小于根节点。
- 小顶堆的根节点是数组中的最小值,左右子节点都大于根节点。
- 构建堆的过程使用"heapify"操作,从最后一个非叶子节点开始,逐级向上调整节点位置,直到根节点满足堆的性质。
- 这一步保证了数组中的元素满足堆的特性,为后续的排序奠定基础。
2.排序
- 在构建好堆之后,堆排序会进行反复的交换和调整操作。
- 首先将堆顶元素(即最大值或最小值)与堆的最后一个元素交换位置。
- 然后对新的根节点进行调整,使其满足堆的性质,成为一个新的有效堆。
- 通过不断重复这样的交换和调整过程,可以将最大值或最小值逐步放置到数组的后部,达到排序的目的。
- 这一步通过不断"弹出"堆顶元素并调整堆,最终实现了整个数组的排序。
3.支持原位排序
- 堆排序是一种原地排序算法,不需要额外的内存空间来辅助排序。
- 算法直接在原数组上进行操作,交换和调整元素位置,不需要申请新的数组空间。
- 这使得堆排序的空间复杂度非常低,仅需O(1)的额外空间开销。
- 原地排序的特性使得堆排序可以高效地处理大规模数据,不会受到内存限制的影响。
4.时间复杂度优秀
- 堆排序的时间复杂度为O(nlogn),其中n是输入数组的大小。
- 这是一个非常优秀的时间复杂度,使堆排序成为高效的通用排序算法之一。
- 无论数据规模大小,堆排序的时间复杂度都保持稳定,不会随数据规模的增加而急剧增长。
5.适用于大规模数据
- 由于时间复杂度优秀,堆排序特别适用于排序大规模数据集。
- 相比于一些时间复杂度为O(n^2)的排序算法,堆排序可以更高效地处理海量数据。
- 这使得堆排序在处理大型数据库、大文件排序等场景下具有很强的优势和应用价值。
三.堆排序的代码实现
1.构建大顶堆
heapify(arr, n, i)
函数用于构建大顶堆。它从最后一个非叶子节点开始,向上调整整个堆。
heapify(int arr[], int n, int i)函数:- 该函数用于调整以i为根节点的子树,使其满足大顶堆的性质。- 首先找到根节点、左子节点和右子节点中的最大值的下标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--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
2.堆排序的算法
heap_sort(arr, n)
函数实现了堆排序的算法。它首先构建大顶堆,然后反复交换堆顶元素和末尾元素,并重新调整堆。
heap_sort(int arr[], int n)函数:- 该函数实现了堆排序的主要逻辑。- 首先从最后一个非叶子节点开始,逐个调用heapify函数,构建一个大顶堆。- 然后进行交换和调整的循环: - 将堆顶元素(即最大值)与数组的最后一个元素交换。- 对新的根节点调用heapify函数,以维护堆的性质。- 重复这个过程,直到整个数组有序。
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) {
// 交换根节点和最大值
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 递归调整子树
heapify(arr, n, largest);
}
}
3.列举例子
main()函数:- 在main函数中,首先定义了一个待排序的数组data。- 然后调用heap_sort函数对数组进行排序。- 最后打印排序后的数组。
int main() {
int data[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(data) / sizeof(data[0]);
heap_sort(data, n);
printf("Sorted array is \n");
for (int i = 0; i < n; i++)
printf("%d ", data[i]);
printf("\n");
return 0;
}
四.堆排序的源码呈现
#include <stdio.h>
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) {
// 交换根节点和最大值
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 递归调整子树
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--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int data[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(data) / sizeof(data[0]);
heap_sort(data, n);
printf("Sorted array is \n");
for (int i = 0; i < n; i++)
printf("%d ", data[i]);
printf("\n");
return 0;
}
本文转载自: https://blog.csdn.net/z6665454/article/details/139031519
版权归原作者 晚安，cheems 所有， 如有侵权，请联系我们删除。
版权归原作者 晚安，cheems 所有， 如有侵权，请联系我们删除。