数据结构与算法-堆排序（详细版）
数据结构与算法-堆排序（详细版）
堆排序是一种基于二叉堆的数据结构的排序算法，具有较高的效率和实用性。本文将详细介绍堆排序的实现过程，包括将数组转换为堆、升序和降序排序的具体步骤，以及更优的建堆方法。通过本文的学习，你将能够掌握堆排序的核心原理和实现技巧。
一、如何将一个数组转换为堆
1. 准备一个数组：
int main()
{
int a[] = { 4,6,2,1,5,8,2,9};
//HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
printf("%d", a[i]);
}
return 0;
}
2. 数组的逻辑结构建堆思路
当前的数组是无序的，我们要如何将这个数组形成一个堆呢？我们想到如果将数组中的数，类似于堆的插入时一个一个插入是不是就能解决了呢？但我们其实不必再创造一个新数组去放逻辑结构上是堆的数。直接在原来的数组上做修改就可以了。由于我们要将后面的数与第一个数进行比较，因此我们用向上调整来实现。将一个已经存在的数组中的数进行堆排序，与堆的插入的区别在于，不用再开辟空间。
二、堆排序-实现升序排序（要求打印出来的一串数字是递增排列）
这里我们可以思考一下用小堆来排，还是大堆来排时间复杂度尽量小呢？我们需要知道，堆排序的应用是选数，那么在一个数组中我们将它形成大堆/小堆我们可以选出最大/最小的数。如果想要选出次大/次小的数呢？
1. 使用小堆:
思路：如果直接删除第一个数，下一个数不就是次小？但时间复杂度太大因此不能直接删除第一个数据，去取第二个数据。
2. 使用大堆：
a. 思路：利用堆的实现时的思路，要得到次小的数字，若不想将堆的排序打乱，先交换首尾。我们想要实现的是升序排序，这时最大元素已在堆尾。相当于尾部已排好，再将现在的根节点 "1" 进行向下调整，（选择出左右孩子中较大的与之交换，直到再没有比他大的孩子），此时次大的数据已在根节点。我们需要继续交换。堆尾已排好，我们将它视作外围数，而他又必须在数组中。那该如何实现呢？将数组的大小看做 -1，最后一个元素的下标 -1
3. 堆排序实现降序排序
建堆时使用建小堆
4. 完整代码
#include"MY_Heap.h"
#include<time.h>
#define _CRT_SECURE_NO_WARNINGS 1
void HeapSort(int* a, int n)
{
//建大堆
for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
Adjustdown(a, end, 0);
--end;
}
}
int main()
{
int a[] = { 4,6,2,1,5,8,2,9};
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
printf("%d", a[i]);
}
return 0;
}
三、更优的建堆（从倒数第一个非叶子，也就是最后一个节点的父亲节点开始向下调整）
优势：效率更高
1.思路
如果左右子树不是小堆呢？最后一个叶子节点一定是最小的数，因此我们从他的父节点开始调整将每一个子树都想像下调整成一个小堆，最后就可以得到新的小堆。时间复杂度：O(N)
2. 时间复杂度的证明：
a. 向下调整时间复杂度：（O(N)）
b. 向上调整时间复杂度：（约等于O(N*logN),但小于）
c.选数时间复杂度: （O(N*logN））
四、更优建堆完整代码
#include"MY_Heap.h"
void HeapSort(int* a, int n)
{
//建大堆
//for (int i = 1; i < n; i++)
//{
// AdjustUp(a, i);
//}
//向下调整建堆
for (int i = (n - 2) / 2; i > 00; --i)
{
Adjustdown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
Adjustdown(a, end, 0);
--end;
}
}
int main()
{
int a[] = { 4,6,2,1,5,8,2,9};
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
printf("%d", a[i]);
}
return 0;
}
本文详细介绍了堆排序算法的实现过程，包括将数组转换为堆、升序和降序排序的具体步骤，以及更优的建堆方法。通过本文的学习，你将能够掌握堆排序的核心原理和实现技巧。