strucd10z.ppt

数据结构
吴润秀
南昌工程学院
概述 插入排序 快速排序 选择排序 归并排序 基数排序 各种内部排序的比较
目录
第十章内部排序
排序:将一组杂乱无章的数据按一定的规律顺次排列起来。
例如:将下列关键字序列
52, 49, 80, 36, 14, 58, 61, 23, 97, 75
调整为
14, 23, 36, 49, 52, 58, 61 ,75, 80, 97
数据表(datalist): 它是待排序数据对象的有限集合。
关键码(key): 通常数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区
概述
分对象,作为排序依据。该域即为关键码。每个数据表用哪个属性域作为关键码,要视具体的应用需要而定。即使是同一个表,在解决不同问题的场合也可能取不同的域做关键码。
主关键码: 如果在数据表中各个对象的关键码互不相同,这种关键码即主关键码。按照主关键码进行排序,排序的结果是唯一的。
排序算法的稳定性: 如果在对象序列中有两个对象r[i]和r[j],它们的关键码 k[i] == k[j],且在排序之前,对象r[i]排在r[j]前面。如果在排序之后,对象r[i]仍在对象r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。
内排序与外排序: 内排序是指在排序期间数据对象全部存放在内存的排序;外排序是指在排序期间全部对象个数太多,不能同时存放在内存,必须根据排序过程的要求,不断在内、外存之间移动的排序。
排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。各节给出算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象关键码序列初始排列及对象个数影响较大的,需要按最好情况和最坏情况进行估算。
静态排序: 排序的过程是对数据对象本身进行物理地重排,经过比较和判断,将对象移到合适的位置。这时,数据对象一般都存放在一个顺序的表中。
动态排序: 给每个对象增加一个链接指针,在排序的过程中不移动对象或传送数据,仅通过修改链接指针来改变对象之间的逻辑顺序,从而达到排序的目的。
算法执行时所需的附加存储: 评价算法好坏的另一标准。
静态排序过程中所用到的数据表类定义,体现了抽象数据类型的思想。
内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中,参与排序的记录序列中存在两个区域:有序区和无序区。
使有序区中记录的数目增加一个或几个的操作称为一趟排序。
逐步扩大记录有序序列长度的方法大致有下列几类:
插入类将无序子序列中的一个或几个记录“插入”到有序序列中,从而增加记录的有序子序列的长度;
: 从记录的无序子序列中“选择”关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度;
:通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度;
4. 归并类: 通过“归并”两个或两个以上的记录有序子序列,逐步增加记录有序序列的长度;
5. 其它方法
假设在排序过程中,记录序列R[1..n]的状态为:
显然,完成这个“插入”需分三步进行:
[i]的插入位置j+1;
[j+1..i-1]中的记录后移一个位置;
[i]复制到R[j+1]的位置上。
则一趟直接插入排序的基本思想为:将记录R[i]插入到有序子序列R[1..i-1]中,使记录的有序序列从R[1..i-1]变为R[1..i]。
插入排序(Insert Sorting)
注意直接插入排序算法的三个要点:
[i-1]起向前进行顺序查找,监视哨设置在R[0];
R[0] = R[i]; // 设置“哨兵”
for (j=i-1; R[0].key<R[j].key; --j);
// 从后往前找
return j+1; // 返回R[i]的插入位置为j+1
特点:利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。
一、直接插入排序