《《数据结构（C语言版）》电子教案－赵坚 数据结构08》由会员分享，可在线阅读，更多相关《《数据结构（C语言版）》电子教案－赵坚 数据结构08（107页珍藏版）》请在金锄头文库上搜索。
1、2019/5/24,1,第8章 排序,排序的概念及种类 插入法排序的各种具体实现方法及算法分析 选择法排序的各种具体方法的实现及时间性能分析 交换法排序的具体实现及性能分析 归并排序和基数排序的各自实现算法,2019/5/24,2,本章导读,排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。由于需要排序的数据表的基本特性可能存在差异，使得排序方法也不同。如何合理地组织数据的逻辑顺序，按照何种方式排出的序列最有效？这是本章要讨论的主题。本章主要介绍排序的概念及几种最常见的排序方法，讨论其性能和特点，并在此基础上进一步讨论各种方法的适用场合，以便
2、在实际应用中能根据具体的问题选择合适的排序方法。通过本章学习，读者应该掌握以下几项内容： 排序的概念及种类 插入法排序的各种具体实现方法及算法分析 选择法排序的各种具体方法的实现及时间性能分析 交换法排序的具体实现及性能分析 归并排序和基数排序的各自实现算法,2019/5/24,3,8.1 排序的基本概念,8.1.1 排序及其分类,1排序概念,排序（sorting）又称分类，是数据处理领域中一种很常用的运算。排序就是把一组记录或数据元素的无序序列按照某个关键字值（关键字）递增或递减的次序重新排列的过程。排序的主要目的就是实现快速查找。日常生活中通过排序以后进行检索的例子屡见不鲜。如电话簿、病历
3、、档案室中的档案、图书馆和各种词典的目录表等，几乎都需要对有序数据进行操作。,2019/5/24,4,假设含有n个记录的序列为： R1，R2 ，Rn (8-1) 其相应的关键字序列为： K1，K2 ，Kn 需确定1，2， ，n的一种排序p1，p2， ，pn，使其 相应的关键字满足如下关系： Kp1Kp2Kpn (8-2) 即使得式（8-1）的序列成为一个按关键字有序的序列 R p1，R p2 ，Rpn (8-3) 这个将原有表中任意顺序的记录变成一个按关键字有序排列的过程称为排序。,2019/5/24,5,2排序分类,增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否
4、则就是减排序。 稳定排序和不稳定排序：假设Ki=Kj（1in，1jn，ij），且在排序前的序列中Ri领先于Rj（即ij）。若在排序后的排序中Ri仍领先于Rj，即那些具有相同关键字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；反之，若Rj领先于Ri，则称所用的方法是不稳定的。,2019/5/24,6,(3) 内部排序与外部排序：在排序中，若数据表中的所有记录的排列过程都是在内存中进行的，称为内部排序。由于待排序的记录数量太多，在排序过程中不能同时把全部记录放在内存，需要不断地通过在内存和外存之间交换数据元素来完成整个排序的过程，称为外部排序。在外部排序情况下，只有部分记
5、录进入内存，在内存中进行内部排序，待排序完成后再交换到外部存储器中加以保存。然后再将其它待排序的记录调入内存继续排序。这一过程需要反复进行，直到全部记录排出次序为止。显然，内部排序是外部排序的基础，本章先介绍内部排序的各种方法，最后再讨论外部排序。,2019/5/24,7,8.1.2 排序算法的效率分析,与许多算法一样，对各种排序算法性能的评价主要从两个方面来考虑，一是时间性能；二是空间性能。,1 时间复杂度分析,排序算法的时间复杂度可用排序过程中记录之间关键字的比较次数与记录的移动次数来衡量。在本章各节中讨论算法的时间复杂度时，一般都按平均时间复杂度进行估算；对于那些受数据表中记录的初始排列
6、及记录数目影响较大的算法，按最好情况和最坏情况分别进行估算。,2019/5/24,8,2空间复杂度分析,排序算法的空间复杂度是指算法在执行时所需的附加存储空间，也就是用来临时存储数据的内存使用情况。 在以后的排序算法中，若无特别说明，均假定待排序的记录序列采用顺序表结构来存储，即数组存储方式，并假定是按关键字递增方式排序。为简单起见，假设关键字类型为整型。待排序的顺序表类型的类型定义如下： typedef int KeyType /定义关键字类型 typedef struct dataType /记录类型 keytype key; /关键字项 elemtype otherelement; /其
7、他数据项 RecType;,2019/5/24,9,8.2 插入排序,插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。也就是说，将待序列表分成左右两部分，左边为有序表（有序序列），右边为无序表（无序序列）。整个排序过程就是将右边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。根据不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序、表插入排序和希尔排序等。本章重点介绍直接插入排序、折半插入排序和希尔排序。,2019/5/24,10,8.2.1 直接插入排序,直接插入排序(Insertion So
8、rt)是所有排序方法中最简单的一种排序方法。其基本原理是顺次地从无序表中取出记录Ri(1in)，与有序表中记录的关键字逐个进行比较，找出其应该插入的位置，再将此位置及其之后的所有记录依次向后顺移一个位置，将记录Ri插入其中。 假设待排序的n个记录为R1，R2 ，Rn，初始有序表为R1，初始无序表为R2 Rn。当插入第i个记录Ri(2in)时，有序表为R1Ri-1，无序表为Ri Rn。将关键字K i依次与Ki-1，Ki-2 ，K1进行比较，找出其应该插入的位置，将该位置及其以后的记录向后顺移，插入记录Ri，完成序列中第i个记录的插入排序。当完成序列中第n个记录Rn的插入后，整个序列排序完毕。,2
9、019/5/24,11,向有序表中插入记录，主要完成如下操作： (1) 搜索插入位置。 (2) 移动插入点及其以后的记录空出插入位置。 (3) 插入记录。,假设将n个待排序的记录顺序存放在长度为n+1的数组R1Rn 中。R0作为辅助空间，用来暂时存储需要插入的记录，起监视哨的作用。直接插入排序算法如下:,2019/5/24,12,void Insert_Sort(int R,int n) int i,j; for(i=2;i=n; i+) /表示待插入元素的下标 R0=Ri; /设置监视哨保存待插入元素，腾出Ri空间 j=i-1; /j指示当前空位置的前一个元素 while(R0.keyRj.
10、key)/搜索插入位置并后移腾出空 Rj+1=Rj; j-; Rj+1=R0; /插入元素 ,2019/5/24,13,显然，开始时有序表中只有1个记录R1，然后需要将R2Rn的记录依次插入到有序表中，总共要进行n-1次插入操作。首先从无序表中取出待插入的第i个记录Ri，暂存在R0中；然后将R0.key依次与Ri-1.key，Ri-2.key，进行比较，如果R0.keyRi-j.key（1ji-1），则将Ri-j后移一个单元；如果R0.keyRi-j.key，则找到R0插入的位置i-j+1，此位置已经空出，将R0 (即Ri)记录直接插入即可。然后采用同样的方法完成下一个记录Ri+1的插入排序。
11、如此不断进行，直到完成记录Rn的插入排序，整个序列变成按关键字非递减的有序序列为止。在搜索插入位置的过程中，R0.key与Ri-j.key进行比较时，如果j=i，则循环条件 R0.keyRi-j.key不成立，从而退出while 循环。由此可见R0起到了监视哨的作用，避免了数组下标的出界。,2019/5/24,14,【例8-1】假设有7个待排序的记录，它们的关键字分别为23，4，15，8，19，24，15，用直接插入法进行排序。,【解】直接插入排序过程如图8-1所示。方括号 中为已排好序的记录的关键字，有两个记录的关键字都为15，为表示区别，将后一个15加下划线。,图8-1 直接插入排序,20
12、19/5/24,15,空间性能：该算法仅需要一个记录的辅助存储空间，空间复杂度为O(1)。 时间性能：整个算法执行for循环n-1次，每次循环中的基本操作是比较和移动，其总次数取决于数据表的初始特性，可能有以下几种情况： （1）当初始记录序列的关键字已是递增排列时，这是最好的情况。算法中while语句的循环体执行次数为0，因此，在一趟排序中关键字的比较次数为1，即R0的关键字与Rj的关键字比较。而移动次数为2，即Ri移动到R0中，R0移动到Rj+1中。所以，整个排序过程中的比较次数和移动次数分别为(n-1)和2(n-1)， 因而其时间复杂度为O(n)。,稳定性：由于该算法在搜索插入位置时遇到关
13、键字值相等的记录时就停止操作，不会把关键字值相等的两个数据交换位置，所以该算法是稳定的。,2019/5/24,16,（2）当初始数据序列的关键字序列是递减排列时，这是最坏的情况。在第i次排序时， while语句内的循环体执行次数为i。因此，关键字的比较次数为i，而移动次数为i+1。所以，整个排序过程中的比较次数和移动次数分别为：,（3）一般情况下，可认为出现各种排列的概率相同，因此取上述两种情况的平均值，作为直接插入排序关键字的比较次数和记录移动次数，约为n2/4。所以其时间复杂度为O(n2)。 根据上述分析得知：当原始序列越接近有序时，该算法的执行效率就越高。,2019/5/24,17,8.
14、2.2 折半插入排序,直接插入排序的基本操作是在有序表中进行查找和插入，而在有序表中查找插入位置，可以通过折半查找的方法实现，由此进行的插入排序称之为折半插入排序。 所谓折半查找，就是在插入Ri时（此时R1，R2，Ri-1已排序），取Ri/2的关键字Ki/2 与Ki进行比较（i/2 表示取不大于i/2的最大整数），如果KiKi/2，Ri的插入位置只能在R1和Ri/2 之间，则在R1和Ri/2-1之间继续进行折半查找，否则在Ri/2+1和Ri-1 之间进行折半查找。如此反复直到最后确定插入位置为止。折半查找的过程是以处于有序表中间位置记录的关键字和Ki比较，经过一次比较，便可排除一半记录，把可插
15、入的区间缩小一半，故称为折半。,2019/5/24,18,设置始指针low，指向有序表的第一个记录，尾指针high，指向有序表的最后一个记录，中间指针mid指向有序表中间位置的记录。每次将待插入记录的关键字与mid位置记录的关键字进行比较，从而确定待插入记录的插入位置。折半插入排序算法如下：,typedef int keytype; void Insert_halfSort(RecType R,int n) /*对顺序表R作折半插入排序*/ int i,j,low,high,mid; for(i=2; i=n; i+) R0=Ri; /保存待插入元素 low=1; high=i-1; /设置初始区间,2019/5/24,19,while(lowRmid.key) low=mid+1; 插入位置在后半部分中 else high=mid-1; /插入位置在前半部分中 for(j=i-1;j=high+1; -j) /high+1为插入位置 Rj+1=Rj; /后移元素，空出插入位置 Rhigh+1=R0; /将元素插入 ,2019/5/24,20,【例8-2】待排序记录的关键字为：28，
