《数据结构与算法》第9章 内部排序

第9章内部排序 概述 插入排序(直接插入、折半插入、表插入排序 希尔排序) 交换排序(起泡排序、快速排序) 选择排序(简单选择排序、树形选择排序、堆 排序) 0归并排序 基数排序 小结

概述 插入排序 （直接插入、折半插入、表插入排序、 希尔排序） 交换排序 （起泡排序、快速排序） 选择排序 （简单选择排序、树形选择排序、堆 排序） 归并排序 基数排序 小结 第9章 内部排序

概述 排序:将一组杂乱无章的数据排列成一个按关 键字有序的序列。 数据表( datalist):它是待排序数据对象的 有限集合 关键字(key):通常数据对象有多个属性域, 即多个数据成员组成,其中有一个属性域可用 来区分对象,作为排序依据。该域即为关键字 每个数据表用哪个属性域作为关键字,要视具 体的应用需要而定。即使是同一个表,在解决 不同问题的场合也可能取不同的域做关键字

概述 排序：将一组杂乱无章的数据排列成一个按关 键字有序的序列。 数据表(datalist): 它是待排序数据对象的 有限集合。 关键字(key): 通常数据对象有多个属性域， 即多个数据成员组成，其中有一个属性域可用 来区分对象，作为排序依据。该域即为关键字。 每个数据表用哪个属性域作为关键字，要视具 体的应用需要而定。即使是同一个表，在解决 不同问题的场合也可能取不同的域做关键字

主关键字:如果在数据表中各个对象的关键字互 不相同,这种关键字即主关键字。按照主关键字 进行排序,排序的结果是唯一的。 次关键字:数据表中有些对象的关键字可能相 同,这种关键字称为次关键字。按照次关键字 进行排序,排序的结果可能不唯一。 排序算法的稳定性:如果在对象序列中有两个对 象rt和r,它们的关键字kn=k,且在 排序之前,对象n排在rn前面。如果在排序 之后,对象r仍在对象r的前面,则称这个 排序方法是稳定的,否则称这个排序方法是不 稳定的

主关键字: 如果在数据表中各个对象的关键字互 不相同，这种关键字即主关键字。按照主关键字 进行排序，排序的结果是唯一的。 次关键字: 数据表中有些对象的关键字可能相 同，这种关键字称为次关键字。按照次关键字 进行排序，排序的结果可能不唯一。 排序算法的稳定性: 如果在对象序列中有两个对 象r[i]和r[j]，它们的关键字 k[i] == k[j]，且在 排序之前，对象r[i]排在r[j]前面。如果在排序 之后，对象r[i]仍在对象r[j]的前面，则称这个 排序方法是稳定的，否则称这个排序方法是不 稳定的

内排序与外排序:内排序是指在排序期间数据 对象全部存放在内存的排序;外排序是指在排 序期间全部对象个数太多,不能同时存放在内 存,必须根据排序过程的要求,不断在内、外 存之间移动的排序。 排序的时间开销:排序的时间开销是衡量算法 好坏的最重要的标志。排序的时间开销可用算 法执行中的数据比较次数与数据移动次数来衡 量。各节给出算法运行时间代价的大略估算 般都按平均情况进行估算。对于那些受对象关 键字序列初始排列及对象个数影响较大的,需 要按最好情况和最坏情况进行估算

内排序与外排序: 内排序是指在排序期间数据 对象全部存放在内存的排序；外排序是指在排 序期间全部对象个数太多，不能同时存放在内 存，必须根据排序过程的要求，不断在内、外 存之间移动的排序。 排序的时间开销: 排序的时间开销是衡量算法 好坏的最重要的标志。排序的时间开销可用算 法执行中的数据比较次数与数据移动次数来衡 量。各节给出算法运行时间代价的大略估算一 般都按平均情况进行估算。对于那些受对象关 键字序列初始排列及对象个数影响较大的，需 要按最好情况和最坏情况进行估算

静态排序:排序的过程是对数据对象本身进 行物理地重排,经过比较和判断,将对象移 到合适的位置。这时,数据对象一般都存放 在一个顺序的表中 动态排序:给毎个对象增加一个链接指针 在排序的过程中不移动对象或传送数据,仅 通过修改链接指针来改变对象之间的逻辑顺 序,从而达到排序的目的。 算法执行时所需的附加存储:评价算法好坏 的另一标准

静态排序: 排序的过程是对数据对象本身进 行物理地重排，经过比较和判断，将对象移 到合适的位置。这时，数据对象一般都存放 在一个顺序的表中。 动态排序: 给每个对象增加一个链接指针， 在排序的过程中不移动对象或传送数据，仅 通过修改链接指针来改变对象之间的逻辑顺 序，从而达到排序的目的。 算法执行时所需的附加存储: 评价算法好坏 的另一标准

衡量排序方法的标准 排序时所需要的平均比较次数 排序时所需要的平均移动 排序时所需要的平均辅助存储空间

衡量排序方法的标准 ▪ 排序时所需要的平均比较次数 ▪ 排序时所需要的平均移动 ▪ 排序时所需要的平均辅助存储空间

待排记录的数据类型定义为: #define maXsize 20 Typedef int Keytype pedef struct kEytYpe key; ∥关键字项 nfo Type otherinfo;∥其它数据项 BRedType Typedef struct RedType rMAXSIze+1/r0闲置或用作哨兵 int length; iSqlist;

待排记录的数据类型定义为： #define MAXSIZE 20 Typedef int KeyType Typedef struct {KeyType key; //关键字项 InfoType otherinfo; //其它数据项 }RedType; Typedef struct {RedType r[MAXSIZE+1] //r[0]闲置或用作哨兵 int length; }Sqlist;

插入排序( Insert Sorting) 插入排序的基本方法是:每步将一个待排序的对 象,按其关键字大小,插入到前面已经排好序的 组对象的适当位置上,直到对象全部插入为止。 直接插入排序( nsert Sort 直接插入排序的基本思想是:当插入第i(≥1)个对象 时,前面的V10,Ⅵ,,v1已经排好序。这时,用 v引的关鍵字与叫l,v2],的关键字顺序进行比较 找到插入位置即将v插入,原来位置上之后的所有对 象依次向后顺移

插入排序 (Insert Sorting) 直接插入排序的基本思想是：当插入第i (i  1) 个对象 时，前面的V[0], V[1], …, v[i-1]已经排好序。这时，用 v[i]的关键字与v[i-1], v[i-2], …的关键字顺序进行比较， 找到插入位置即将v[i]插入，原来位置上之后的所有对 象依次向后顺移。 插入排序的基本方法是：每步将一个待排序的对 象，按其关键字大小，插入到前面已经排好序的 一组对象的适当位置上，直到对象全部插入为止。 直接插入排序 (Insert Sort)

各 趟 排 21 25//49 25 608 序 012345 结 果 =1目 49 25 6(8 25 2 3 5 temp 49 i=2 2125 08 012345 tem

各 趟 排 序 结 果 21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 08 i = 1 25 0 1 2 3 4 5 temp 21 25 49 25* 16 08 49 i = 2

49 i=3 2125 608 25 012345 4同园回同 0123 5 temp 5同 21 252549 b 012345 tem

21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 i = 4 08 0 1 2 3 4 5 temp 21 25 49 16 25* 08 i = 5 i = 3 25* 16 08