目录
在数据结构中我们学了堆的性质及其实现,而这里我们将讲解用堆来实现排序
对给定数组进行堆排序,排成降序
如果是排升序那么则先将给定数组建立大堆 如果是排降序那么则先将给定数组建立小堆
注:这里排成降序,我们数组建立成一个数组小堆,对于大堆稍作修改就行了
leftchild=root*2+1; rightchild=root*2+2; (leftchild(rightchild)-1)/2=root;
我们依据下标关系,可以找到对应的根位置或者子位置并操作数据建立成堆
//数据调整
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;
}