《最新《数据结构讲义》排序》由会员分享，可在线阅读，更多相关《最新《数据结构讲义》排序（6页珍藏版）》请在金锄头文库上搜索。
1、1 .掌握排序的基本概念。2.掌握内部排序中的插入排序方法。教学重点：内部排序中的插入排序方法教学难点：内部排序中的插入排序方法 授课内容排序的基本概念排序（sorting）又称分类，是计算机程序设计中的一个重要操作，即把一批任意序列的数 据元素（或记录），重新排列成一个按关键字有序的序列。通过排序可以提高数据表的直观性， 并为以后查询提供方便，提高查找效率。排序的应用领域十分惯犯，因此在很多领域有广泛应 用。电话簿、病历、情报、档案、图书馆和各种词典的目录表（或目录卡）等都离不开排序。为了进一步理解排序，在此给出一个比较确切的排序定义：假设含d个记录的序列为R1 ,R2 ,Rd其相应的关键字
2、序列为K1 ,K2 ,K需确定1，2,d的一种排列p1,p2,pd,使其响应的关键字满足下列的非递减（或非递 增）关系：Kp1WKp2WWKpd即使式（一.1 ）的序列成为一个按关键字有序的序列Rp2,，叩这样一种操作成为排序。在待排序的记录中若关键字值是唯一的(即Ki是主关键字)，则任何一组记录经排序后得 到的结果是唯一的；在待排序的记录中若有两个或两个以上关键字值相同的记录，则排序的结 果不唯一。在用某种方法排序之后，这些关键字相同的记录相对先后次序不变，即当 Ki=Kj(1WiWd,1WjWd,iN)且ij,若在排序后的序列中Ri仍领先于Rj，则称所用的排序方 法是稳定的；反之，若可能使
3、排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。排序的方法有多种，若按排序过程中所涉及的存储器不用，可奖排序方法分为两大类：一类 是内部排序，即将待排记录调入计算机的内存中进行的排序过程，其排序方法包括插入排序、 交换排序、选择排序、归并排序和基数排序等。另一类是外部排序，即待排序记录的数量很大， 以致内存不能依次容纳全部记录，在排序过程中尚需对外存访问的排序过程。数据结构定义为：#define MAXSIZE 30typedef structint key;dataType oth;RcdType;RcdType rMAXSIZE+1;2内部排序21插入排序1 .直接插入排序直接
4、插入排序(straight insertion sort)是一种最简单的插入排序方法。它的基本操作 是将一个记录插入到一个长度为n (假设)的有序表中，使之仍保持有序，从而得到一个新的长 度为n+1的有序表。如同玩扑克牌的人抓牌一样，将抓到的牌插入到手重已排好的牌的一个适 当位子上。算法思路：设有彝族关键字%,、,Kn；认为Kl就是一个有序序列；让K2插入上述表 长为1的有序序列中，使之成为一个表长为2的有序序列；让K3插入上述表长为2的有序序列 中，使之成为一个表长为3的有序序列；依此类推，最后让Kn插入到表厂为n-1的有序序列中， 得到一个表长为n的有序序列。初始关的：40 2Q 45 1
5、5 70 3340 45 50J40 45 * 70Ji=715 20 33 43 45 50 70Jvoid InsertSort(RcdType r ,int n)for(i=2;i=n;i+)r0=ri;j=i-1;while(r0.keyrj.key)rj+1=rj;j-;rj+1=r0;2,折半插入排序当用直接插入排序进行到某一趟比较时，对于ri.key来讲，前边i-1个记录已经按关键 字排序。此时可不用直接插入排序的方法，而改用折半插入排序。算法思路：与直接插入排序相近，只是在进行比较时，ri.key首先与已排好序的中间记录进行比较，然后根据比较结果来确定ri.key继续与中间记录
6、的前面记录比较，还是与中间记录的后面记录比较，找出应插入的位置，然后插入。算法如下：void BinSort(RcdType r ,int n )for (i=2;i=n;i+)r0=ri;low=1;high=i-1;while(low=high)mid=(low+high)/2;if(r0.key=low;j-) rj+1=rj;rlow=r0;3.希尔排序希尔排序(Shell sort)也称“缩小增量排序”。它的做法不是每次一个元素挨一个元素的 比较。而是先将整个待排序记录序列分割成为若干子序列分别进行直接插入排序，待整个序列 中的记录看承是一组，然后在各组内进行插入排序;接着取d2(d
7、2=1),即所有记录成为一个组为止。希尔排序对增量序列的选择没有严格规定，一般 选 d约为 n/2,d2 为 d1/2,d3 为 d2/2,，di=1。void ShellSort(RcdType r ,int n)d=n/2;while(d0)for (i=d+1;i=0&r0.keyrj.key)rj+d=rj;j=j-d; rj+d=r0;d=d/2;L初始关键字:&6 75 50 40 90 33 15 70755070趟排序结果一昭33 15 40 9D 75 50 701570751 5 33 50 43 B6 70 90 75三趟排序结果:15 33 4D 50 70 75 B6 90
