【精品】插入排序.ppt

《【精品】插入排序.ppt》由会员分享，可在线阅读，更多相关《【精品】插入排序.ppt（60页珍藏版）》请在三一办公上搜索。

1、第 九 章排序,9.1 概述9.2 插入排序9.3 交换排序9.4 选择排序9.5 归并排序9.6 基数排序9.7 各种内部排序方法比较,排序的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列.,9.1 概述,排序：有n个记录的序列R1，R2，Rn，其相应关键字的序列是K1，K2，Kn，相应的下标序列为1，2，n。通过排序，要求找出当前下标序列1，2，n的一种排列p1，p2，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1 Kp2 Kpn，这样就得到一个按关键字有序的记录序列：Rp1，Rp2，Rpn。,9.1 概述,内部排序与外部排序：根据排序时数据所

2、占用存储器的不同，可将排序分为两类。一类是整个排序过程完全在内存中进行，称为内部排序；另一类是由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，成为外部排序。,稳定排序与不稳定排序：,假设Ki=Kj(1in，1jn，ij)，若在排序前的序列中Ri领先于Rj(即ij)，经过排序后得到的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，当相同关键字的领先关系在排序过程中发生变化者，则称所用的排序方法是不稳定的。12,45,123,67,45,89,在排序过程中，一般进行两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置移动到另一个位置。本章主要

3、讨论在向量结构上各种排序方法的实现。为了讨论方便，假设待排记录的关键字均为整数，均从数组中下标为1的位置开始存储，下标为0的位置存储监视哨，或空闲不用。,#define MAXSIZE 20typedef int KeyType;typedef struct KeyType key;/关键字项OtherType other_data;/其他数据项 RedType;/记录类型typedef struct RedType rMAXSIZE+1;/r0闲置或作哨兵int length;/顺序表长度Sqlist;/顺序表类型,9.2 插入排序,9.2.1 直接插入排序9.2.2 折半插入排序9.2.3

4、 希尔排序,基本方法:将待排序文件中的记录，逐个地按其关键字值的大小插入到目前已经排好序的若干个记录组成的文件中的适当位置，并保持新文件有序。,9.2.1 直接插入排序,直接插入排序算法的思路是:初始可认为文件中的第1个记录己排好序，然后将第2个到第n个记录依次插入已排序的记录组成的文件中。在对第i个记录Ri进行插入时，R1，R2，Ri-1已排序，将记录Ri的关键字keyi与已经排好序的关键字从右向左依次比较，找到Ri应插入的位置，将该位置以后直到Ri-1各记录顺序后移，空出该位置让Ri插入。,图9.1 直接插入排序的例子。,1)48 62 35 77 55 14 35 98 2)48 62

5、35 77 55 14 35 983)35 48 62 77 55 14 35 984)35 48 62 77 55 14 35 985)3548 55 62 77 14 35 986)14 35 48 5562 77 35 98 7)14 35 35 48 55 62 77 98 8)14 35 35 48 55 62 7798,假设待排序记录存放在r1.n之中，为了提高效率，我们附设一个监视哨r0，使得r0始终存放待插入的记录。监视哨的作用有两个：一是备份待插入的记录，以便前面关键字较大的记录后移；二是防止越界.,void InsertSort(Sqlist/插入到正确位置,算法描述,算法

6、分析,该算法的要点是：使用监视哨r0临时保存待插入的记录。从后往前查找应插入的位置。查找与移动用同一循环完成。直接插入排序算法分析：首先从空间角度来看，它只需要一个辅助空间r0,空间复杂度为S(n)=O(1),算法分析,从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。直接插入排序的时间复杂度:最好情况:初始有序,为O(n);最坏情况:初始逆序,为O(n2);平均时间复杂度T(n)=O(n2)直接插入排序方法是稳定的排序方法。直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。当待排记录数目较大时，直接插入排序的性能就不好,9.2.2 折半插入排序,在直接插入排序中，我

7、们采用顺序查找法来确定记录的插入位置。由于（R1，R2，Ri-1）是有序子文件，我们可以采用折半查找法来确定Ri的插入位置，这种排序称为折半插入排序(二分插入排序)。,排序思想,根据插入排序的基本思想，在找第i个记录的插入位置时，前i-l个记录已排序，将第i个记录的排序码keyi和已排序的前i-1个的中间位置记录的排序码进行比较，如果keyi小于中间位置记录排序码，则可以在前半部继续使用二分法查找，否则在后半部继续使用二分法查找，直到查找范围为空，即可确定keyi的插入位置。,图9.2 折半插入排序的例子。,1)48 62 35 77 55 14 35 98 2)48 62 35 77 55

8、14 35 983)35 48 62 77 55 14 35 984)35 48 62 77 55 14 35 985)3548 55 62 77 14 35 986)14 35 48 5562 77 35 98 7)14 35 35 48 55 62 77 98 8)14 35 35 48 55 62 7798,55,算法实现:,void BInsertSort(Sqlist/插入记录/for,算法分析,采用折半插入排序法，可减少关键字的比较次数。每插入一个元素，需要比较的次数最大为折半判定树的深度，因此插入n-1个元素的平均关键字的比较次数为O(nlog2n)。虽然折半插入排序法与直接插入

9、排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n2)。,9.2.3 希尔排序,希尔排序（Shells Method）又称“缩小增量排序”（Diminishing Increment Sort），是由D.L.Shell在1959年提出来的。希尔排序的基本思想是：先将待排序记录序列分割成若干个“较稀疏的”子序列，分别进行直接插入排序。经过上述粗略调整，整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入排序。,具体实现:首先选定两个记录间的距离d1，在整个待排序记录序列中将所有间隔为d1的记录分成一组，进行组内直接插

10、入排序，然后再取两个记录间的距离d2d1，在整个待排序记录序列中，将所有间隔为d2的记录分成一组，进行组内直接插入排序直至选定两个记录间的距离dt=1为止，此时只有一个子序列，即整个待排序记录序列。,图9.3 希尔排序过程的实例,void ShellInsert(Sqlist L,int dk)/对顺序表L做一趟希尔插入排序 for(i=dk+1；i0 j-=dk)L.rj+dk=L.rj；L.rj+dk=L.r0；/*ShellInsert*/,算法描述,void ShellSort(Sqlist&L,int dlta,int t)/*按增量序列dlta0.t-1对顺序表L做希尔排序*/fo

11、r(k=0；kt；+k)ShellInsert(L，dltak)；,算法描述续,算法分析,希尔排序的分析是一个复杂的问题，因为它的时间耗费是所取的“增量”序列的函数。到目前为止，尚未有人求得一种最好的增量序列。但大量研究也得出了一些局部的结论。在排序过程中，相同关键字记录的领先关系发生变化，则说明该排序方法是不稳定的。,9.3 交换排序,9.3.1 冒泡排序9.3.2 快速排序,9.3.1 冒泡排序,冒泡排序是一种简单的交换类排序方法，它是通过相邻的数据元素的交换，逐步将待排序序列变成有序序列的过程。冒泡排序的基本思想是：从头扫描待排序记录序列，在扫描的过程中顺次比较相邻的两个元素的大小。以升

12、序为例：在第一趟排序中，对n 个记录进行如下操作：若相邻的两个记录的关键字比较，逆序时就交换位置。在扫描的过程中，不断的将相邻两个记录中关键字大的记录向后移动，最后将待排序记录序列中的最大关键字记录换到了待排序记录序列的末尾，这也是最大关键字记录应在的位置。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是使次大的记录被放在第n-1个记录的位置上。如此反复，直到排好序为止（若在某一趟冒泡过程中，没有发现一个逆序，则可结束冒泡排序），所以 冒泡过程最多进行n-1趟。,图9.3 冒泡排序示例,48,35,62,55,14,35,77,22,40,98,48,35,62,55,62,1

13、4,62,35,77,22,77,40,1趟,2趟,3趟,4趟,5趟,6趟,算法描述,void Bubble_Sort(Sqlist change=TRUE；,算法分析,最坏情况下，待排序记录按关键字的逆序进行排列，此时，每一趟冒泡排序需进行i次比较，3i次移动。经过n-1趟冒泡排序后，总的比较次数为总的移动次数为3n(n-1)/2 次，因此该算法的时间复杂度为O(n2)，空间复杂度为O(1)。另外，冒泡排序法是一种稳定的排序方法。,9.3.2 快速排序,快速排序的基本思想是：从待排序记录序列中选取一个记录（通常选取第一个记录），其关键字设为K1，然后将其余关键字小于K1的记录移到前面，而将关

14、键字大于K1的记录移到后面，结果将待排序记录序列分成两个子表，最后将关键字为K1的记录插到其分界线的位置处。我们将这个过程称作一趟快速排序。通过一次划分后，就以关键字为K1的记录为分界线，将待排序序列分成了两个子表，且前面子表中所有记录的关键字均不大于K1，而后面子表中的所有记录的关键字均不小于K1。对分割后的子表继续按上述原则进行分割，直到所有子表的表长不超过1为止，此时待排序记录序列就变成了一个有序表。,38,49,65,97,76,13,27,49,初始关键字,49,pivotkey,27,65,13,97,49,27,38,13,49,76,97,65,49,1趟,27,13,38,2

15、7,76,49,97,65,76,2趟,49,13,27,38,49,65,76,97,49,13,27,38,49,65,76,97,3趟,有序序列,49,13,27,38,49,65,76,97,图9.4 快速排序图示,快速排序算法描述,void QSort(Sqlist,一趟快速排序算法描述:,int Partition(Sqlist L,int low，int hith)/*对顺序表L中的子表L.rlow.high部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/L.r0=L.rlow；pivotkey=L.rlow.key

16、;while(low=pivotkey)high-；L.rrow=L.rhigh;while(lowhigh/*返回基准记录的位置*/,算法分析,分析快速排序的时间耗费,共需进行多少趟，取决于递归调用深度。快速排序所需时间的平均值为 Targ(n)Knln(n)，这是目前内部排序方法中所能达到的最好平均时间复杂度。但是若初始记录序列按关键字有序或基本有序时，快速排序将蜕变为冒泡排序，其时间复杂度为O(n2)。为改进之，可采用其他方法选取枢轴元素，以弥补缺陷。,9.4 选择排序,选择排序的基本思想是：每一趟在n-i+1（i=1，2，n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。我

17、们主要介绍简单选择排序、树型选择排序和堆排序。,9.4.1 简单选择排序,简单选择排序的基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行i-1趟比较，直到所有记录排序完成为止。例如：进行第i趟选择时，从当前候选记录中选出关键字最小的k号记录，并和第i个记录进行交换。,图9.5 简单选择排序图示,49,65,38,49,76,13,27,97,13,65,38,49,76,49,27,97,13,65,27,49,76,49,38,97,13,38,27,49,76,49,65,97,13,38,27,49,76

18、,97,65,49,13,38,27,76,49,97,65,49,13,38,27,76,49,65,97,49,13,38,27,97,49,65,76,49,初始关键字,1趟,3趟,2趟,4趟,5趟,6趟,7趟,算法描述,void SelectSort(Sqlist/*SelectSort*/,算法分析,简单选择排序算法分析：在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录

19、序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是=(n-1)+(n-2)+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n2)。,9.4.2 树型选择排序,树型选择排序也称作锦标赛排序。它的基本思想是：先把待排序的n个记录的关键字两两进行比较，取出较小者。然后再在 个较小者中，采用同样的方法进行比较选出每两个中的较小者，如此反复，直至选出最小关键字记录为止。我们可以用一棵有n个结点的树来表示，选出的最小关键字记录就是这棵树的根结点。在输出最小关键字之后，为选出次小关键字，将根结点即最小关键字记录所对应的叶子结点的关

20、键字的值置为，再进行上述的过程，直到所有的记录全部输出为止。,图9.5 树型选择排序示例,(a)选出最小关键字13,图9.5 树型选择排序示例,(b)选出次小关键字27,算法分析,在树型选择排序中，被选中的关键字都是走了一条由叶子结点到根结点的比较的过程,由于含有n个叶子节点的完全二叉数的深度，则在树型选择排序中，每选择一个小关键字需要进行 次比较，因此其时间复杂度为O(nlog2n)。移动记录次数不超过比较次数，故总的算法时间复杂度为O(nlog2n)。与简单选择排序相比较降低了比较次数的数量级，增加了n-1个额外的存储空间存放中间比较结果，同时附加了与进行比较的时间耗费。为了弥补，威洛姆斯

21、在1964年提出了进一步的改进方法，即另外一种形式的选择排序方法堆排序。,9.4.3 堆排序,堆排序是对树型选择排序的进一步改进。采用堆排序时，只需要一个记录大小的辅助空间。堆排序是在排序过程中，将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录，即待排序记录仍采用向量数组方式存储，并非采用树的存储结构，而仅仅是采用完全二叉树的顺序结构的特征进行分析而已。,具体做法是：把待排序的记录的关键字存放在数组r1.n之中，将r 看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录r1作为二叉树的根，以下各记录r2.n依次逐层从左到右

22、顺序排列，任意结点ri的左孩子是r2i,右孩子是r2i+1,双亲是r i/2。对这棵完全二叉树进行调整，使各结点的关键字值满足下列条件：ri.keyr2i.key并且ri.keyr2i+1.key(i=1,2,.n/2)，满足这个条件的完全二叉树为堆。这个堆中根结点的关键字最大，称为大根堆。反之，如果这棵完全二叉树中任意结点的关键字小于或者等于其左孩子和右孩子的关键字（当有左孩子或右孩子时），对应的堆为小根堆。,图9.6 堆示例,(a)大根椎,(b)小根椎,图9.7 堆排序过程,49,65,38,49,76,13,27,97,49,38,65,97,76,13,27,49,49,97,13,6

23、5,13,49,13,97,27,49,97,27,97,49,27,97,97,38,97,38,65,65,49,76,49,49,49,97,97,49,65,65,97,76,97,76,76,97,关键字初始序列,算法分析,堆排序方法对记录数较少的文件并不值得提倡,但对n较大的文件还是很有效的.因为其运行时间主要耗费在建初始堆和调整新堆时进行的反复“筛选”上。堆排序在最坏情况下，其时间复杂度也为O（nlogn),相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小供交换用的辅助存储空间。,9.5 归并排序,前面介绍的三类排序方法：插入排序、交换排序和选择排序，都是将

24、一组记录按关键字大小排成一个有序的序列。而本节介绍的归并排序法，它的基本思想是将两个或两个以上有序表合并成一个新的有序表。假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列；在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。这种方法被称作2-路归并排序。,二路归并排序是稳定的，时间复杂度为O(nlog2n)。,归并的思想主要用于外部排序。外部排序可分两步，待排序记录分批读入内存，用某种方法在内存排序，组成有序的子文件，再按某种策略存入外存。子文件多路归并，成为

25、较长有序子文件，再记入外存，如此反复，直到整个待排序文件有序。外部排序可使用外存、磁带、磁盘，最初形成有序子文件长取决于内存所能提供排序区大小和最初排序策略，归并路数取决于所能提供排序的外部设备数。,9.6 基数排序,前介绍的排序方法都是根据关键字值的大小来进行排序的。本节介绍的方法是按组成关键字的各个位的值来实现的排序的，这种方法称为基数排序（radix sort）。采用基数排序法需要使用一批桶（或箱子），故这种方法又称为桶排序列。,基排序有两种方法：一种方法是根据关键字的最高位有效数字进行排序，然后根据次高位进行排序，依次类推，直到根据最低位有效数字进行排序，产生一个有序序列，这种方法称最

26、高位优先法。另一种方法是根据关键字的最低位有效数字进行排序，然后根据次低位进行排序，依次类推，直到根据最高位有效数字进行排序，产生一个有序序列，这种方法称最低位优先法,例如，给出关键字序列（02，77，70，54，64，21，55，11，38，21），其中关键字02用1个0在2的前面补足到2位，余关键字均为2位的正整数。进行基数排序的过程如图9-9所示。在这个例子中，文件和所有的队列都表示成向量（一维数组）。显然，关键字的某一位有可能均为同一个数字（例如，个数都为0），这时所有的记录都同时装入同一个队列中（例如，同时装入0号队列中）。因此，如果每个队列的大小和文件大小相同，则需要一个10倍于文

27、件大小的附加空间。此外，排序时需要进行反复的分配和收集记录。所以，采用顺序表示是不方便的。,基数排序所需的计算时间不仅与文件的大小n有关，而且还与关键字的位数、关键字的基有关。设关键字的基为r（十进制数的基为10，二进制数的基为2），为建立r个空队列所需的时间为O（r）。把n个记录分放到各个队列中并重新收集起来所需的时间为O（n），因此一遍排序所需的时间为O（n+r）。若每个关键字有d位，则总共要进行d遍排序，所以基数排序的时间复杂度为O（d（n+r）。由于关键字的位数d直接与基数r以及最大关键字的值有关，因此不同的r和关键字将需要不同的时间。,9.7 各种内部排序方法比较,介绍的上述各种内部

28、排序方法中，就所需要的计算时间来看，快速排序、归并排序、堆排序是很好的方法。但是，归并排序需要大小为n的辅助空间，快速排序需要一个栈。除了快速排序、堆排序、选择排序不稳定外，其它排序方法都是稳定的。评价一个排序算法性能好坏的主要标准是它所需的计算时间和存储空间。影响计算时间的两个重要因素是比较关键字的次数和记录的移动次数。在实际应用中，究竟应该选用何种排序方法，取决于具体的应用和机器条件。,作业,1、已知一组记录的关键字为（45,23,30,38,9,77,12,96,23,76,5），要求：（1）用直接插入排序方法进行排序，写出每一趟排序后的结果；（2）用冒泡法排序，写出第一趟冒泡过程和各趟冒泡排序后的结果；（3）用希尔排序方法进行排序，画出增量d分别为4,2,1时，每趟排序后的结果；（4）用堆排序进行排序，写出在建初始堆和堆排序的过程中，每次筛运算后的排序结果，并画出初始建堆的图形示意图；（5）用快速排序方法进行排序，写出第一次划分过程和每一趟排序后的结果；（6）用二路归并方法进行排序，写出每一趟二路归并排序后的结果；,