急急！请问，序列 {29.70.54.32..78}使用最小堆的堆排序方法排序每一趟的排序结果
发布网友
发布时间：2022-04-23 03:17
共1个回答
热心网友
时间：2023-10-13 02:47
(1) 序列 {29, 70, 54, 32, , 78} 有6个数据,先建立"完全二叉树",
[1]=29,[2]=70,[3]=54,[4]=32,[5]=,[6]=78
29 [1]
/ \ / \
70 54 [2] [3]
/ \ / / \ /
32 78 [4] [5] [6]
完全二叉树 对应的顺序号
(2) "完全二叉树"有6个结点,也就是N=6,要建立"初始堆",就要从第N/2号结点到
第1号结点进行调整,也就是按顺序,调整第3号结点,第2号结点,第1号结点,
这3个结点都有分支.
第3号结点,[3]=54,它比左分支78小,所以不用互换,二叉树保持不变,
此时,序列是 29 70 54 32 78
29
/ \
70 54
/ \ /
32 78
(3) 第2号结点,[2]=70,它比左分支32大,比右分支大,而左分支32较小,互换32和70,
此时,序列是 29 32 54 70 78
29
/ \
32 54
/ \ /
70 78
(4) 第1号结点,[1]=29,它比左分支32小,比右分支54小,所以,不用互换,
此时,序列是 29 32 54 70 78
29
/ \
32 54
/ \ /
70 78
按照"最小堆"的规则,依次完成前3个结点的调整,得到"初始堆":
29 32 54 70 78
接下来,就是正式的排序过程,因为使用最小堆的堆排序方法,
所以,最后排序的结果是从大到小.
(5) 根节点29与最后一个结点78互换,78成为根结点,然后,78与32,依次互换,
这一次的调整,得到最小值29.
此时,序列是 32 54 70 78 29
78 32 32
/ \ / \ / \
32 54 78 54 54
/ \ / \ / \
70 29 70 29 70 78 29
(6) 根结点32与最后一个结点78互换,78成为根结点,然后,78与54互换,
这一次的调整,得到最小值32.
此时,序列是 54 78 70 32 29
78 54
/ \ / \
54 78
/ /
70 32 29 70 32 29
(7) 根结点54与最后一个结点70互换,70成为根结点,70与互换,
这一次的调整,得到最小值54.
此时,序列是 70 78 54 32 29
70
/ \ / \
78 70 78
54 32 29 54 32 29
(8) 根结点与最后一个结点78互换,78成为根结点,78与70互换,
这一次的调整,得到最小值.
此时,序列是 70 78 54 32 29
78 70
/ /
70 78
54 32 29 54 32 29
(9) 根结点70与最后一个结点78互换,最后得到一个完全有序的序列(从大到小):
78 70 54 32 29
图示:
78
70
54 32 29
//C语言测试程序
//使用最小堆的堆排序方法
#include <stdio.h>
char fileName[]="d:\\heapSort.txt";
int printIndex;
int writeindex;
void printData(int *a,int n) //屏幕打印数据
{
int i;
printf("(%d) ",printIndex);
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
printIndex++;
}
void writeFile(int *a,int n) //排序过程写入文件
{
FILE *fp;
int i;
fp=fopen(fileName,"a"); //"a"以附加的方式打开只写文件
if(fp == NULL)
{
printf("\n打开文件 %s 时出错.\n",fileName);
return;
}
fprintf(fp,"(%d) ",writeindex);
for(i=0;i<n;i++)
{
fprintf(fp,"%d ",a[i]);
}
fprintf(fp,"\n");
fclose(fp); //关闭文件
writeindex++;
}
//array是待调整的堆数组，i是待调整的数组元素的位置，nlength是数组的长度
//本函数功能是：根据数组array构建大根堆
void HeapAdjust(int array[],int i,int nLength)
{
int nChild;
int nTemp;
for(;2*i+1<nLength;i=nChild)
{
//子结点的位置=2*（父结点位置）+1
nChild=2*i+1;
//得到子结点中较小的结点
if(nChild < nLength-1 && array[nChild+1] < array[nChild])
{
++nChild;
}
//如果较小的子结点小于父结点那么把较小的子结点往上移动，替换它的父结点
if(array[i] > array[nChild])
{
nTemp=array[i];
array[i]=array[nChild];
array[nChild]=nTemp;
}
else break; //否则退出循环
}
}
//堆排序算法
void HeapSort(int array[],int length)
{
int i;
//调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
//length/2-1是最后一个非叶节点.
for(i=length/2-1;i>=0;--i)
{
HeapAdjust(array,i,length);
printData(array,length);
writeFile(array,length);
}
printIndex=1;
writeindex=1;
//从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for(i=length-1;i>0;--i)
{
//把第一个元素和当前的最后一个元素交换，
//保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
array[i]=array[0]^array[i];
array[0]=array[0]^array[i];
array[i]=array[0]^array[i];
//不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
HeapAdjust(array,0,i);
printData(array,length);
writeFile(array,length);
}
}
int main()
{
int num[]={29,70,54,32,,78};
int i;
int len;
len=sizeof(num)/sizeof(int);
printIndex=0;
writeindex=0;
printData(num,len);
writeFile(num,len);
HeapSort(num,len);
printf("最后结果:\n");
for(i=0;i<len;i++)
{
printf("%d ",num[i]);
}
printf("\n排序的过程保存在文件 %s\n",fileName);
return 0;
}
