数据结构 第四版 高职计算机应用技术专业 安训国 课件第八章 排序

《数据结构 第四版 高职计算机应用技术专业 安训国 课件第八章 排序》由会员分享，可在线阅读，更多相关《数据结构 第四版 高职计算机应用技术专业 安训国 课件第八章 排序（65页珍藏版）》请在金锄头文库上搜索。

1、第8章 排 序,第8章 排 序,学习目的要求:,掌握排序的概念和排序的种类。 熟练掌握五类基本排序:插入排序、交换排序、选择排序、归并排序和基数排序的算法思想、算法实现和性能分析。,8.1 排序的基本概念,8.2 插入排序,8.3 选择排序,8.4 交换排序,8.5 归并排序,8.6 基数排序,8.7 几种排序方法的比较,第8章 排 序,8.1 排序的基本概念,假设含有n个记录的序列为R1，R2，Rn其相应的关键字序列为K1，K2，Kn需确定1，2，n的一种排列P1，P2， ，Pn，使其相应的关键字满足如下非递减关系（满足非递增关系时，将“”号改为“”号）Kp1Kp2Kpn使n个记录的无序序列

2、成为一个按关键字有序的序列Rp1 ，Rp2 ，Rpn这样一种操作过程称为排序。,排序过程中依据的不同原则，内部排序方法可大致分为插入排序、交换排序、选择排序、归并排序和基数排序等五类。,评价一个排序算法优劣的标准主要有两条:第一条是算法执行时所需的时间，第二条是执行算法时所需要的附加空间。执行排序的时间复杂性是算法优劣的重要的标志。,8.1 排序的基本概念,影响时间复杂性的主要因素又可以用算法执行中的比较次数和移动次数来衡量，所以在应用时还要根据具体情况来计算实际开销，以选择合适的算法。,通常，在排序的过程中需进行下列两种基本操作: （1）比较两个关键字的大小; （2）将记录从一个位置移动至另

3、一个位置。,8.1 排序的基本概念,待排序的记录序列可以有下列三种存储方式: （1）待排序的记录存放在地址连续的一组存储单元上，它类似于线性表。在这种存储方式中，记录之间的次序关系由其位置决定，因此排序时必须移动记录; （2）待排序的记录存放在静态链表中，记录之间的次序关系由指针指定，排序时不需要移动记录，仅需修改指针; （3）待排序的记录本身存储在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，排序时仅需移动地址向量中这些记录的“地址”，排序后再按照地址向量中的值调整记录的存储位置。,8.1 排序的基本概念,如果在排序期间具有相同键值的记录的相对位置不变，即在原序列中R

4、i和Rj的键值Ki=Kj且Ri在Rj之前，而排序后的序列中Ri仍在Rj之前，则称此排序方法是稳定的，否则称为不稳定的。,8.1 排序的基本概念,8.2 插入排序,插入排序（Insertion Sort）的基本思想是:每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的有序序列中的适当位置上，直到全部记录插入完成为止。 根据具体插入方法的不同，插入排序可分为好几种，本节介绍其中的四种插入排序方法:直接插入排序、折半插入排序、2路插入排序和希尔排序。,8.2.1 直接插入排序,直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是依次将记录序

5、列中的每一个记录插入到有序序列中，使有序序列的长度不断地扩大。,8.2 插入排序,这样，一共需要经过n-1趟就可以将初始序列的n个记录重新排列成按关键字值大小排列的有序序列。,其具体的排序过程可以描述如下: 首先将待排序记录序列中的第一个记录作为一个有序序列，将记录序列中的第二个记录插入到上述有序序列中形成由两个记录组成的有序序列，再将记录序列中的第三个记录插入到这个有序序列中，形成由三个记录组成的有序序列，如此进行下去，直到最后一个记录也插入完成。,8.2 插入排序,注意:第二条记录和第八条记录的相对位置在排序后没有发生变化，此排序算法是稳定的。,8.2 插入排序,main() int i,

6、j; int r9=0,42,36,56,78,67,11,27,36; for(i=2;i=8;+i) /*第一个数是有序的,为初始有序序列,i从2开始*/ if(riri-1) /*如“,需将ri插入到前面有序序列中*/ /*否则ri不需要插入,保持原来位置*/ r0=ri; /*ri的值放入监视哨中*/ for(j=i-1;r0rj;-j) rj+1=rj; /*记录后移*/ rj+1=r0; /*插入到正确位置*/ for(i=1;i=8;i+) printf(“%d “,ri); /*输出排序后的数组元素*/ ,8.2 插入排序,直接插入排序算法简单、容易实现，其算法的时间复杂度是O

7、（n2）。 从空间复杂度来看，只需要一个记录大小的辅助空间用于暂存待插入的记录。 当待排序记录较少时，排序速度较快，反之，当待排序的记录数量较大时，大量的比较和移动操作将使直接插入排序算法的效率降低; 另外，若当待排序的数据元素基本有序时，排序过程中的记录移动次数会大大减少，从而效率会有所提高。 直接插入排序是一种稳定的排序方法。,8.2 插入排序,8.2.2 折半插入排序,折半插入排序是对直接插入排序的改进算法，它是利用折半查找来实现插入位置的定位，因为折半查找的效率比较高，因此可以减少排序过程中的比较次数。适用于待排序的记录数量较大的情况。,8.2 插入排序,一趟折半插入排序的步骤为: （

8、1）初始化 将待插入的记录存入r0中:r0ri; 给指定查找区间上下界指针赋值:low1，high i-1; （2）折半查找插入位置; （3）将插入位置后面的记录依次后移一个位置; （4）将暂存在r0中的待插入记录放入找到的位置上。,8.2 插入排序,折半插入排序仅仅减少了关键字间的比较次数，而记录的移动次数不变。因此折半插入排序的时间复杂度仍为O（n2）。 从空间复杂度来看，折半插入排序只需要一个记录大小的辅助空间用于暂存待插入的记录，这与直接插入排序相同。 折半插入排序是一种稳定的排序方法。,8.2 插入排序,8.2.3 2-路插入排序,2-路插入排序是对折半插入排序的改进算法，它是利用增

9、加辅助空间来减少排序过程中移动记录的次数，也就是我们常说的“以空间换时间”。,8.2 插入排序,具体做法是:建立一个和待排序序列rn同类型的数组dn作为辅助空间。首先，将r0的值赋给d0，将d0看成是处于最后有序序列中处于中间位置的记录，然后从r1开始依次将记录插入到d0之前或之后的有序序列中。将数组d看成是一循环向量（既首尾相连的环状空间），并设置两个指针first和final分别指向有序序列的第一条和最后一条记录，将当前待插入记录ri与d0比较，若rid0，则将其插入d0之前的有序序列中，反之，则将其插入到d0之后的有序序列中。当所有的记录都插入完成后，从指针first所指向的记录开始一直

10、读取到指针final所指向的记录，所得到的序列就是排序后的有序序列。,8.2 插入排序,8.2.4 希尔排序,希尔排序方法又称为缩小增量排序（Diminishing Increment Sort），它也是一种插入排序方法，是对直接插入排序方法的改进。,基本思想是将整个待排序的记录序列划分成若干个子序列，然后分别对每个子序列进行直接插入排序，这样可以减少参与直接插入排序的数据量，如此反复，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录进行一次直接插入排序。,8.2 插入排序,例如，一组待排序的记录的关键字如下，要求按照关键字由小到大进行排序。 45 38 63 85 71

11、17 28 45 6 90（n=10）,按di+1= di/2 选取增量序列，具体排序的程序如下:,8.2 插入排序,从以上结果发现排序前序列中的第一条记录和第八条记录的关键字相同，在排序后它们的相对位置与排序前的相对位置颠倒了，因此希尔排序是一种不稳定的排序方法。 在待排序的记录数目较大的情况下，希尔排序方法一般要比直接插入排序方法快。 其时间复杂度与所选取的增量序列有关，是所取增量序列的函数，介于O（nlog2n）和O（n2）之间。增量序列有多种取法，但应使增量序列中的值没有除1之外的公因子，并且增量序列中的最后一个值必须为1。 从空间复杂度来看，与直接插入排序一样，希尔排序也只需要一个记

12、录大小的辅助空间，用于暂存当前待插入的记录。,8.2 插入排序,8.3 选择排序,选择排序（Selection Sort）的基本思想是:每一趟从待排序的序列中选出关键字最小的记录，顺序放在已排好序的子序列的最后，直到全部记录排序完毕。常用的选择排序方法有简单选择排序和堆排序。,简单选择排序的基本思想是:将整个序列（假设含有n条记录）分为有序区和无序区，初始时有序区为空，无序区为整个待排序序列。 第1趟排序，从无序区的n个记录中选取最小的记录与序列中的第一条记录交换位置，它做为有序区的第一条记录，此时无序区剩下n-1条记录; 第2趟排序，从无序区的n-1条记录中选取最小的记录与序列中的第二条记录

13、交换位置，它做为有序区的第二条记录，此时无序区剩下n-2条记录 第i趟排序，从无序区的n-i+1条记录中选取最小的记录与序列中的第i条记录交换，它做为有序区的第i条记录，此时无序区剩下n-i条记录; 如此反复，n个记录的可经过n-1 趟简单选择排序得到有序结果。,8.3.1 简单选择排序,8.3 选择排序,例如，一组待排序的记录的关键字如下，要求按照关键字由小到大进行排序。,8.3 选择排序,简单选择排序算法简单，但是速度较慢，时间复杂度为O（n2），并且是一种不稳定的排序方法，在排序过程中也只需要一个用来交换记录的暂存单元作为辅助空间。,8.3 选择排序,8.3.2 堆排序,堆排序（Heap

14、 Sort）是利用堆的特性进行排序的过程。堆的定义如下: n个元素的序列为K1，K2，Kn， 当且仅当满足下列关系时，称之为堆。 KiK2iKiK2i+1或KiK2iKiK2i+1（i=1，2，n/2） 若将与此序列对应的一维数组看成是一棵完全二叉树按层次编号的顺序存储，则堆的含义表明，完全二叉树中所有非终端结点的值均不小于（或不大于）其左、右孩子结点的值。因此，堆顶元素的值必为序列中的最大值或最小值（即大顶堆或小顶堆）。,8.3 选择排序,堆排序的基本思想是:对一组待排序的记录，首先把它们按堆的定义排成一个堆，将堆顶元素取出;然后把剩下的记录再排成堆，取出堆顶元素;依次下去，直到取出全部元素

15、，从而将全部记录排成一个有序序列。,8.3 选择排序,实现堆排序需要解决两个问题: （1）如何将一个无序序列建成一个堆? （2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆?,建堆就是把待排序的记录序列R1，R2，Rn，按照堆的定义调整为堆，使父结点的关键字大于（或小于）子结点的关键字。为此，我们先把待排序数据初始次序置入完全二叉树的各个结点中，然后由下而上逐层进行父子结点的关键字比较并交换，直到使其最后满足堆的条件。 建堆时是从最后一个非终端结点 n/2 开始的。,8.3 选择排序,例如，假定待排序的一组数据序列为: 42 36 56 78 67 11 27 36,对上述待排序序列建成堆之后，输出堆顶元素并调整成新堆的过程如图所示。,8.3 选择排序,对一组有n个记录的待排序序列进行按关键字非递减排序时，先建立一个大顶堆，然后选取关键字值最大的堆顶记录与最后一个记录交换，再对前n-1个记录调整为一个新的大顶堆，如此反复直到排序结束。,8.3 选择排序,void heapadjust(int r,int s,int m int rc,j; /*rc暂存记录的关键字*/ rc=rs; /*记录关键字送rc*/ for(j=2*s;jrj) break; /*将rj调到父结点的位置*/ rs=rj; s=j; rs=rc;