数据结构教程第三十六课选择排序,归并排序
文章作者 100test 发表时间 2007:03:10 18:28:18
来源 100Test.Com百考试题网
教学目的: 掌握选择排序,归并排序算法
教学重点: 选择排序之堆排序,归并排序算法
教学难点: 堆排序算法
授课内容:
一、选择排序
每一趟在n-i 1(i=1,2,...n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
二、简单选择排序
算法:
Smp_Selecpass(ListType &.r,int i)
{
k=i.
for(j=i 1.j
if (r[j].key
k=j.
if (k!=i)
{ t=r[i].r[i]=r[k].r[k]=t.}
}
Smp_Sort(ListType &.r)
{
for(i=1.i
Smp_Selecpass(r,i).
}
三、树形选择排序
又称锦标赛排序,首先对n个记录的关键字进行两两比较,然后在其中一半较小者之间再进行两两比较,如此重复,直到选出最小关键字的记录为止。
四、堆排序
只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。
什么是堆?n个元素的序列{k1,k2,...,kn}当且仅当满足下列关系时,称之为堆。关系一:ki<=k2i 关系二:ki<=k2i 1(i=1,2,...,n/2)
堆排序要解决两个问题:1、如何由一个无序序列建成一个堆?2、如何在输出堆顶元素之后,调整剩余元素成为一个新的堆?
问题2的解决方法:
![](http://www.bc-cn.net/Article/UploadFDL01/200411/20041112074219560.jpg)