目录
前言
背景
排序策略
排序原则
如何建小堆数组
建堆策略1：向上调整
建堆策略2：向下调整
建成小堆之后
测试
具体堆源码
前言
在数据结构中我们学了堆的性质及其实现，而这里我们将讲解用堆来实现排序
背景
对给定数组进行堆排序，排成降序
排序策略
排序原则
如果是排升序那么则先将给定数组建立大堆 如果是排降序那么则先将给定数组建立小堆
注：这里排成降序，我们数组建立成一个数组小堆，对于大堆稍作修改就行了
如何建小堆数组
- 根位置和左右子位置下标关系：
leftchild=root*2 1; rightchild=root*2 2; (leftchild(rightchild)-1)/2=root;
我们依据下标关系，可以找到对应的根位置或者子位置并操作数据建立成堆
建堆策略1：向上调整
- 对每个数据进行向上调整直到符合小堆
- 当前位置数据和根位置数据比较，如果不符合小堆则交换，直到向上调整到符合小堆
- 这里我们可以从第二个数据开始调整，也可以从最后一个数据开始调整
- 图示过程：从尾部数据往前开始向上调整
建堆策略2：向下调整
- 对每个位置数据的根位置数据进行向下调整
- 根位置和数据较小的子位置比较，不符合大堆则交换，直到符合
- 然而对数据使用向下调整的前提是，根的左右子堆都符合大堆
- 所以我们从最后一个数据的根位置开始进行调整，直到堆顶数据调整完毕
- 图示过程：
建成小堆之后
- 我们都知道小堆堆顶的数据永远是当前堆中数据最小的
- 我们让堆顶的数据与堆尾数据进行交换（最小的数就排到了最后）
- 交换后将除现堆尾的数据看成一个堆
- 对交换后的堆顶数据进行向下调整（调整后又成小堆）
- 调整后的堆顶数据是当前堆中（包括排除在外的堆尾的最小数）次小的数
- 让该堆顶数据与堆倒数第二个数据交换
- 以此循环直到交换到堆的正数第二个数据，这个数组降序也就排序好了
- 过程示图：
- 参考代码：
//数据调整
void AdjustDown(HPDataType* a, int size, int parent)
{
int child = parent * 2 1;
while (child<size)
{
//找到数据小的儿子
if (child 1 < size && a[child 1] < a[child])
{
child ;
}
//将父节点与小子节点交换
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);//交换数据
parent = child;//调整下标位置
child = parent * 2 1;
}
else
{
break;//结束调整
}
}
}
// 对数组进行堆排序
void HeapSort(int* a, int n)
{
//排降序，建立小堆（小堆堆顶数据一定是最小的）
for (int i = (n - 1 - 1) / 2; i >= 0; i--)//建堆：从最后一个数据的父节点进行向下调整一直到最开始数据
{
AdjustDown(a, n,i);
}
//将堆顶数据放与末尾数据交换，再将除最小数据外的数组看成堆
//对当前顶数据调整，调整后当前堆的最小数据处在堆顶位置
//以此循环，每次最小的数据都放在当前堆的最后面，最终也就成了降序
for (int end = n - 1; end >= 0; end--)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
}
}测试
- 测试代码：
int main()
{
int a[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i)
{
printf("%d ", a[i]);
}
printf("n");
HeapSort(a, sizeof(a) / sizeof(a[0]));
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i)
{
printf("%d ", a[i]);
}
printf("n");
return 0;
}- 测试结果：
