10.4选择排序简单选择排序堆排序一、简单选择排序假设排序过程中，待排记录序列的状态为：有序序列R[1..i-1
]无序序列R[i..n]第i趟简单选择排序从中选出关键字最小的记录有序序列R[1..i]无序序列R[i+
1..n]简单选择排序的算法描述如下：voidSelectSort(Sqlist&L){for(i=1
;iSelectMinKey(L,i);//在R[i..n]中选择关键
字最小的记录if(i!=j)L.r[i]←→L.r[j];//与第
i个记录交换Sqlist的定义见P264时间性能分析对n个记录进行简单选择排序，所需进行的关键字间的比较次
数总计为：移动记录的次数，最小值为0,最大值为3(n-1)。二、堆排序堆是满足下列性质的数列{k1,k2,…
，kn}：或堆的定义:{12,36,27,65,40,34,98,81,73,55,49}例如:是小
顶堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小顶堆)(大顶堆)(
i=1,2,3……,n/2)KiK2iK2i+1kik2ik2i+1若将该数列视作完全二叉树，则k2
i是ki的左孩子,k2i+1是ki的右孩子1236276549817355403498例如:
是堆14不{12,36,27,65,40,34,98,81,73,55,49}14堆排序即是利用堆
的特性对记录序列进行排序的一种排序方法。例如：建大顶堆{98,81,49,73,36,27,40,55,6
4,12}{12,81,49,73,36,27,40,55,64,98}交换98和12重新调
整为大顶堆{81,73,49,64,36,27,40,55,12,98}{40,55,49,73
,12,27,98,81,64,36}经过筛选升序排序如何“建堆”？两个问题:如何“筛选”？定义堆类型为
:typedefSqListHeapType;//堆采用顺序表表示
之所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。堆堆筛选98814
973556412362740例如:是大顶堆12但在98和12进行互换之后，并将98从树中去掉，剩下
的完全二叉树就不是堆了，因此，需要对它进行“筛选”。981281736412比较比较建堆是一个从下往上进行反复
“筛选”的过程。筛选从最后一个非叶子(即第n/2个元素)开始。40554973816436122798例如:
排序之前的关键字序列为123681734998817355现在，左/右子树都已经调整为堆，最后只要调
整根结点，使整个二叉树是个“堆”即可。98494064361227堆排序(升序)算法:1.将完全二叉树建成一
个大顶堆2.将堆顶元素(根)与二叉树的最后一个元素交换。3.去掉完全二叉树的最后一个元素。4.将剩余的
完全二叉树再重新调整成大顶堆。5.重复第2步至第4步（n-1次）小小（降序）习题：已知：一组无序
记录，其关键字为：{503，87，512，61，908，170，897，275，653，462}，用堆排序方法对其升序排序，画出
排序过程示意图。voidHeapAdjust(HeapType&H,ints,intm){
//本函数自上而下调整H.r[s]的关键字，//使H.r[s..m]也成为一个大顶堆
}//HeapAdjustrc=H.r[s];//暂存H.r[s]for(j=2s;j<=m
;j=2){if(j!LT(rc.key,H.r[j].key))break;H.r[s]=H.r[j];s=j;
}H.r[s]=rc;//将调整前的堆顶记录插入到s位置voidHeapSort(
HeapType&H){//对顺序表H进行堆排序
}//HeapSortfor(i=H.length/2;i>0;--i)HeapAdju
st(H.r,i,H.length);//建大顶堆for(i=H.length;i>1;--i)
{H.r[1]←→H.r[i];//将
堆顶记录和当前未经排序子序列//H.r[1.
.i]中最后一个记录相互交换HeapAdjust(H.r,1,i-1);//将H.r[1..i-1]重新调整为大
顶堆}堆排序的时间复杂度分析：1.对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；3.调整
“堆顶”n-1次，总共进行的关键字比较的次数不超过2(?log2(n-1)?+?log2(n-2)?+…+
log22)<2n(?log2n?)因此，堆排序的时间复杂度为O(nlogn)。2.对n个关键字，建成深度为h(=?log2n?+1)的堆，所需进行的关键字比较的次数至多4n；作业：已知无序序列｛61，20，19，37，45，25，42｝给出采用堆排序法对该序列做降序排序的每一趟的结果。（画出排序过程示意图） |
|
