人民邮政出版社：《数据结构》课程教学资源（PPT课件）第10章 内排序

痰据结柄 李云清杨庆红揭安全

李云清 杨庆红 揭安全

第10章内排序 排序是数据处理过程中经常使用的一种重要的运 算,排序的方法有很多种,本章主要讨论内排序的各 种算法,并对每个排序算法的时间和空间复杂性以及 算法的稳定性等进行了讨论。 10.1排序的基本概念 假设一个文件是由n个记录R1,R2…,Rn组成 所谓排序就是以记录中某个(或几个)字段值不減(可 不增)的次序将这n个记录重新排列,称该字段为排 序码。能唯一标识一个记录的字段称为关键码,关 键码可以作为排序码,但排序码不一定要是关键码

第10章 内排序 排序是数据处理过程中经常使用的一种重要的运 算，排序的方法有很多种，本章主要讨论内排序的各 种算法，并对每个排序算法的时间和空间复杂性以及 算法的稳定性等进行了讨论。 10.1 排序的基本概念 假设一个文件是由n个记录R1，R2，…，Rn组成， 所谓排序就是以记录中某个(或几个)字段值不减(或 不增)的次序将这n个记录重新排列，称该字段为排 序码。能唯一标识一个记录的字段称为关键码，关 键码可以作为排序码，但排序码不一定要是关键码

按排序过程中使用到的存储介质来分,可以将排 序分成两大类内排序和外排序 内排序是指在排序过程中所有数据均放在内存中 处理,不需要使用外存的排序方法。而对于数据量很 大的文件,在内存不足的情況下,则还需要使用外存, 这种排序方法称为外排序。 排序码相同的记录,若经过排序后,这些记录 仍保持原来的相对次序不变,称这个排序算法是稳 定的。否则,称为不稳定的排序算法

按排序过程中使用到的存储介质来分，可以将排 序分成两大类:内排序和外排序。 内排序是指在排序过程中所有数据均放在内存中 处理，不需要使用外存的排序方法。而对于数据量很 大的文件，在内存不足的情况下，则还需要使用外存， 这种排序方法称为外排序。 排序码相同的记录，若经过排序后，这些记录 仍保持原来的相对次序不变，称这个排序算法是稳 定的。否则，称为不稳定的排序算法

评价排序算法优劣的标准 首先考虑算法执行所需的时间,这主要是用执行 过程中的比较次数和移动次数来度量; 其次考虑算法执行所需要的附加空间。 当然,保证算法的正确性是不言而喻的,可读性等 也是要考虑的因素

评价排序算法优劣的标准 ： 首先考虑算法执行所需的时间，这主要是用执行 过程中的比较次数和移动次数来度量； 其次考虑算法执行所需要的附加空间。 当然，保证算法的正确性是不言而喻的，可读性等 也是要考虑的因素

排序算法如未作特别的说明,使用的有关定义如下 /常见排序算法的头文件,文件名 table. h # define maXsize100/文件中记录个数的最大值* typedef int keytype;/定义排序码类型为整数类型* typedef struct keytype key 为了方便,rJ-般不用 于存放排序码,在一些排序 /此处还可以定义记录中除 算法中它可以用来作为中间 frecordtype 记录单元存放临时数据。 length pede struct 域是待排序的记录个数,它 必须不大于 MAXSIZE,这样 recordtype「 MAXSIZE+1 第1 length个记录的排序码 nt length; 待排F分别存于 Stable; /待排序r1key- r[length]. key中

排序算法如未作特别的说明，使用的有关定义如下 ： /*常见排序算法的头文件，文件名table.h*/ #define MAXSIZE 100 /*文件中记录个数的最大值*/ typedef int keytype; /*定义排序码类型为整数类型*/ typedef struct{ keytype key; /*此处还可以定义记录中除排序码外的其它域*/ }recordtype; /*记录类型的定义*/ typedef struct{ recordtype r[MAXSIZE+1]; int length; /*待排序文件中记录的个数*/ }table; /*待排序文件类型*/ 为了方便，r[0]一般不用 于存放排序码，在一些排序 算法中它可以用来作为中间 单元存放临时数据。length 域是待排序的记录个数，它 必须不大于MAXSIZE，这样， 第1~length个记录的排序码 分别存于 r[1].key~r[length].key中

102插入排序 插入排序的基本方法是: 将待排序文件中的记录,逐个地按其排序码值的 大小插入到目前已经排好序的若干个记录组成的文件中 的适当位置,并保持新文件有序。 1021直接插入排序 直接插入排序算法的思路是初始可认为文件中的 第1个记录己排好序,然后将第2个到第n个记录依次插 入已排序的记录组成的文件中。在对第论个记录R进行 插入时,R1,R2…,R已排序,将记录R的排序码 key与已经排好序的排序码从右向左依次比较,找到R 应插入的位置,将该位置以后直到R各记录顺序后移 空出该位置让R插入

10.2 插入排序 插入排序的基本方法是: 将待排序文件中的记录， 逐个地按其排序码值的 大小插入到目前已经排好序的若干个记录组成的文件中 的适当位置，并保持新文件有序。 10.2.1 直接插入排序 直接插入排序算法的思路是:初始可认为文件中的 第1个记录己排好序，然后将第2个到第n个记录依次插 入已排序的记录组成的文件中。在对第i个记录Ri进行 插入时，R1，R2，…，Ri-1已排序，将记录Ri的排序码 keyi与已经排好序的排序码从右向左依次比较，找到Ri 应插入的位置，将该位置以后直到Ri-1各记录顺序后移， 空出该位置让Ri插入

组记录的排序码分别为 312,126,272,226,28,165,123 初始时将第1个排序码作为已经排好序的,把排好序 的数据记录放入中括号[中,表示有序的文件,剩下 的在中括号外,如下所示 312],126,272,226,28,165,123 设前3个记录的排序码已重新排列有序,构成一个含 有3个记录的有序文件 [126,272,312],226,28,165,123 现在要将第4个排序码226插入

一组记录的排序码分别为: 312，126，272，226，28，165，123 初始时将第1个排序码作为已经排好序的，把排好序 的数据记录放入中括号[]中，表示有序的文件，剩下 的在中括号外，如下所示： [312]，126，272，226，28，165，123 设前3个记录的排序码已重新排列有序，构成一个含 有3个记录的有序文件: [126，272，312]，226，28，165，123 现在要将第4个排序码226插入 ！

[126,272,312],226,28,165,123 现在要将第4个排序码226插入 将待插入的排序码226和已经有序的最后一个排 序码312比较,因为待插入的排序码226小于312,所 以226肯定要置于312的前面,至于是否就是置于312 的前一个位置,此时还不能确定,需要继续向左比较; 将所有大于待插入排序码226的那两个排序码 312和272依次后移一个位置,在空出的位置插入待 排序的排序码226,得一含有4个记录的有序文件 [126,226,272,312],28,165,123

[126，272，312]，226，28，165，123 现在要将第4个排序码226插入 ！ 将待插入的排序码226和已经有序的最后一个排 序码312比较，因为待插入的排序码226小于312，所 以226肯定要置于312的前面，至于是否就是置于312 的前一个位置，此时还不能确定，需要继续向左比较； 将所有大于待插入排序码226的那两个排序码 312和272依次后移一个位置，在空出的位置插入待 排序的排序码226，得一含有4个记录的有序文件： [126，226，272，312]，28，165，123

需要注意的是,当待插入排序码小于所有已排序的 排序码时,如在插入第5个值28时 [126,226,272,312],28,165,123 算法设计的时候如处理? 方法之一:设置“哨

需要注意的是，当待插入排序码小于所有已排序的 排序码时，如在插入第5个值28时： [126，226，272，312]，28，165，123 算法设计的时候如处理？ 方法之一：设置“哨 兵

void insertsort(table*tab for(i=2; length; i++)/依次插入从第2个开始的所有元素 {j=i-1; tab->r[0]key=tab→>]key/设置哨兵,准备找插入位置 While(tab->r0]keyrj]key)找插入位置并后移 tab->j+1]key=tab->key;/后移 继续向前(左)查找* tab->rj+1]key=tab->ro]key;/插入第个元素的副本,即前面设置的哨兵 算法10.1直接插入排序算法

void insertsort(table *tab) { int i,j; for(i=2;ilength;i++)/*依次插入从第2个开始的所有元素*/ { j=i-1; tab->r[0].key=tab->r[i].key;/*设置哨兵，准备找插入位置*/ while(tab->r[0].keyr[j].key) /*找插入位置并后移*/ { tab->r[j+1].key=tab->r[j].key; /*后移*/ j=j-1; /*继续向前（左）查找*/ } tab->r[j+1].key=tab->r[0].key; /*插入第i个元素的副本，即前面设置的哨兵*/ } } 算法10.1 直接插入排序算法