《算法与数据结构-C语言描述（第二版）：第8章 排序》由会员分享，可在线阅读，更多相关《算法与数据结构-C语言描述（第二版）：第8章 排序（84页珍藏版）》请在金锄头文库上搜索。
1、第八章排序目录8.1 基本概念基本概念8.2 插入排序插入排序8.2.1直接插入排序直接插入排序8.2.2二分法插入排序二分法插入排序8.2.3表插入排序表插入排序8.2.4Shell排序排序8.3 选择排序选择排序8.3.1直接选择排序直接选择排序8.3.2堆排序堆排序8.4 交换排序交换排序8.4.1起泡排序起泡排序8.4.2快速排序快速排序8.5 分配排序分配排序8.5.1概述概述8.5.2基数排序基数排序8.6 归并排序归并排序8.6.1内排序内排序8.6.2外排序外排序*8.1基本概念基本概念排序的对象是由一组记录组成的文件，每个记录由若干字段组成，所谓排排序序码码是记录中的一个(或
2、多个)字段，排序以排序码为依据。排序码可以不是关键码，则可能有多个记录具有相同的排序码，使得排序的结果不唯一。排序码之间需要进行比较，本章中都假设排序码为整型。设 R0,R1,Rn-1是 由 n个 记 录 组 成 的 文 件 ，K0,K1,Kn-1是排序码集合，所谓排排序序就是将文件中的全部记录按排序码不增(或不减)的次序重新排列。排序看成字典上的操作在排序的讨论中，并不关心被排序对象本身的逻辑结构，所以读者可以把排序看成是字典上的一种操作。不同的排序算法，可能依赖与不同的存储结构，可以理解为在字典的不同存储表示上排序的实现。而把非字典结构中元素的排序，归结为是对于其结点按照排序码建立的密集索
3、引的排序。与上一章关于索引的讨论类似，在本章的具体排序算法中，只关心排序码的作用和表示，而把记录中的其它字典隐藏起来。在待排序的文件中，如果存在多个排序码相同的记录，经过排序后，相同排序码记录的相对次序如果保持不变，则称这种排序方法是稳定稳定的，否则是不稳定的。稳定性稳定性本章中提到的记录和文件，主要是指内存的数据。待排序的记录在排序过程中全部存放在内存的称为内排序内排序，否则称为外排序外排序。外排序也就是外存文件的排序。本章讨论的主要是内排序的方法，但有些方法(例如归并排序)也适用于外排序。内排序与外排序内排序与外排序排序方法分类排序方法分类插入排序、选择排序、交换排序、分配排序、归并排序。
4、（每一种方法具体可能有多个不同算法）评价排序算法代价的标准第一，执行算法所需的时间；比较次数、移动次数第二，执行算法所需要的附加空间；另外，算法本身的复杂程度也是比较算法一个因素。8.2插入排序插入排序基本方法是每步将一个待排序的记录，按其排序码大小，插到前面已经排序的文件中的适当位置，直到全部插入完为止。直接插入排序二分法插入排序表插入排序shell排序8.2.1直接插入排序假设待排序的假设待排序的n个记录个记录R0,R1,Rn-1顺序存顺序存放在数组中，直接插入法在插入记录放在数组中，直接插入法在插入记录Ri(i=1,2n-1)时，记录集合被划分为两个区间时，记录集合被划分为两个区间R0，
5、Ri-1和和Ri，Rn-1，其中，前一个子区，其中，前一个子区间已经排好序，后一个子区间是当前未排序的间已经排好序，后一个子区间是当前未排序的部分，将排序码部分，将排序码Ki与与Ki-1，Ki-2，K0依次依次比较，找出应该插入的位置，将记录比较，找出应该插入的位置，将记录Ri插入。插入。直接插入排序采用顺序存储结构。直接插入排序采用顺序存储结构。例题设待排序的记录共8个，排序码分别为49,38,65,97,76,13,27,49，请用直接插入排序法排序(为了区别两个相同的排序码49，后面的49用49表示)。初始序列4938659776132749i=13849659776132749i=23
6、849659776132749i=33849659776132749i=43849657697132749i=51338496576972749i=61327384965769749i=71327384949657697typedefintKeyType;typedefintDataType;typedefstructKeyTypekey;/*排序码字段*/DataTypeinfo;/*记录的其它字段*/RecordNode;typedefstructintn;/*n为文件中的记录个数*/RecordNode*record;SortObject;存储结构存储结构程序实现：voidinsertS
7、ort(SortObject*pvector)若文件初态为正序，则算法的时间复杂度为O(n)，若初态为反序，则时间复杂度为O(n2)。平均移动次数与平均比较次数同级，是O(n2)。直接插入排序的平均时间复杂度为T(n)=O(n2)。算法中引入了一个附加的记录空间temp，因此辅助空间为S(n)=O(1)。直接插入排序是稳定的。算法的设计与分析算法的设计与分析8.2.2二分法插入排序在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入二分法插入排序。(1)1327384965769749(2)1327384965769749(3)1327384965 7
8、69749(4)1327 3849 49 65 76 97二分法插入排序示例二分法插入排序示例二分法插入排序必须采用顺序存储方式，存储结构的定义同上一节的SortObject。程序实现存储结构与算法代价分析代价分析二分法插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数。插入第i个记录时，如果i=2j(0j)，则恰好经过j=log2i次比较；如果2ji2j+1，则比较次数为j+1。排序的总比较次数为=0+1+2+2+k+k+k(20个1，21个2，2k-1个k)=1+2+22+2k-1+2+22+2k-1+22+2k-1=k2k2k+1=nlog2nn+1nlog2n算法8.2的
9、移动次数与算法8.1的相同，最坏的情况为n2/2，最好的情况为2n，平均移动次数为O(n2)。二分法插入排序算法的平均时间复杂度为T(n)=O(n2)。算法中增加了一个辅助空间temp，因此，算法的辅助空间为S(n)=O(1)。二分法插入排序是稳定的。代价分析代价分析8.2.3表插入排序表插入排序表插入排序的目标是在直接插入排序的基础上减少记录移动的次数，其基本思想是在每个记录中增加一个指针字段，指向下一个记录。整个被排序的文件表示成一个记录的单链表。插入记录Ri时，记录R0至Ri-1已经排序，为了确定插入的位置，可以先将记录Ri脱链，再采用顺序比较的方法找到Ri应插入的位置，像单链表的插入那
10、样，将Ri插入链表。例题初始序列为49,38,65,97,76,13,27,49，请用表插入排序法排序。图7.3表插入排序示例表插入排序必须采用链接存储方式structNode;/*单链表结点类型*/typedefstructNodeListNode;structNodeKeyTypekey;/*排序码字段*/DataTypeinfo;/*记录的其它字段*/ListNode*next;/*记录的指针字段*/;typedefListNode*LinkList;表插入排序的程序实现：voidlistSort(LinkList*plist)存储结构与算法的实现存储结构与算法的实现表插入排序时，每插入
11、一个记录，最大比较次数等于表中已排序的记录个数；最小比较次数为1。总比较次数最大为最小为n-1n表插入排序时记录移动的次数为0，但算法的比较次数与直接插入排序的比较次数同级。平均时间复杂度为T(n)=O(n2)。表插入排序是稳定的。代价分析代价分析8.2.4 Shell排序Shell排序排序的方法又称缩小增量法缩小增量法，是对直接插入排序法的改进。具体作法是先取一个整数d1n，把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，先在各组内排序；然后取d2recordp;intchild=2*p+1;while(childsize)if(childrecordchild.keypvect
12、or-recordchild+1.key)child+;/*选择比较小的子结点选择比较小的子结点*/if(temp.keypvector-recordchild.key)pvector-recordp=pvector-recordchild;/*将将小的子结点上移小的子结点上移*/p=child;child=2*p+1;elsebreak;/*调整结束调整结束*/pvector-recordp=temp;/*将将temp放入正确位置放入正确位置*/voidheapSort(SortObject*pvector)inti,n;RecordNodetemp;n=pvector-n;for(i=n/
13、2-1;i=0;i-)sift(pvector,n,i);/*建立初始堆建立初始堆*/for(i=n-1;i0;i-)/*进行进行n-1趟堆排序趟堆排序*/temp=pvector-record0;pvector-record0=pvector-recordi;pvector-recordi=temp;sift(pvector,i,0);/*重新调整建堆，注意重新调整建堆，注意i在控制调整范围中的作用在控制调整范围中的作用*/初始序列为26，5，77，1，61，11，59，15，48，19，请用（大根）堆排序法排序。排序过程中堆的主要变化在图8.6中给出。排好序后的关键码序列为：1，5，11，
14、15，19，26，48，59，61，77。例例:堆排序的时间耗费主要在构造初始堆，以及排序过程中不断将“去掉”最小元素后的元素重新建堆两部分上。初始建堆总的比较次数C1(n)4nO(n)排序过程中每去掉一个元素都需要重新建堆。总共排序过程中重新建堆比较花费的次数C2(n) 2nlog2n = O(nlog2n)整 个 堆 排 序 中 总 的 比 较 次 数 为 C(n)=C1(n)+C2(n)=O(n*log2n)。而结点移动的次数小于比较的次数，因此总的时间花费T(n)=O(n*log2n)。堆排序是不稳定的代价分析代价分析8.4交换排序交换排序交换排序交换排序的基本方法是两两比较待排序记录
15、的排序码，交换不满足顺序要求的偶对，直到全部满足为止。本节介绍起泡排序和快速排序。8.4.1起泡排序起泡排序起泡排序的方法是先将序列中的第一个记录R0与第二个记录R1比较，若前者大于后者，则两个记录交换位置，否则不交换；然后对新的第二个记录R1与第三个记录R2作同样的处理；依次类推，直到处理完第n-1个记录和第n个记录。经过这次起泡，n个记录中最大者被交换在第n个位置上。再对前n-1个记录进行同样处理，使n-1个记录的最大者被交换在整个序列的第n-1个位置上。然后再对前n-2个记录重复上述过程，这样最多做n-1次起泡就能完成排序。程序实现：voidbubbleSort(SortObject*p
16、vector）例子若文件初态为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)。若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值:起泡排序的最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)。起泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)。起泡排序是稳定的。代价分析代价分析8.4.2 快速排序快速排序是对起泡排序的改进。快速排序快速排序又称分区交换排序分区交换排序。其基本思想是在待排序的n个记录中任取一个记录(通常取第一个记录)，把所有小于该记录的记录移到其
17、左边，把所有大于该记录的记录移到其右边。所选记录正好处在其应在的位置，且把原有序列划分成两个子序列。然后，对两个子序列分别重复上述过程，直到所有记录都排好序。初始序列为49,38,65,97,76,13,27,49，用快速排序进行第一趟排序的过程如图8.8(a)所示。假设每次分区后，都是先处理前面的区，各趟排序的结果见图8.8(b)。图中用方括号括起来的部分为有待进行分区交换的部分。图8.8(a)中的49为分区的标准，是当前空出的位置。例：存储结构与算法实现快速排序采用顺序存储方式，存储结构的定义同SortObject。程序实现：voidquickSort(SortObject*pvector
18、,intl,intr)代价分析对于快速排序方法而言，当待排序记录已经排序时，算法的执行时间最长，总比较次数为最好情况下，每次划分使两个子文件的长度大致相等。则总的比较次数为C(n)n+2*C(n/2)O(n*log2n)快速排序的记录移动次数不大于比较次数，所以，快速排序的最坏时间复杂度应为O(n2)，最好时间复杂度为O(n*log2n)。快速排序的平均时间复杂度是T(n)=O(n*log2n)。算法需要一个栈空间实现递归。栈的大小取决于递归调用的深度，最多不超过n，若每次都选较大的部分进栈，处理较短的部分，则递归深度最多不超过log2n。快速排序是不稳定的。8.5 8.5 分配排序分配排序分
19、配排序分配排序的思想是把排序码分解成若干部分，然后通过对各个部分排序码的分别排序，最终达到整个排序码的排序。8.5.1概述假设文件F有n个记录F=(R0，R1，Rn-1)，记录Ri的排序码ki含有d部分(ki0,ki1,kid-1)，则文件F对排序码有序是指文件中任意两个记录Ri和Rj(0ijn-1)满足词典次序有序关系：(ki0,ki1,kid-1)(kj0,kj1,kjd-1)其中k0称为最高位排序码，kd-1称为最低位排序码。实现分配排序，有两种方法第一种是高位优先法：先对最高位排序码k0排序，将文件分成若干堆，每堆中的记录都具有相同的k0，然后分别就每堆对排序码k1排序，分成若干子堆，
20、如此重复，直到对kd-1排序，最后将各堆按次序叠在一起成为一个有序文件。第二种是低位优先法：从最低位排序码kd-1起排序，然后再对高一位排序码kd-2排序，如此重复，直到对K0排序后便成为一个有序文件。8.5.2基数排序不失一般性，下面以十为基的自然数作为排序码，并且假设其位数不超过两位。采用基数排序法，按低位优先排序时先按个位从小到大将记录分配到10个堆（队列）中，然后依次收集，再按十位分配到10个堆中，然后再收集起来，得到的便是排好序的序列。初始序列为36，5，16，98，95，47，32，36，48，10，下图是用基数排序法排序的主要过程。图中Q0.Q9是与基数对应的10个单链表表示的队
21、列，它们的头和尾指针分别是Qi.f和Qi.e。例子例子假设r是排序码的基数，d是排序码的位数，每位的类型是KeyType。待排序的文件采用带表头结点的链接表示，类型为RadixList，结点为RadixNode类型；为了实现记录的分配和收集，建立r个链接表示的队列，每个队列的类型为Queue。具体定义如下：存储结构存储结构structNode;typedefstructNodeRadixNode;structNode/*结点类型*/KeyTypekeyD;DataTypeinfo;RadixNode*next;typedefRadixNode*RadixList;/*待排序文件类型*/type
22、defstructRadixNode*f;/*队列的头指针*/RadixNode*e;/*队列的尾指针*/Queue;基数排序的实现：voidradixSort(RadixList*plist,intd,intr)文件的记录在排序前已经连接成一个带表头结点的链表。每趟排序中，清队列的时间为O(r)，将n个记录分配到队列的时间为O(n)，收集的时间为O(r)，因此，一趟排序的时间为O(r+n)。总共要进行d趟排序，基数排序的时间复杂度是T(n)=O(d*(r+n)。基数排序中，每个记录中增加了一个next字段，还增加了一个queue数组，故辅助空间为S(n)=O(n+r)。基数排序是稳定的。代价
23、分析代价分析8.6归并排序归并排序归并排序归并排序的主要思想是把待排序的文件分成若干个子文件，先将每个子文件内的记录排序，再将已排序的子文件合并，得到完全排序的文件。8.6.1内排序设文件中有n个记录，可以看成n个子文件，每个子文件中只包含一个记录，先将每两个子文件归并，得到n/2个部分排序的较大的子文件，每个子文件包含2个记录；再将每两个子文件归并，如此反复，直到得到一个文件。上述每步归并都是将两个子文件合成一个子文件，称为二路归并排序二路归并排序。类似地还有三路归并排序或多路归并排序。初始序列为25,57,48,37,12,82,75,29,16，用二路归并排序法排序的主要过程如图8.10
24、所示。图中用下划线连在一起的排序码是一个已经排序的子文件，每趟归并后，子文件的长度扩大一倍。例：二路归并排序采用顺序存储方式，存储结构的定义同SortObject。首先介绍两组归并算法两组归并算法merge。设rlow到rm和rm+1到rhigh是存储在同一个数组中且相邻的两个有序的子文件，算法8.10将这两个子文件合并为一个有序的文件，并存储在r1low到r1high中。voidmerge(RecordNode*r,RecordNode*r1,intlow,intm,inthigh)存储结构与算法存储结构与算法设各子文件长度为length，则归并前r0到rn-1中共有个有序的子文件。在mer
25、gePass中反复调用上面定义的merge操作，将相邻的一对对子文件归并。voidmergePass(RecordNode*r,RecordNode*r1,intn,intlength)一趟归并的算法一趟归并的算法mergePass二二路路归并并排排序序就是多次调用“一趟归并”过程，每趟归并后有序子文件的长度length扩大一倍。二路归并算法的实现：二路归并算法的实现：voidmergeSort(SortObject*pvector)代价分析第i趟归并后，有序子文件长度为2i，因此，具有n个记录的文件排序，必须做趟归并，每趟归并所花费的时间是O(n)， 二 路 归 并 排 序 算 法 的 时
26、间 复 杂 度 为T(n)=O(n*log2n)。算法中增加了一个数组record，算法的辅助空间为S(n)=O(n)。二路归并排序是稳定的。8.6.2外排序*按照记录的排序码，把外存文件的全部记录按照从小到大（或从大到小）的次序，重新进行排列。这种操作叫做外排序外排序。本节先介绍适合外排序的二路归并法，然后介绍速度更快的多路归并法。顺串顺串：一个长度为的顺串，就是文件中个记录按排序码递增的次序所排成的序列。二路归并排序问题的提出问题的提出外存的二路归并排序，首先需要解决两个充分外存的二路归并排序，首先需要解决两个充分大的顺串（也可以看成是两个有序文件）的合大的顺串（也可以看成是两个有序文件）
27、的合并问题。并问题。另外，如何提高外排序的速度，减少对于外存另外，如何提高外排序的速度，减少对于外存的访问次数是研究外排序的核心问题。的访问次数是研究外排序的核心问题。还有，如何减少访外时的定位时间，如何提高还有，如何减少访外时的定位时间，如何提高主机与外存设备的并行能力等，都是值得研究主机与外存设备的并行能力等，都是值得研究的重要内容。的重要内容。多路归并排序多路归并排序多路归并排序是二路归并排序的推广，可以减少归并趟数。路归并排序的基本方法是：开始，把若干长度为的初始顺串尽量均匀地分布到个输入文件，上。然后反复从，各读一个顺串，归并成长度为*的顺串，轮流地写到输出文件，上。下一趟从，归并到
28、，。一趟又一趟地反复进行，直到排序结束。前边谈到的提高二路归并排序速度的措施，都可推广到多路归并中来，不再重复。这里要重点讨论的是在内存中对来自个顺串的记录进行归并的技术。小小结结各种排序方法各有优缺点。排序算法之间的比较主要考虑以下几个方面算法的时间复杂度算法的辅助空间与被排序对象的表示方式排序算法的稳定性算法结构的复杂性适合参加排序的数据的规模由上表的平均时间复杂度可知，Shell排序、堆排序、快速排序及归并排序的速度较快，其它排序方法的速度较慢；一般情况下，从算法结构的简单性看，速度慢的排序算法比较简单、直接。Shell排序法，快速排序法、堆排序法及归并排序法可以看作是对某一种排序方法的
29、改进，算法结构一般都比较复杂。进一步分析，可以得出以下几点结论当数据规模n较小时，则采用简单的排序方法比较合适，如直接插入排序或直接选择排序等。由于直接插入排序法所需记录的移动较多，当空间的要求比较容易满足时，可以采用表插入排序法减少记录的移动。当文件的初态已基本有序时，可选择简单的排序方法，如直接插入排序或起泡排序等。当数据规模n较大时，应选用速度快的排序算法，其中快速排序法最快，被认为是目前基于比较的排序方法中最好的方法。当待排序的记录是随机分布时，快速排序的平均时间最短。但快速排序有可能出现最坏情况，这时快速排序算法的时间复杂度为O(n2)，且递归深度为n，即所需栈空间为O(n)。堆排序不会出现象快速排序那样的最坏情况，且堆排序所需的辅助空间比快速排序少。这两种算法都是不稳定的，如果要求排序是稳定的，则可以选择归并排序方法。基数排序法所需的辅助空间较大，但其时间复杂度可简化成O(dn)；当排序码的位数d较少时，可进一步简化成O(n)，能达到较快的速度。但是基数排序只适用于象字符串和整数这类有明显结构特征的排序码，当排序码的取值范围为某个无穷集合时，则无法使用。因此，当n较大，记录的排序码位数较少且可以均匀分解时，采用基数排序方法较好。归并排序法可以用于内排序，也可以用于外排序。
