数据结构》课件C语言10.ppt

第*页 归并排序 ? 算法描述： 归并排序的递归算法 void msort( RecType Sr[], RecType Tr1[], int s, int t ) {//对r[s..t]中记录进行归并排序 if( s == t ) Tr1[s] = Sr[s]; else { m = ( s + t ) / 2; msort( Sr, Tr2, s, m ); msort( Sr, Tr2, m +1, t); merge( Tr2, Tr1, s, m , t ); } } Void MergeSort( SqList L) { msort( L.r, L.r, 1, L.length ); } 第*页 n个记录要进行 多少趟归并？ 要归并?Log2n? 趟。 每趟比较次数=n, 赋值次数=n。 归并排序的算法分析 总时间复杂性为O(nlog2n)，空间复杂性为O(n)。 归并排序是稳定的。 j? i? j? j? i? i? i? j? i? [13 27 38 49 65 76 97] 一棵有n个树叶的“倒”的完全二叉树， 深度为?Log2n?+1。 第*页 概述——多关键字的排序 基数排序 示例： 已知扑克牌中52张牌面的次序关系为： ?2?3..?A?2?3..?A ?2?3..?A?2?3..?A 每一张牌面有两个关键字： 花色（ ?、?、?、?）和面值（2、3、…、K、A），且花色的地位高于面值。现要对扑克牌进行整理。 ? 这是一个多关键字的排序问题。 第*页 概述——多关键字的排序 为实现多关键字排序，通常有两种方法： 如理牌示例中，先按花色，再按面值。 1)最高位优先（MSD法） 先按最高位关键字排序，将序列分成若干子序列，再按次高位关键字排序分成若干更小的子序列，依次重复，最后得到有序序列。 2)最低位优先（LSD法） 从最低位关键字开始排序，然后再对高一位排序，依次重复，直到对最高位排序。 如理牌示例中，先按面值，再按花色。 第*页 概述——多关键字的排序 说明： 以整数关键字为例，若采用最高位优先，则首先按最高位分配，假设关键字取值0~999之间，则可将0~99的放在一个盒子中，100~199的放在另一个盒子中，…，900~999放在最后一个盒子，然后再将每个盒子中的关键字排序。这种分配方法实际上就是把一个整数看成是三位数字组合的复合关键字。 (1)当关键字为多字段时，基数排序是一种很自然的方法，一般说来，最低位优先法要比最高位优先法简单，因为前者是从头到尾进行若干次分配与收集，执行的次数取决于构成关键字成分的多少；而后者则要分配以后处理各子集的排序问题，这通常是一个递归过程。 (2)当关键字为一简单的字段时，也可以采用分配排序的思想。 快速排序某种意义上就是可看成一种最高位优先的分配排序，因为执行快速排序每趟都将关键字分成两组（两个盒子），然后递归处理排序问题。 第*页 基数排序 其中r称为基数。基数的选择和关键字的分解法，因关键字的类型而异。关键字为十进制整数时，最自然的取法是r为10（0~9），当关键字为字符串时，可取r =26（A~Z）。 基本思想：把每一个关键字看成是一个d元组： 排序时先按Kdi的值从小到大将记录分配到r个盒子中，然后依次收集这些记录，再按Kid-1的值分配到r个盒子中，如此反复，直到对K1i分配后收集起来的序列，便是完全排序的序列。 示例 设初始关键字序列为{278，109，063，930，589，184，505，269，008，083}。取 r=10，d=3，c1=0，cdr=9。以10个链队列表示10个箱子，f [i] 和 e[i] 分别为第 i(0≤i≤9) 个队列的头指针和尾指针。 链式基数排序过程示例如下 第*页 278 109 063 930 589 184 505 269 008 083 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 930 063 184 505 278 109 083 008 589 269 f [0] f [1] f [2] f [3] f [4] f [5] f [6] f [7] f [8] f [9] (b) 第一趟分配之后 930 063 083 184 505 278 008 109 589 269 (c) 第一趟收集之后 (a) 初始状