数据结构及应用算法教程（修订版） 第3章 排序.ppt

《数据结构及应用算法教程（修订版） 第3章 排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章排序3.1概述3.2简单排序3.3先进排序3.4基数排序3.5各种排序方法的综合比较3.1概述排序的定义排序的稳定性排序的分类内部排序方法的分类1、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列:52,49,80,36,14,58,61,23,97,75调整为:14,23,36,49,52,58,61,75,80,97排序的确切定义:假设含n个记录的序列为{R1,R2,…，Rn},其相应的关键字序列为{K1,K2,…，Kn}对上述的记录序列排序就是确定序号1,2,…,n的一种排列

2、,p1,p2,…,pn,使其相应的关键字满足如下的非递减的关系：Kp1≤Kp2≤…≤Kpn也就是使上述的记录序列成为一个按关键字有序的序列{Rp1,Rp2,…，Rpn}的操作称作排序。2、排序的稳定性当待排序记录中的各关键字ki(i=1,2,…,n)都不相同时，排序结果惟一；当待排序记录中存在两个或两个以上关键字相等的记录时，排序结果不惟一。稳定性：假设关键字ki=kj(n≥i≥1,1≤j≤n,i≠j),并且在排序前记录ri领先rj,若在排序后ri仍领先rj，则称排序是稳定的；否则，称排序是不稳定的。3、排序的分类：内部排序和外部排序若整个排序过程不需要访问外存便

3、能完成，则称此类排序问题为内部排序；反之,若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。4、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。通常在排序的过程中，参与排序的记录序列中可划分为两个区域：1.有序序列区：其中的记录按关键字非递减有序。2.无序序列区一趟排序：使有序序列区中记录的数目增加一个或几个的操作，称为一趟排序。基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：简单排序先进排序基数排序经过一趟排序有序序列区无序序列区有序序列区无序序列区待排记录的数据类型定义如下:

4、constMAXSIZE=20;//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置intlength;//顺序表长度}SqList;//顺序表类型3.2简单排序选择排序插入排序起泡排序希尔排序各种排序方法的学习要点：掌握基本思想举例说明排序过程书写算法稳定性的判断时间复杂度的分析3.2.1选择排序1、基本思想：

5、从无序序列区R[i]到R[n]的n-i+1个记录中选出关键字最小的记录R[j]和R[i]交换，从而使有序序列区从R[1]到R[i-1]扩大至R[1]到R[i]。2、举例：一组关键字(491,38,65,492,76,13,27,52)进行选择排序。初始()i=1(13),38,65,492,76,491,27,52i=2(13,27),65,492,76,491,38,52i=3(13,27,38),492,76,491,65,52i=4(13,27,38,492),76,491,65,52i=5(13,27,38,492,491)76,65,52i=6(13,2

6、7,38,492,491,52),65,76i=7(13,27,38,492,491,52,65),763、一趟选择排序算法（算法3.1）voidSelectPass(SqList&L,inti){//已知L.r[1..i-1]中记录按关键字非递减有序，本算法实现//第i趟选择排序，即在L.r[i..n]的记录中选出关键字最小的//记录L.r[j]和L.r[i]交换RcdTypeW；j=i；//j指示关键字最小记录的位置，初值设为ifor(k=i+1;k<=L.length;k++)if(L.r[k].key

7、记录位置if(i!=j){W=L.r[j]；L.r[j]=L.r[i]；L.r[i]=W；}//最后互换记录R[j]和R[i]}//SelectPass算法3.2voidSelectSort(SqList&L){//对顺序表L作简单选择排序。RcdTypeW；for(i=1;i

8、.r[i]