堆排序（HeapSort）详解

本文主要是介绍堆排序（HeapSort）详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

堆排序

一，思考
二，算法步骤
- 2.1向上调整建堆
- 2.2关键思路
- 2.3完整代码
- 补充：向下调整建堆
三，总结

一，思考

我们上一篇文章讲到了堆的基本实现，那么堆排序我们就先借助堆的结构来实现。

void HeapSort(HP* hp)
{int a[] = { 65,100,70,32,50,60 };HeapInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapPrint(&hp);HeapDestroy(&hp);}

我们先创建堆，然后依次取堆顶的数据，虽然这种打印出来是正确的顺序，但是本质上我们只是依次取了数据，数组a的数据根本没有变。所以我们要对这个代码做出一点改变。

void HeapSort(int*a,int n)
{HP hp;HeapInit(&hp);for (int i = 0; i < n; i++){HeapPush(&hp, a[i]);}int i = 0;while (!HeapEmpty(&hp)){/*printf("%d ", HeapTop(&hp));*/a[i++] = HeapTop(&hp);HeapPop(&hp);}HeapPrint(&hp);HeapDestroy(&hp);}

我们在这个代码中加入a[i++] = HeapTop(&hp);这个就依次把a数组中的数据依次取代。但是这个代码依旧有缺陷。
我们刚刚提到我们是有了堆结构，才写出这个堆排序的，所以这个很大程度上他很麻烦，要有堆结构才能有堆排。所以我们就要想有没有什么写法不需要对结构就可以写出这个排序。

二，算法步骤

我们在写堆的时候提到了两种调整，一个是向上调整，一个是向下调整我们接下来真正的堆排序就要从他们入手。
***注意
既然是堆排序，那么我们就要先建堆。说到建堆我们这个又有一个需要考虑的问题，我们如果要排升序，我们应该建大堆还是小堆呢？我们正常思路就是排升序就建小堆，因为这样根就是最小的数可以直接取出。但是我们要考虑完全，取完了最小的数那么接下来呢？把剩下的数再排，让下一个数当根，这样又出现了一个问题就是，兄弟关系变成了父子，那么堆就被破坏了。所以这种方法是不可行的。排升序应该建大堆。
堆排序：升序建大堆；降序建小堆
（我们接下来都是以排升序为例）

2.1向上调整建堆

在这里插入图片描述
我们先选择用向上调整去建堆，我们先把70设为跟，然后尾插，在向上调整数的位置，用一个循环就可达到，也是非常的简单。

	for (int i = 0; i < n; i++){Adjustup(a,i);}

2.2关键思路

建完了堆我们就要开始排序了，
在这里插入图片描述

我们在堆的删除中用了，把根和最后一个位置交换，然后再向下调整。当然这里我们引用了这种方法，我们先交换根和最后一个数，这样最大的数我们就排好了，这里我们还设置了一个end，每牌好一个数，end就–去找次大的数。这样用循环控制，直到end<0我们的堆排就完成了。

2.3完整代码

void HeapSort(int* a, int n)
{//向上调整建堆for (int i = 0; i < n; i++){Adjustup(a,i);}int end = n - 1;while (end>0){Swap(&a[end], &a[0]);AdjustDown(a,end,0);end--;}
}

补充：向下调整建堆

上面的堆排已经没什么大问题了，但是他两种调整都用了，我们在写堆排的时候还是有些麻烦，所以有没有什么办法在简便一些呢？这里我们就用向下调整建堆
在这里插入图片描述
刚刚的向上调整建堆是从上到下，而向下调整则是从下到上，我们都知道向下调整的前提是：左右子树都是堆
那么我们就从这一点入手，我们找到第一个非叶子节点，叶子节点没有排的必要，所以我们从非叶子节点出发，他的左右孩子都是堆，然后我们就可以向下调整，用循环控制，当然这里我们要注意，非叶子节点的下标，最后一个值的下标是n-1,那么他的父亲（第一个非叶子节点）就是[(n-1)-1]/2，然后再–就找到了上一个节点。

void HeapSort(int* a, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i > 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end>0){Swap(&a[end], &a[0]);AdjustDown(a,end,0);end--;}
}