《算法与数据结构》第8章 排序及基本算法ppt.ppt

算法与数据结构 第8章 排序及基本算法 排序及基本算法 n为了便于检索，人们通常希望能在计算机中保存的数据是 按关键字值大小排列的有序表。 n这是因为对于有序表可以采用检索效率较高的二分法检索 算法，其平均检索长度为log2(n+1)-1;而对于无序表只能进 行顺序检索，其平均检索长度为(n+1)/2。 n又如为了方便检索，需要构造二叉检索树、B树和B+树等 树表，构造这些树表的过程本身就是一个排序的过程。 n在现今的计算机系统中，有相当大的一部分CPU时间开销 是用于对数据的排序整理上的。 n因此，学习和研究各种排序算法，分析并设计出高效适用 的排序算法，是摆在计算机科学工作者面前的重要课题之 一。 第8章 排序及基本算法 8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介 8.1 排序的基本概念 n 排序是数据处理中的重要运算，其功能是将一组 数据元素（或记录）的任意序列，经重新排列整理 成为按关键字值大小有序的序列。 n 排序的实际应用领域也是非常广泛的。例如在实 际问题的数据处理中常会遇到这样的情况，需要把 若干名字如人名、地名、国名、书名、校名、物名 等按字母顺序列表；需要把若干数值如各种考试分 数、田赛的长度、径赛的时间等按成绩次序排名； 需要把若干不同属性的记录按照某种方法排列次序 。所有这些都是排序问题，都需要把一组数据 元素或记录按照某种特定的次序排列起来。 排序的基本概念（续） n 排序的确切定义可以描述为： n设（R1，R2 Rn）是某文件的n个记录，其相应的关键 字为（K1，K2 Kn）。 n排序（sort）是这样一种操作，它确定文件中n个记录的 一种排列（Rj1，Rj2 Rjn），使得其相应关键字满足递 增（即不减）关系Kj1Kj2Kjn或递减（即不增）关系 Kj1Kj2Kjn。 n若关键字满足递增（即不减）关系时，称作按关键字升 序排序(ascending sort)； n若关键字满足递减（即不增）关系时，称作按关键字降 序排序(descending sort)。 排序的基本概念（续） n在前面定义中，关键字Ki(i=1，2 n)称作排序 码（sort code）。 n排序码可以是记录的主关键字，也可以是次关键 字，或者是多个关键字的组合（即组合关键字）。 n当排序码是主关键字时，由于主关键字可以惟一 标识一个记录，所以排序结果是惟一的。 n当排序码是次关键字时，同一关键字值可能标识 了两个或两个以上的记录，所以排序结果不惟一。 排序的基本概念（续） n若相同关键字值的记录在排序前后的相对位置不 会发生改变，即若Ri与Rj的关键字相同（Ki=Kj）且 在排序前Ri在Rj之前，排序后的Ri仍在Rj之前，则 称所用的排序算法是稳定的(stable)； n否则，若排序前后相同关键字值的记录其相对位 置可能发生改变，即排序之后的序列中有可能出 现Rj在Ri之前的情况，则称所用的排序算法是不稳 定的。 n当排序码是组合关键字时，通常称作多关键字排 序，其排序结果的惟一性取决于组合关键字是否 能惟一标识一个记录。 排序的分类 n根据排序过程中待排序文件存放的位置不同，可 以把排序分为内部和外部排序两大类。 n内部排序是指待排序文件放在内存中进行排序的 排序；内部排序适用于记录个数不很多的较小待 排序文件的排序； n外部排序是指在待排序文件很大时，内存中不能 一次容纳全部记录，还要借助于外存存放待排序 文件，在排序过程中需要对外存进行访问的排序 ；外部排序则适用于记录个数太多不能一次全部 放入内存的较大待排序文件的排序。 排序的分类（续） n按排序中所用策略的不同： n内部排序通常可以分为插入排序、选择排序、 交换排序、归并排序和分配排序这五类，每一 类中不同的排序算法都是基于同一策略的不同 方法。 n外部排序多是采用多路归并方法进行排序。 内部排序文件的组织形式 n 每种内部排序方法均可在不同的存储结构上实 现。通常待排序文件的组织形式有三种方式： n以一维数组作为组织形式，排序过程是对记录本身进行 物理重排，通过比较和判定把记录移动到合适的位置； n以链表（动态链表或静态链表）作为组织形式，排序过 程中无需移动记录，仅需修改指针即可，通常把这类排 序称为表排序； n为待排序文件组织一个辅助表，如组织一张含关键字和 指向记录指针的索引表，在排序过程中只需对辅助表的 表目进行物理重排，不需移动记录本身，在排序结束后 按辅助表调整记录位置。 排序的基本概念（续） n排序的方法很多，每一种方法都有自己的优缺点 ，适用于在不同的环境下使用，很难说哪一种方 法是最好的方法。 n由于所需的辅助空间的量一般都不大，所以排序 的时间代价是衡量排序算法的最重要的因素。 n内部排序的时间代价主要用关键字的比较次数和记录的 移动次数来衡量； n而外部排序的时间代价主要用访问外存储器的次数来衡 量。 排序的基本概念（续） n在本章主要讨论内部排序算法，以记录数组作为 待排序文件的组织形式，并假定关键字均为整数， 按递增次序讨论排序算法（即讨论升序排序问题） 。 n待排序文件中记录结构类型定义如下： typedef struct int key; /*关键字*/ elemtype otheritems; /*其它域*/ recordtype /*记录类型标识符*/ 第8章 排序及基本算法 8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介 插入排序 n插入排序的基本方法是：每次将一个待排序的记 录Ri，按其关键字Ki的大小插入到前面已经排好序 的部分文件中的适当位置，直到全部记录插完整 个文件已排好序为止。 n本节介绍的插入排序方法有直接插入排序和希尔 排序；并简介二分法插入排序、二路插入排序和 共享栈插入排序。 8.2 插入排序 8.2.1 直接插入排序 8.2.2 希尔排序 8.2.3 其它插入排序简介 直接插入排序 n直接插入排序（straight insertion sort）是一种最简 单的排序方法。 n它的基本思路是： n依次把待排序的记录逐个插入已排好序的序列中。 n一开始，第一个记录是一个长度为1的有序序列； n从第二个记录起，每次用第i(i=2，3 n)个记录的关键 字Ki与前面有序序列中记录的关键字Ki-1、Ki-2 K1进行 比较，从而找到Ki所在记录应该插入的位置并依次后移 各记录后插入之，使得有序序列的长度加1； n这样插入n-1次就会得到n个记录的有序序列，从而完成 整个文件的排序工作。 直接插入排序举例 n例如，已知待排序文件中记录的关键字序列为（ 23，48，32，107，86，75，68），直接插入排序 的过程可示意如下： n其中，方括号表示已排好序的序列，i表示插入第i个记录。 直接插入排序（续） n 在插入第i个记录时，用Ki和前面已排好序记录的关键字 比较，若Ki小则后移一个记录，直到Ki不小于时插入位置找 到了，直接插入Ki完成第i个记录的插入。 n由于后移操作会覆盖第i个记录，在算法描述中可在进行 第i个记录插入之前，先保存其于R0中再进行比较后移操作 ；这个附加的R0还可起到“监视哨”的作用，即当Ki小于前面 有序序列中的每一个关键字时，在和R0中关键字（它本身） 比较时不会小于，既找到了正确的插入位置，又避免了循 环控制变量的越界检查。 n设置监视哨是一种程序设计技巧，既使程序控制简单，又 节省了测试时间提高了检索效率。 直接插入排序的算法描述 n 直接插入排序的算法描述如下： void insertsorting(recordtype R,int n) int i,j; for(i=2;iR0和R0=Ri）,无需记录后移 ；其比较次数为n-1次，移动操作次数为2（n-1）次 ，算法的时间复杂度为O(n)。 直接插入排序的算法分析(续 ) n在最坏的情况下是待排序文件中各记录为关键字的 逆序排列（即递减序列），每一趟中需要和前面已 排好序的i-1个记录以及监视哨中R0进行关键字值 的比较，即第i趟中需进行i次比较操作； n向后移动次数为i-1次，加上与监视哨之间的两次 移 动，第i趟需要移动记录i+1次；总的比较次数为 次，总的移动次数为 次，算 法的时间复杂度为O(n2)。 直接插入排序的算法分析(续 ) n若初始文件中各记录是随机排列，即关键字的各种 排列的出现概率相同时，我们可取上述最好与最坏 情况的平均值作为比较和移动的平均次数，约为 n2/4,由此可得直接插入排序的时间复杂度为O(n2)。 n由于直接插入排序在整个排序过程中只需一个记录 的辅助空间（即R0），所以其空间复杂度为O(1)。 由于对于相同关键字值的记录在排序前后相对位置 不会发生变化（如上例中的48和 ），所以直接插入 排序是一种稳定的排序方法。 8.2 插入排序 8.2.1 直接插入排序 8.2.2 希尔排序 8.2.3 其它插入排序简介 希尔排序 n希尔排序（shells method），又称作缩小增量排序（ diminishing increatment）。它是1959年由D.L.Shell提出来的 对直接插入排序的一种改进方法。 n希尔排序是不稳定的排序算法。 n由直接插入排序的分析可知，在待排序文件已按关键字值 递增有序时的时间复杂度为O(n)，在逆序时的时间复杂度为 O(n2)。 n换句话说，如果待排序文件能够基本有序，则文件中的大 多数记录都不需要进行插入（即后移）操作，整个排序的时 间开销就可以大大减少。 n另外，当n的值很小时，n2的值受n的值的影响也不太大， 直接插入排序的效率也比较高。希尔排序正是基于这两点考 虑而得到的对直接插入排序的一种改进方法。 希尔排序的方法 n希尔排序的方法是： n先选取一个小于n的整数d1作为第一个增量，把 待排序文件中的全部记录分成d1个组，将所有距 离为d1倍数的记录放在同一个组中，在各组内进 行直接插入排序； n然后选取第二个增量d2 d) /*shellsorting end*/ 希尔排序（续） n需要说明的是，算法中没有调用直接插入排序算法 insertsorting，而是独立设计直接插入排序的部分；这 是因为希尔排序中距离为d的倍数的记录为一组，组 中成员记录之间有间隔不连续不能直接调用的缘故。 n另外，在for循环中的分组执行直接插入排序的过程 ，是依次先插入d个组中的第二个记录，再插入d个组 中的第三个记录最后插入d个组中的最后一个记 录；是d个组的交替插入过程，而不是一个组的直接 插入排序完成后再进行下一组，这样有利于算法设计 的简洁性和算法描述的方便性。 希尔排序（续） n 如果考虑设置监视哨，很自然地会考虑到仿照直接插入排 序算法中的监视哨设置办法。对于增量为d的一趟希尔排序， 待排序文件被分成d 组，各组中记录之间的距离为d；需要在 R1到Rd处设置监视哨，而在Rd+1到Rd+n处安排待排序 文件中的n个记录。由于在各趟排序中的增量d1,d2 di是逐次 缩小的，而待排序文件中各记录的位置空间安排好之后不宜变 动（移动需时间开销），所以d可选为di中的最大值d1，即一次 性安排监视哨空间并固定不变； n另外，监视哨中的值应在不同组中的不同记录插入时安排不 同的值（即待插入记录的值），但是多次更换监视哨中的值既 繁琐又影响效率，我们可以考虑在排序之前一次性设置各监视 哨的值，可设置为不超过待排序文件中最小关键字值的某一个 值如-maxint。这种监视哨的设置方法，没有在监视哨中保存 各组中的一个个待插入记录，但可以统一保存待插入记录于 R0中。 希尔排序的算法描述(设置监视哨) n 设置监视哨的希尔排序算法可描述如下： void shellsort(recordtype R,int n) int i,j,d; for(i=1;i 1); /*shellsort end*/ 希尔排序的算法分析 n在前面给出的两个算法，除了是否设置监视哨外， 排序的方法是相同的，其时间复杂度也是相同的；其 增量序列为d1= ，di= (i2)。算法中的主要时 间开销在于三重循环： n外层do-while循环控制排序趟数，共执行log2n次。 n中层的for循环控制一趟中各组记录的直接插入排序，执行 次数依次为 次；其平均次数为 ；即中层 for循环的平均执行次数不超过n。 n内层的while循环确定各组中每个记录的插入位置，进行关 键字的比较和记录的移动操作； 希尔排序的算法分析（续） n在最好的情况下只执行一次比较而无记录移动，其一趟中 总的比较次数与中层for循环的执行次数相同，为 ； n而一趟中执行插入的次数为n-di，即平均比较次数不超过 ,更不会超过log2n次； n由于希尔排序算法中开始时两个记录一组，以后随着组数 的减少组中记录增多也逐步基本有序，所以在n较大时的其 它情况下的平均比较次数也是接近于最好情况下的次数log2n 或是它的线性函数，而移动次数或平均移动次数是远远小于 比较次数和平均比较次数的； n由此得内层while循环的平均执行次数为O(log2n)阶函数。 由算法分析的乘法法则可知，前面给出的两个希尔排序算法 ，shellsorting和shellsort的时间复杂度为O(n(log2n)2)。 8.2 插入排序 8.2.1 直接插入排序 8.2.2 希尔排序 8.2.3 其它插入排序简介 1.二分法插入排序 n 由第七章的讨论我们知道，对有序表采用二分法检索， 检索性能大大优于顺序检索。 n如果我们把直接插入排序中的由后向前顺序检索寻找插入 位置的方法改为用二分法检索来实现，当n较大时就可以大 幅度地降低关键字的比较次数。我们把经过这种改进后的插 入排序方法，称作二分法插入排序（binary insertion sort）。 n二分法插入排序与直接插入排序相比较，仅是减少了寻找 插入位置时的关键字比较次数，记录的移动次数没有改变， 其时间复杂度仍为O(n2)； n所需的辅助存储空间也与直接插入排序相同，也是稳定的 排序方法（在检索位置出现关键字值相等时需后移插入位置 指示器变量，否则为不稳定方法）。 2.二路插入排序 n二路插入排序（2-way insertion sort）是在二分法插入排序 基础上的进一步改进，改进的目标是减少排序过程中记录的 移动次数，但为此多开销了n个记录大小的辅助存储空间。 n其具体方法是： n另设一个和R同类型的数组S，先将R1赋给S1，并将 S1看成是在已排好序序列中处于中间位置的记录； n然后从R中第二个记录起，依次插入到S1之前或S1之 后的有序序列中去， n若待插记录的关键字小于S1.key则插入S1之前的有序 表中，否则插入S1之后的有序表中。 n在算法实现时，把S数组看成是一个循环数组，并设两个 指针first和final分别指示排序过程中得到的有序序列中的第 一个记录和最后一个记录在S中的位置。 二路插入排序举例 二路插入排序举例（续） 二路插入排序（续） n在二路插入排序中，记录的移动次数约为n2/8，比 直接插入排序减少移动次数约一半。它只能减少移 动次数而不能绝对避免移动记录，若要大幅度降低 移动次数，可改变存储结构为静态链表，进行表插 入排序。 n此外，二路插入排序中，当R1为待排序文件中 最小或最大关键字的记录时，完全失去优越性退化 为直接插入排序的时间效率。 n二路插入排序，是一种稳定的排序方法。 3.共享栈插入排序 n共享栈插入排序（shared stack insertion sort ）也是对直接插入排序的一种改进方法。 n其基本思想是： n把待排序的记录数组R看作是一个静态的共享栈（栈1和 栈2），栈1按数组下标由小到大方向增长，栈2按数组下 标由大到小方向增长；栈1中按关键字升序排列压入待排 序记录，栈2中按关键字降序排列压入待排序记录。 n一开始先比较R1和Rn的关键字值大小，若R1Rn 则交换；top1=1,top2=n； n然后把R2到Rn-1逐一插入两个栈中，插入的过程中 始终保证栈1的栈顶记录的关键字值都不大于栈2 的栈顶 记录的关键字值。 共享栈插入排序（续） n为此需要区分以下三种情况并作相应处理： n当待插入记录Ri的关键字值不小于栈1 的栈顶记录的关 键字值且不大于栈2的栈顶记录的关键字值时，将待插记录 压入栈1中。即Ri.keyRtop1.key且 Ri.keyRtop2.key时进栈1，只须改变top1的值为 top1+1即可。 n当Ri.keytop2.key时，由栈2反复传送记录到栈1，直 到Ri.keytop2.key时将Ri插入栈2。由栈2传送到栈 1一个记录，需要把Ri+1到Rtop2-1的记录后移一个位 置。 共享栈插入排序举例 共享栈插入排序举例（续） 共享栈插入排序（续） n共享栈插入排序不需要增加额外的存储开销，在时 间性能上与二路插入排序相当，而且有效地避免了 因R1为待排序记录中关键字值为最大或最小记录 时完全失去优越性的不足。 n若增加存储开销另设与R相同类型的数组作为共享 栈，则可以进一步减少移动次数，且排序结果不象 二路插入排序那样要使用循环数组解释。 n共享栈插入排序是一种稳定的排序方法。 第8章 排序及基本算法 8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介 交换排序 n交换排序的基本方法是，两两比较待排序记录 的关键字值，并交换那些不满足顺序要求的记录 对，直到全部待排序记录都已满足顺序要求时为 止。 n本节介绍两种交换排序的方法： n一种是冒泡排序， n一种是快速排序。 8.3 交换排序 8.3.1 冒泡排序 8.3.2 快速排序 冒泡排序 n冒泡排序（bubble sort）也称作起泡排序，是 一种简单的排序方法。 n它是通过相邻记录之间的关键字比较和记录交换 ，使关键字值较小的记录由底部向上移动，而关 键字值较大的记录由顶部向下移动，就象水中的 气泡向上飘浮（冒泡）一样。 冒泡排序算法 n冒泡排序的具体做法是： n将关键字纵向排列，然后自下而上地对相邻两个记录的关 键字进行比较，若为逆序（即Rj-1.keyRj.key， j=n,n-12）则交换两个记录，直到全部记录都比较和交 换完毕（即j=2），第一趟冒泡排序结束； n此时最小关键字值的记录上浮到了R1的位置上。然后对 n-1个记录重复类似的操作，次小关键字值的记录上浮到 R2的位置上。 n重复进行这样的过程，直到没有记录需要交换为止（最多 需n-1趟冒泡排序），整个待排序文件就按关键字值升序 排列完毕。 冒泡排序算法举例 n例如，对于8个记录的关键字序列（46，26，43， 18，74，21, ,57），冒泡排序的过程如下图所示 ： 冒泡排序算法（续） n由该冒泡排序的实例，也证实了至多需要n-1趟冒 泡排序即可完成整个排序。 n事实上存在不需要n-1趟就可以完全排好序的情况 ，如上例的第五趟排序后就已经排好序了； n其识别办法是，若某一趟冒泡排序过程中没有进行 记录的位置交换，则说明待排序文件已经完全排好序 了。 n为此，需在算法中引入一个交换状态变量flag，在 每一趟排序之前置flag为0，每次交换时给flag加1， 若一趟结束时flag为0则终止算法。 冒泡排序的算法描述 void bubblesort(recordtype R,int n) int i,j,flag; recordtype temp; for(i=1;i= i+1;j-) if(Rj-1.key Rj.key) temp=Rj-1; Rj-1=Rj; Rj=temp; flag=flag+1; /*置已交换标志*/ if(flag=0) break; /*bubblesort end */ 冒泡排序算法分析 n冒泡排序也是一种稳定的排序方法。 n其时间复杂度可以如下分析： n在最好的情况下，是初始记录的关键字已递增有序时，只 需一趟排序，比较次数为n-1，没有交换记录即记录的移 动次数为0； n在最坏的情况下，是初始记录递减有序（即逆序）时，需 进行n-1趟排序，比较次数为 ，交换次数 为 ，每次交换需三次移动记录，其移动次 数为 。 n在平均情况下，关键字的比较次数和记录的移动次数大约 为最坏情况下的一半，因此冒泡排序算法的时间复杂度为 O(n2)。 冒泡排序算法分析（续） n上述的冒泡排序算法还可以作一些改进来提高排序 速度，比如： n在每趟排序中记住最后一次发生交换记录的位置K，因为 位置K之前的记录都已排好了序，下一趟的排序可以终止 于位置K而不必进行到预定的下界位置i。 n在排序过程中交替变化扫描比较的方向，即前一趟由后向 前扫描，后一趟则由前向后扫描，而不是一直都由后向前 扫描。由后向前扫描比较交换一趟，可使最轻的气泡上浮 到顶部，但只能使最重的气泡下沉一个位置；由前向后扫 描比较交换一趟，可使最重的气泡下沉到底部，但只能使 最轻的气泡上浮一个位置。交替变化扫描方向可以加速最 轻和最重的气泡向两端迅速沉浮，有利于加速排序过程。 8.3 交换排序 8.3.1 冒泡排序 8.3.2 快速排序 快速排序 n快速排序（quick sort）也称作分区交换排序，是对冒泡 排序的一种改进排序方法。它是目前各种内部排序方法中较 快的方法，故称之为快速排序。 n快速排序的基本思想是： n在待排序文件的n个记录中，任取一个记录（通常是选取 第一个记录）作为基准； n经过一趟排序后以基准记录的关键字把全部记录分为两 部分，所有关键字值比基准记录关键字值小的记录都排 列在基准记录之前，而所有关键字值比基准记录关键字 值大的记录都排列在基准记录之后； n然后对基准记录前后的这两个部分分别重复这样的过程 ，得到本趟排序的两个新到位的基准和四个部分如 此重复上述过程，直到每一个部分只剩下一个记录（即 全部到位）时为止。 快速排序算法 n设两个指示器变量i和j，分别指向待排序区间的第一个记 录和最后一个记录； n先将第一个记录移到暂存变量temp中，然后j从区间的最 后一个记录起向前扫描，直到找到满足Rj.keytemp.key的记录时，将Ri移入Rj中； n就这样j自j-1从后向前扫描一次移入一个Rj于Ri中， i自i+1从前向后扫描一次移入一个Ri于Rj中，反复交 替的扫描和移动记录； n直到i=j时把temp移入Ri中（区间中第一个记录应在的 位置），它把整个待排序区间分割为相互独立的两个更小 的区间。 快速排序的算法描述 n这种把一个待排序区间通过基准记录（第一个记录）分割 成为两个区间的一次分割排序算法如下： int divideareasort(recordtype R,int s,int t) int i,j; recordtype temp; i=s; j=t; temp=Rs; do while(Rj.key=temp.key) if(temp.keyRj.key) Ri=Rj; i=j; j=2*i; else j=t+1; Ri=temp; /*heapadjust end*/ 堆排序的算法描述 n有了上述调整堆的筛选算法，就可以很方便地设计完 整的堆排序算法如下： void heapsort(recordtype R,int n) int i; recordtype temp; for(i=n/2;i=1;i-) heapadjust(R,i,n); for(i=n;i1;i-) temp=R1; R1=Ri; Ri=temp; heapadjust(R,1,i-1); /*heapadjust end*/ 堆排序的算法分析 n堆排序的性能分析如下：设表示堆的完全二叉树深度 为h，h= ，从根到叶的筛选过程中，关键字的比 较次数至多为2（k-1）次，至多交换记录k次。所以在建 好堆后，排序过程的n-1次筛选中的比较次数不会超过下 式的值： n而在建立初始堆时的比较次数不会超过4n次，因此堆 排序在最坏情况下的时间复杂度为O(nlog2n)。 n此外，堆排序所需的辅助存储空间少。 n堆排序是一种不稳定的排序方法。 n堆排序适宜用于待排序文件中记录较多的情况，因为 其主要时间开销在于建堆和调整堆，记录较少时不合算 。 第8章 排序及基本算法 8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介 归并排序 n归并排序（merge sort）的基本思想是： n将一些已排序的子文件进行合并而得到一个完整的有序 文件。 n归并时只要比较各子文件的第一个记录的关键字，其最 小者就是全局最小者；取出它后继续比较各子文件的第 一个记录的关键码，就可以得到全局的次小者如此 下去就可完成排序任务。 n假设待排序文件中含有n个记录，我们可以把它看作是n个 有序的子序列，每个有序子序列的长度为1；然后两两归并 得到个长度为2（其中最后一个长度可能为1）的有序子序列 ；再两两归并得到长度为4的若干有序子序列如此这样 反复归并，直到得到一个长度为n的有序序列时为止。这种 排序方法称为二路归并排序（two-way merge sort）。 归并排序举例 n例如，对于待排序文件的关键字序列（22，36，06，78， 25，43，73，18，39，62，27，66，13），利用二路归并排 序的过程如下： 归并排序举例 n 由上述归并排序过程可以看出，二路归并的主 要操作是把相邻两个有序序列归并成为一个有序 序列；对于n个记录的待排序文件，需要归并趟才 能完成排序；每趟归并使有序子序列的长度增加 一倍，而使有序子序列的个数减少约一半。 n下面，我们给出对相邻两个有序序列的归并算法 ，并给出归并排序的递归算法和非递归算法。 8.5 归并排序 8.5.1 归并相邻两个有序序列 8.5.2 二路归并排序的递归算法 8.5.3 二路归并排序的非递归算法 归并相邻两个有序序列 n在前面分析的基础上，归并相邻两个有序序列为一个有序 序列的算法merge可描述如下： void merge(recordtype R,int L,int m,int h,recordtype R1) int i,j,k; i=L; /*i指向第一个有序子序列的第一个记录*/ j=m+1; /*j指向第二个有序子序列的第一个记录*/ k=L; /*k指向结果有序序列的第一个位置*/ while(im，要么jh，使得最后的两 个while循环总有一个相当于空语句，而另一个while循环把 剩余记录传送到R1中。 8.5 归并排序 8.5.1 归并相邻两个有序序列 8.5.2 二路归并排序的递归算法 8.5.3 二路归并排序的非递归算法 二路归并排序的递归算法 n 在前述算法merge的基础上，可给出二路归并排序的递归 算法如下： void mergesortrecalg(recordtype R,intL,int h,recordtype R1) int m; if(L=h) R1L=RL; else m=(L+h)/2; mergesortrecalg(R,L,m,R1); mergesortrecalg(R,m+1,h,R1); merge(R1,L,m,h,R); /*mergesortrecalg end*/ n对待排序文件R1n中的n个记录排序，只须用参数R、1 、n调用该递归算法，即mergesortrecalg(R,1,n,R1)即可。 8.5 归并排序 8.5.1 归并相邻两个有序序列 8.5.2 二路归并排序的递归算法 8.5.3 二路归并排序的非递归算法 二路归并排序的非递归算法 n在给出二路归并排序的非递归算法之前，我们先 讨论一趟归并排序的实现算法。 n设R1n中的有序子序列长度为len，只有最后 一个有序子序列的长度有可能小于len，进行两两 有序的子序列归并后的结果依次存放在R11n中 。 n进行一趟归并排序时调用算法merge，依次对相邻 的两个长度为len的有序子序列归并；当有序子序 列为奇数个或虽为偶数个但最后一个有序子序列长 度小于len时的两种情况做特殊处理。 二路归并排序的非递归算法(续) n一趟归并排序算法可描述如下： void mergepass(recordtype R,int len,int n,recordtype R1) int i=1; while(i+2*len-1=1;i-) for(j=0;j2d时，链式基数排序的时间性能比二路归并排 序、堆排序和快速排序还要好，是时间性能最好的排序方法。 从空间性能上讲，各种排序方法都比较好；链式基数排序 和希尔排序的空间性能为问题规模n的线性函数，其它排序方 法的空间性能与问题规模无关是个常数。 各种内部排序方法的比较(续) 从稳定性上看，链式基数排序、二路归并排序和除直接选 择排序之外的其它简单排序方法都是稳定的；而直接选择排序 和时间性能较好的堆排序、快速排序和希尔排序方法是不稳定 的。需要指出的是，算法的稳定性是由方法本身所决定的。对 于不稳定排序方法，不论算法如何描述，总能找出一个说明其 不稳定性的实例来；对于稳定的排序方法，尽管可以写出不稳 定的排序算法，但总能找到一种不会引起不稳定的算法描述。 n 已有的排序方法远远不止这几种，人们之所以会研 究出多种排序方法，不仅是由于排序在计算机中的重 要地位，而且与至今为止没有一种排序方法可以堪称 绝对最优有关。各种排序方法都有各自的优缺点，都 可以根据需要应用于不同的场合。 各种内部排序方法的选择 n 选取排序方法时需要考虑的因素有： 待排序文件中记录的个数n的大小，即问题规模 ； 记录本身的大小，即记录中的信息量； 关键字的分布情况，即关键字特点； 对排序算法的稳定性要求； 辅助空间大小； 所用语言工具的条件和算法的简单性等。 各种内部排序方法的选择(续) n依据这些因素，可以给出如下的选择策略可供参考： 若问题规模较小，如n50时，可选用某种简单排序方法。一般情况下 选用最简单的直接插入排序，当记录本身信息量较大时可选用直接选 择排序（交换记录次数少），当对排序有稳定性要求时也可选用冒泡 排序，当对排序速度有要求时可选用希尔排序。 若问题规模较大，则应该采用平均时间复杂度为O(nlog2n)的快速排序 、堆排序和二路归并排序。如果单纯追求平均时间性能，可选用快速 排序；如果还要追求最坏情况下的时间性能，可选用堆排序；如果既 追求时间性能又要求排序的稳定性，则可选用二路归并排序。若选用 二路归并排序，不提倡本章介绍的从单个记录起两两归并，宜和直接 插入排序结合起来使用。先用直接插入排序求得较长的有序子序列， 然后再用二路归并排序两两归并之。由于直接插入排序是稳定的，这 样改进后的归并排序方法也是稳定的。 各种内部排序方法的选择(续) 若待排序文件中各记录按关键字基本有序，宜选用直接插 入排序或冒泡排序。 当n很大而关键字的位数较少时，采用链式基数排序既可 以有很好的时间性能，又可以保证排序的稳定性，是一种 合适的排序方法选择。 n在本章中讨论的排序方法，除基数排序外都是在顺 序存储的一维数组上实现的。当记录本身信息量较大 时为了避免移动记录耗费大量时间，可以采用链式存 储结构；如插入排序和归并排序都易在链表上实现， 并可分别称作表插入排序和表归并排序。 各种内部排序方法的选择(续) n对于象快速排序和堆排序这样的难于在链表上实现 的排序方法，可以利用关键字建立索引，然后对索引 表排序，排序结束时花费O(n)的时间代价按索引表中 的次序重新排列各个记录的位置。 n一种更为简洁的方法是，引入一个整型数组t作为 辅助表；排序前令ti=i(1in)，若排序过程中 需要交换Ri和Rj，只须交换ti和tj；排序结 束时t1n中保存了记录之间的顺序关系，再花 O(n)时间按t中次序重排各记录即可。 各种内部排序方法的选择(续) n已有研究结论表明，基于关键字比较的排序方法 其在最坏情况下所能达到的最好时间性能为 O(nlog2n)。 n本章中的排序方法除基数排序外都是基于关键字 比较的排序方法，其中堆排序和二路归并排序已在 最坏情况下达到最好时间性能，快速排序、堆排序 和二路归并排序在平均情况下也已达到了最好的时 间性能。 n换句话说，要研究时间性能优于O(nlog2n)的排序 算法，就要放弃基于关键字比较的研究而另辟蹊径 。 第8章 排序及基本算法 8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介 外部排序简介 n前面讨论的排序方法，都是以待排序文件全部装 入内存为前提的内部排序方法。如果待排序文件大 到不能一次全部装入内存而有一部分必须放在外存 储器上时，相应的排序方法称之为外部排序（ ex