数据结构考研分类复习真题 第十章 答案[39]

() 堆排序是对树型选择排序的改进克服了树型选择排序的缺点其定义在前面已多次谈到请参见上面四应用题的题和题()筛选是堆排序的基础算法由于堆可以看作具有n个结点的完全二叉树建堆过程是从待排序序列第一个非终端结点ën/û开始直到根结点进行筛选的过程堆建成后即可选得一个关键字最大或最小的记录然后堆顶元素与序列中最后一个元素交换再将序列中前n记录重新调整为堆可选得一个关键字次大或次小的记录依次类推则可得到元素的有序序列

() void Sift(RecType R[]int iint m)

{ //假设R[i+m]中各元素满足堆的定义本算法调整R[i]使序列R[im]中各元素满足堆的性质

R[]=R[i];

for(j=*i; j<=m; j*=)

{ if(j<m && R[j]key<R[j+l]key) j++; //建大根堆

if(R[]key<R[j]key) { R[i]=R[j]; i=j;} else break;

}//for

R[i]=R[];

}//Sift

void HeapSort(RecType R[]int n)

{ //对记录序列R[n]进行堆排序

for(i=n/;i>;i) Sift(Rin);

for(i=n;i>;i){ R[]<>R[i]; Sift(Ri);}//for

}//HeapSort

()堆排序的时间主要由建堆和筛选两部分时间开销构成对深度为h的堆筛选所需进行的关键字比较的次数至多为(h－)对n个关键字建成深度为h(=ëlognû+)的堆所需进行的关键字比较的次数至多C (n)它满足下式

调整堆顶n次总共进行的关键字比较的次数不超过因此堆排序的时间复杂度为O(nlogn)

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []