山东大学《数据结构》讲义07排序.docx

第七章排序
内容概述：
我们居住在一个迷惑于如何保存信息的世界里，为了寻找出路，人们必须以某 种切合实际的顺序来保存信息。本章我们考虑数据处理中经常遇到的问题一排 序，主要内容包括：排序的基本概念；插入排序、交换排序、堆排序、归并排序 等内排序方案及实现算法；外排序简介。
重点与难点：
重点为插入、交换、选择等基本排序方法和改进的排序方法，归并排序算法及基 数排序算法。
难点为快速排序算法、堆排序算法和归并排序算法。
思考与习题：
1 .从时间复杂度的角度对排序方法进行归类。
2 .在所有排序方法中，关键字比拟的次数与记录的初始排列次序无关有哪些？
3 .空间复杂度最正确的排序方法有哪些？
4 .从算法的简单性角度对排序方法进行归类.序列{503, 17, 512, 908, 170, 897, 275, 653, 426, 154, 509,
612, 677, 765, 703, 94},请给出采用希尔排序法（dl=8）对该序列作升序 排序时的每一趟的结果。
5 .序列{70, 83, 100, 65, 10, 32, 7, 9},请给出采用插入排序法对该 序列作升序排序时的每一趟的结果。
6 .序列{10, 18, 4, 3, 6, 12, 1, 9, 18, 8},请给出采用归并排序法 对该序列作升序排序时的每一趟的结果。
7 .采用单链表作存储结构，编写一个采用选择排序方法进行升序排序的算法〃将有序的P[i・.m]和P[m+L・n]归并为有序的Q[i..n]
forfl=m+l, k=i; i<=m &&j<=n; ++k){ 〃将P中的记录由小到大归并到Q 里if (P[i].key <= P[j].key)
Q[k]=P[i++];else Q[k]=P[j++];
)if(i<=m) Q[k..n]=P[i..m]; 〃将剩余的 复制到 Q
if(j〈=n) Q[k..n]=P[j..n]; 〃将剩余的 复制到 Q}// Merge
算法7-9有序表的归并算法递归形式的二路归并排序的算法如下所示。
void MergeSort (ElemType P[ ], ElemType &Q[ ], int sjnt t){〃对具有n个记录的数组P作归并排序，s初值为0, t的初值为n・l
if(s= =t) Q[s]=P[s];
else{
m=(s+t)/2;〃将 平分为 P[s..m] P[m+l..t]
MergeSort(P, Pl, s, m); 〃递归地将归并为有序的 Pl[s..m]
MergeSort(P, Pl, m+l,t); 〃递归地将P[m+L.t]归并为有序的Pl[m+l..t]
Merge(Pl, Q, s, m, t); 〃将 Pl[s..m]和 Pl[m+l..t]归并到 Q[s,.t]
)}// MergeSort
算法7-10二路归并排序的递归算法二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。归并趟数 为(当为奇数时，那么为)。因为每一趟归并就是将两两有序表归并，而每一对有 序表归并时，记录的比拟次数均不大于记录的移动次数(即由一个数组复制到另 一个数组中的记录个数)，而记录的移动次数等于这一对有序表的长度之和，因 此每一趟归并的移动次数均等于数组中记录的个数n,即每一趟归并的时间复杂 度为0(n)。所以，二路归并排序的时间复杂度为O(nlog2n)。
二路归并排序时还需要利用和待排序数组大小相同的一个辅助数组，所以其空间 复杂度为0(n)。
第六节各种内部排序方法的比拟讨论为了在实际应用中更好地选择合适的排序算法，本节对内部排序方法进行的比拟, 主要从以下几个方面综合考虑：时间复杂度、空间复杂度、算法稳定性、算法简 单性、待排序记录数n的大小、记录本身的信息量等。
工、从时间复杂度对内排序的分析1、从时间复杂度对内排序的分析
选择n个整数组成一些随机排序,各种内部排序方法的实际时间如图7-10所示。 从时间复杂度看，所有内部排序方法可以分为两类。插入排序、选择排序和起泡 排序这三种简单排序方法属于第一类，其时间复杂度为0(n2)；堆排序、快速排 序和归并排序这三种排序方法属于第二类，其时间复杂度为O(nlog2n)。这是就 平均情况而言的，如果从最好的情况考虑，那么插入排序和起泡排序的时间复杂度 最好，为。(n),而其他算法的最好情况同平均情况大致相同。如果从最坏的情 况考虑，快速排序的时间复杂度为0(n2),插入排序和起泡排序虽然同平均情况 相同，但系数大约增加一倍，运行速度降低一半，而选择排序、堆排序和归并排 序那么影响不大。
总之，在平均情况下，快速排序最快；在最好情况下，插入排序和起泡排序最快； 在最坏情况下，堆排序和归并排序最快。
2、从空间的复杂度对内排序的分析2、从空间的复杂度对内排序的分析
从空间复杂度看，归并排序属于第一类，其空间复杂度为0(n)；快速排序属于 第二类,其空间复杂度为O(nlog2n)；其它排序方法归为第三类，其空间复杂度 为0(1)。所以，第三类算法的空间复杂度最好，第二类次之，第一类最差。
3、从算法稳定性对内排序的分析3、从算法稳定性对内排序的分析
从算法稳定性看，所有内部排序方法可以分为两类。插入排序、起泡排序和归并 排序属于第一类,是稳定的排序方法;选择排序、快速排序和堆排序属于第二类， 是不稳定的排序方法。相对而言，后者的时间性能较好。
由于大多数情况下排序是按照记录的主关键字进行的，那么所用的排序方法是否稳 定无关紧要。但是如果排序是按照记录的次关键字进行的，那么应根据问题需要慎 重选择排序方法及其描述算法。
4、从算法简单性对内排序的分析4、从算法简单性对内排序的分析
从算法简单性看，一类是简单算法，一般包括插入排序、选择排序和起泡排序, 这些算法都比拟简单和直接，易于理解；另一类是改进后的算法，一般包括堆排 序、快速排序和归并排序，这些算法都比拟复杂。当序列中的记录基本有序或者 n值较小时，直接插入排序是最正确的排序方法，因此常常将它和其他的排序方法 结合使用。
第七节外部排序外部排序是指大文件的排序，待排序的记录存储在外存储器上。本结介绍适合于 外排序方法以及外排序实现过程。
1、外排序的最正确实现方法1、外排序的最正确实现方法
外部排序是指大文件的排序，待排序的记录存储在外存储器上，在排序过程中需 要屡次进行内存和外存之间的交换。对外存文件中的记录进行排序后的结果仍然 被放到原有文件中。
外存磁盘文件能够随机存取任何位置上的信息，所以在数组上采用的各种内部排 序方法都能够用于外部排序。但考虑到要尽量减少访问外存的次数，故归并排序 方法最适合于外部排序。
2、外排序实现过程2、外排序实现过程
外部排序过程可以分成两个相对独立的阶段：
（1）按可用内存的大小，把外存上含有n个记录的文件分成假设干个长度为L的 子文件，把这些子文件依次读入内存，并利用有效的内部排序方法对它们进行排 序，再将排序后得到的有序子文件重新写入外存；
（2）对这些有序子文件逐趟归并，使其逐渐由小到大，直至得到整个有序文件 为止。
其中，第一个阶段即为内部排序的操作，而第二个阶段涉及到了外部排序中的归 并。在前面提到，内存归并排序在开始时是把数组中的每个元素均看作是长度为 1的有序表，在归并过程中，有序表的长度从1开始，依次为2、4、8直至有序表的长度len大于等于待排序的记录数n为止。而在对外存文件的归并 排序中，初始有序表的长度通常是从一个确定的长度开始而不是从1开始，这是 为了能够有效地减少归并的趟数和访问外存的次数，以提高外部排序的效率。所 以，在第一阶段要按照初始有序表确定的长度在原文件上依次建立好每个有序表, 在第二个阶段再调用对文件的归并排序算法完成排序。
第一节概述排序（Sorting）是数据处理领域一种最常用的运算，它是把一组记录（或元素） 按关键字递增或递减的次序重新排列的过程。本节将解决如下问题：待排序的纪 录如何存储？排序方法有哪些？如何归类？
1、内排序和外排序1、内排序和外排序
排序（Sorting）是数据处理领域一种最常用的运算，它是把一组记录（或元素） 按关键字递增或递减的次序重新排列的过程。
当排序的文件较小，在整个排序过程中，文件涉及的所有数据都可放在内存中， 此时可一次性将文件装入内存进行排序，这就是内部排序。否那么，当被排序的文 件数据量较大，在排序过程中，不能将整个文件涉及的所有数据都同时装入内存, 只能通过屡次内存、外存数据传递、交换逐步进行排序，这就是外部排序。
2、内排序的归类2、内排序的归类
内排序的方法有很多种，按所用策略不同，常见的有插入排序、交换排序、选择 排序、归并排序；按排序过程中所需的工作量的大小，一般分为简单的排序方法 和改进的排序方法，前者的时间复杂度为0（n2）,后者的时间复杂度为O（nlogn）。 3、排序的一组记录的存储方式3、排序的一组记录的存储方式
待排序的一组记录的存储方式一般有以下三种：（1）顺序存储方式：待排序的 一组记录存放在地址连续的一组存储单元上，相邻的两个记录在存储位置上也是 相邻的；（2）链式存储方式：待排序的一组记录存放在静态链表中（排序时只 改变记录间的次序关系而不做插入、删除操作且在排序结束时仍需调整记录，故 采用静态链表），由指针指示记录之间的次序关系，那么排序过程中仅需修改指针 而不需要移动记录；（3）带有地址向量的顺序存储方式：待排序的一组记录存 储在一组地址连续的存储单元内，同时附设一个地址向量指示各个记录的存储位 置，在排序过程中仅需移动地址向量中这些记录的地址而不需要移动记录本身， 排序结束后按照地址向量中的值调整记录的存储位置。
第二节插入排序
插入排序是所有内排序方法中最简单的排序方法之一，本节将介绍直接插入 排序、改进的插入排序和希尔排序。
1、直接插入排序的算法及评价1、直接插入排序的算法及评价
在内部排序的所有方法中，最简单的排序方法之一是直接插入排序（Straight Insertion Sort） □它是由n・l趟排序组成的。例如,在第i趟排序前（2后
(18 44 61 74) 42 31
61
i=5趟排序后
(18 42 44 61 74) 31
42
i=6趟排序后
(18 31 42 44 61 74)
31
图7.1插入排序例如
如图7-1所示，当i=3趟排序后，即第4趟排序前，第1个位置到第3个位 置的记录都是有序的，准备将第4个记录61插入。插入后，即i=4时的有序序 歹U： (18, 44, 61, 74) o
一般情况下，对于第i趟排序前，记录l~i-l是已排过序的，需要将第i个记 录插入其中，使之仍为有序。插入中，首先通过比拟插入记录和已排序记录的大 小找到插入的位置，然后将所在位置的记录及其后记录依次后移一个位置。其具 体算法如下：
void InsertSort(ElemType P[ ], int n){〃对具有n个记录的数组P作直接插入排序
//n个记录存放在数组中，P[0]留作''哨兵"使用for(i=2; i<=n; i++)
if(P[i].key将 P[i]插入有序子表P[0]=P[i]；
P[i]=P[i-l]；forQ=i-2;P[0].key
P[j+l]=p[j];〃向后移动数组记录P[j+l]=P[O];〃插入记录
) }//InsertSort算法7-1直接插入排序
从处理过程来看，该算法简洁、易实现，下面我们对该算法的效率进行分析。
从空间上看，它只需要一个位置作为辅助空间，算法中为P[0]；从时间上看, 该算法的主要操作和影响算法效率的步骤为比拟两个记录的关键字大小和移动 记录。当待排序的记录按关键字有序排列(本算法中有序为非递减排列)时，所 需的关键字间的比拟次数到达最小值(即n・l),不需要移动记录；反之，当待 排序记录按关键字非递增排列(相对本算法为反序)时，那么比拟次数到达最大值 (即(n+2)(n-l)/2),记录移动次数也到达最大值(即(n+4)(n-l)/2)。对于随 机排列的记录序列，比拟次数和移动记录的次数约为~/4。所以，插入排序的时 间复杂度为0(己)。该算法在n较小时或待排序的记录基本有序时还是较为适用 的。
2、折半插入排序的算法及评价2、折半插入排序的算法及评价
折半插入排序(Binary Insertion Sort)是一种改进的插入排序方法。
由插入记录的基本操作可知，每次操作都是向有序表中插入记录，在查找插入位 置时，我们可以通过'折半查找〃来减少记录关键字的比拟次数。具体算法如下:
void BiInsertSort(ElemType P[ ], int n){ 〃对具有n个记录的数组P作折半插入排序//n个记录存放在数组P[l「n]中 for(i=2; i<=n; i++){
P[0]P[i];〃P[0]作为辅助空间〃折半查找插入位置
〃折半位置

〃折半查找插入位置
〃折半位置
low=l; high=i-l; while(low<=high){ m=(low+high)/2;if(P[O].key=high+l; j") P[j+l]=P[j]; 〃向后移动数组记录
P[high+l]=P[0];〃插入记录)
}//BiInsertSort算法7-2折半插入排序
和普通插入排序相比拟，折半插入排序的辅助空间也为一个位置；在时间上，虽 然平均移动记录的次数不变，但是关键字的比拟次数减少。本算法的时间复杂度 仍为0(n2)。
3、希尔排序的思想及优点3、希尔排序的思想及优点
希尔排序使用一个序列hl, h2,…,ht,叫做增量序列(Increment Sequence)。 在使用增量hk的一趟排序之后，对于每一个记录i有P[i]WP[i+hk],即所有相隔 hk的记录都被排序。此时称该序列是hk-排序(hk-sorted)的。而且，希尔排 序具有一个很重要的性质，一个hk-排序后的序列，将在以后的排序中一直保持 它的hk-排序性。假如不是这样，那么该算法就不具有什么意义了，因为前面各 趟排序的结构就不会被后面各趟排序给打乱。如图7-2为一个序列在各趟排序后 的情况。
希尔排序的优点是综合了直接插入排序的优点：在文件长度n较小时或文件基本 有序的情况下，直接插入排序还是具有较高效率的。希尔排序通过使用增量hk 进行分组，同一组中的元素进行比拟并排序，这样在前面几趟排序时，每组长度 较小，可使发生逆序的元素较快地向前大幅度调整，而在后面几趟排序时，尽管 此时每组长度已经较大，但每组内的数据基本有序，需要调整的数据已经很少了， 这样从整体上实现了效率的提高。
4、希尔排序算法及评价4、希尔排序算法及评价
hk-排序的一般做法是，对于hk,hk+l,…，n中的每一个位置i,其中的记录在序 列i,i-hk,i-2hk…中处于正确的位置，使该序列有序，即对该序列进行插入排序。 如图7-2中所示，对于5-排序中的81, 35,41进行插入排序，使之成为35,41, 81 的有序序列。具体算法如下：
void ShellSort(日emType P[ ], int n){〃对具有n个记录的数组P作希尔排序
//n个记录存放在数组中，P[0]留作''哨兵〃使用for(increment=n/2; increment>0; increment/=2)
〃该增量序列为Shell建议序列，使用简单，但效率不高for(i=increment+l; i<=n; i++)〃针对某一增量进行一趟希尔排序
if(P[i].key0 && P[0] .key

关于我们      便捷服务       自信AI       AI导航        抽奖活动©2010-2026 宁波自信网络信息技术有限公司  版权所有客服电话：[phone]  投诉电话：[phone]浙公网安备33021202000488号   浙ICP备2021020529号-1  |  浙B2-20240490  关注我们 ：