《山东大学《数据结构》讲义07排序》由会员分享，可在线阅读，更多相关《山东大学《数据结构》讲义07排序（12页珍藏版）》请在金锄头文库上搜索。
1、第七章 排序内容概述： 我们居住在一个迷惑于如何保存信息的世界里，为了寻找出路，人们必须以某种切合实际的顺序来保存信息。本章我们考虑数据处理中经常遇到的问题排序，主要内容包括：排序的基本概念；插入排序、交换排序、堆排序、归并排序等内排序方案及实现算法；外排序简介。重点与难点： 重点为插入、交换、选择等基本排序方法和改进的排序方法，归并排序算法及基数排序算法。 难点为快速排序算法、堆排序算法和归并排序算法。思考与习题： 1从时间复杂度的角度对排序方法进行归类。 2在所有排序方法中，关键字比较的次数与记录的初始排列次序无关有哪些？ 3空间复杂度最佳的排序方法有哪些？ 4从算法的简单性角度对排序方法
2、进行归类 5已知序列503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94，请给出采用希尔排序法（d1=8）对该序列作升序排序时的每一趟的结果。 6已知序列70，83，100，65，10，32，7，9，请给出采用插入排序法对该序列作升序排序时的每一趟的结果。 7已知序列10，18，4，3，6，12，1，9，18，8，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。 8采用单链表作存储结构，编写一个采用选择排序方法进行升序排序的算法第一节 概述排序（Sorting）是数据处理领域一种最常用的运算，它是把一组记录（或元素）
3、按关键字递增或递减的次序重新排列的过程。本节将解决如下问题：待排序的纪录如何存储？排序方法有哪些？如何归类？1、内排序和外排序1、内排序和外排序排序（Sorting）是数据处理领域一种最常用的运算，它是把一组记录（或元素）按关键字递增或递减的次序重新排列的过程。当排序的文件较小，在整个排序过程中，文件涉及的所有数据都可放在内存中，此时可一次性将文件装入内存进行排序，这就是内部排序。否则，当被排序的文件数据量较大，在排序过程中，不能将整个文件涉及的所有数据都同时装入内存，只能通过多次内存、外存数据传递、交换，逐步进行排序，这就是外部排序。 2、内排序的归类 2、内排序的归类内排序的方法有很多种，
4、按所用策略不同，常见的有插入排序、交换排序、选择排序、归并排序；按排序过程中所需的工作量的大小，一般分为简单的排序方法和改进的排序方法，前者的时间复杂度为O(n2)，后者的时间复杂度为O(nlogn)。 3、排序的一组记录的存储方式 3、排序的一组记录的存储方式待排序的一组记录的存储方式一般有以下三种：（1）顺序存储方式：待排序的一组记录存放在地址连续的一组存储单元上，相邻的两个记录在存储位置上也是相邻的；（2）链式存储方式：待排序的一组记录存放在静态链表中（排序时只改变记录间的次序关系而不做插入、删除操作且在排序结束时仍需调整记录，故采用静态链表），由指针指示记录之间的次序关系，则排序过程中
5、仅需修改指针而不需要移动记录；（3）带有地址向量的顺序存储方式：待排序的一组记录存储在一组地址连续的存储单元内，同时附设一个地址向量指示各个记录的存储位置，在排序过程中仅需移动地址向量中这些记录的地址而不需要移动记录本身，排序结束后按照地址向量中的值调整记录的存储位置。 第二节 插入排序插入排序是所有内排序方法中最简单的排序方法之一，本节将介绍直接插入排序、改进的插入排序和希尔排序。1、直接插入排序的算法及评价 1、直接插入排序的算法及评价在内部排序的所有方法中，最简单的排序方法之一是直接插入排序（Straight Insertion Sort）。它是由n-1趟排序组成的。例如，在第i趟排序前
6、（2in），位置从1到i-1上的记录是已排过序的，则第i趟排序是向第1到i-1个有序记录之间插入一个新记录，使插入后的记录序列仍为有序，排序过程的每一步类似于线性表中有序表的插入。如图7-1显示了一个数组在每一趟插入排序后的情况变化：初始(44) 18 74 61 42 31插入元素i=2趟排序后(18 44) 74 61 42 3118i=3趟排序后(18 44 74)61 42 3174i=4趟排序后(18 44 61 74) 42 3161i=5趟排序后(18 42 44 61 74) 3142i=6趟排序后(18 31 42 44 61 74)31图7.1插入排序示例如图7-1所示，当
7、i=3趟排序后，即第4趟排序前，第1个位置到第3个位置的记录都是有序的，准备将第4个记录61插入。插入后，即i=4时的有序序列：（18，44，61，74）。一般情况下，对于第i趟排序前，记录1i-1是已排过序的，需要将第i个记录插入其中，使之仍为有序。插入中，首先通过比较插入记录和已排序记录的大小找到插入的位置，然后将所在位置的记录及其后记录依次后移一个位置。其具体算法如下：void InsertSort(ElemType P , int n)/对具有n个记录的数组P作直接插入排序/n个记录存放在数组P1.n中，P0留作“哨兵”使用for(i=2; i=n; i+)if(Pi.keyPI-1.
8、KEY) span 将Pi插入有序子表P0=Pi;Pi=Pi-1;for(j=i-2;P0.keyPJ.KEY; span j-)Pj+1=Pj; /向后移动数组记录Pj+1=P0; /插入记录/InsertSort算法7-1直接插入排序从处理过程来看，该算法简洁、易实现，下面我们对该算法的效率进行分析。从空间上看，它只需要一个位置作为辅助空间，算法中为P0；从时间上看，该算法的主要操作和影响算法效率的步骤为比较两个记录的关键字大小和移动记录。当待排序的记录按关键字有序排列（本算法中有序为非递减排列）时，所需的关键字间的比较次数达到最小值（即n-1），不需要移动记录；反之，当待排序记录按关键字
9、非递增排列（相对本算法为反序）时，则比较次数达到最大值（即(n+2)(n-1)/2），记录移动次数也达到最大值（即(n+4)(n-1)/2）。对于随机排列的记录序列，比较次数和移动记录的次数约为n2/4。所以，插入排序的时间复杂度为O(n2)。该算法在n较小时或待排序的记录基本有序时还是较为适用的。2、折半插入排序的算法及评价 2、折半插入排序的算法及评价折半插入排序（Binary Insertion Sort）是一种改进的插入排序方法。由插入记录的基本操作可知，每次操作都是向有序表中插入记录，在查找插入位置时，我们可以通过“折半查找”来减少记录关键字的比较次数。具体算法如下：void BiI
10、nsertSort(ElemType P , int n)/对具有n个记录的数组P作折半插入排序/n个记录存放在数组P1.n中for(i=2; i=n; i+)P0=Pi; /P0作为辅助空间low=1; high=i-1;while(low=high) /折半查找插入位置m=(low+high)/2; /折半位置if(P0.keyPM.KEY) span 在低半区插入else low=m+1; /在高半区插入/whilefor(j=i-1; j=high+1; j-) Pj+1=Pj; /向后移动数组记录Phigh+1=P0; /插入记录/BiInsertSort算法7-2 折半插入排序和普
11、通插入排序相比较，折半插入排序的辅助空间也为一个位置；在时间上，虽然平均移动记录的次数不变，但是关键字的比较次数减少。本算法的时间复杂度仍为O(n2)。 3、希尔排序的思想及优点 3、希尔排序的思想及优点希尔排序使用一个序列h1, h2, , ht，叫做增量序列（Increment Sequence）。在使用增量hk的一趟排序之后，对于每一个记录i有PiPi+hk，即所有相隔hk的记录都被排序。此时称该序列是hk-排序（hk-sorted）的。而且，希尔排序具有一个很重要的性质，一个hk-排序后的序列，将在以后的排序中一直保持它的hk-排序性。假如不是这样，那么该算法就不具有什么意义了，因为前
12、面各趟排序的结构就不会被后面各趟排序给打乱。如图7-2为一个序列在各趟排序后的情况。希尔排序的优点是综合了直接插入排序的优点：在文件长度n较小时或文件基本有序的情况下，直接插入排序还是具有较高效率的。希尔排序通过使用增量hk进行分组，同一组中的元素进行比较并排序，这样在前面几趟排序时，每组长度较小，可使发生逆序的元素较快地向前大幅度调整，而在后面几趟排序时，尽管此时每组长度已经较大，但每组内的数据基本有序，需要调整的数据已经很少了，这样从整体上实现了效率的提高。 4、希尔排序算法及评价 4、希尔排序算法及评价hk-排序的一般做法是，对于hk, hk+1, , n中的每一个位置i，其中的记录在序
13、列i, i-hk, i-2hk中处于正确的位置，使该序列有序，即对该序列进行插入排序。如图7-2中所示，对于5-排序中的81, 35, 41进行插入排序，使之成为35, 41, 81的有序序列。具体算法如下：void ShellSort(ElemType P , int n)/对具有n个记录的数组P作希尔排序/n个记录存放在数组P1.n中，P0留作“哨兵”使用for(increment=n/2; increment0; increment/=2)/该增量序列为Shell建议序列，使用简单，但效率不高for(i=increment+1; i=n; i+) /针对某一增量进行一趟希尔排序if(Pi
14、.key0 & P0 .key PJ j-=increment)Pj+increment=Pj;Pj+increment=P0;/if/ShellSort算法7-3 希尔排序在希尔排序中，我们可采用不同的增量序列进行排序，而对于不同的增量序列，其算法的时间复杂度是不同的。对于Shell建议序列，即hk为1, 2, 4, 8, , n/2，算法的时间复杂度为O(n2)；对于Hibbard增量序列，即hk=2k-1，算法的时间复杂度为O(n3/2)；对于Sedgewick增量序列，即hk=9*4k- 9*2k+1或4k - 3 * 2k + 1，算法的时间复杂度为O(n7/6)第三节 交换排序交换排序是指待排序纪录间通过比较和“交换”而进行的排序。本节着重介绍冒泡排序和快速排序。1、冒泡排序的基本思想 1、冒泡排序的基本思想在需要通过大量“交换”
