数据结构教程第三十六课选择排序，归并排序

文章作者 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的解决方法：