08-第九章排序.ppt

折半查找算法的前提是什么 查找表必须是有序表 由无序到有序的过程就是排序 知识回顾 9 1概述 9 2插入排序 9 3交换排序 9 4选择排序 9 5归并排序 9 6基数排序 第9章内部排序 9 1概述 1 什么是排序 排序 将数据表 a1 a2 an 调整为按关键字从小 大 到大 小 排列的过程 例如 初始序列 1 8 9 4 2 7 6无序排序之后 1 2 4 6 7 8 9有序 升序 2 排序的目的是什么 3 排序算法的好坏如何衡量 时间效率 排序速度 即排序所花费的全部比较次数和移动的次数 空间效率 占内存辅助空间的大小稳定性 若两个记录A和B的关键字值相等 但排序后A B的先后次序保持不变 则称这种排序算法是稳定的 便于查找 4 什么叫内部排序 什么叫外部排序 若待排序记录都在内存中 称为内部排序 若待排序记录一部分在内存 一部分在外存 则称为外部排序 注意 外部排序时 要将数据分批调入内存来排序 中间结果还要及时放入外存 显然外部排序要复杂得多 5 待排记录的数据类型定义如下 defineMAXSIZE1000 待排顺序表最大长度 typedefintKeyType 关键字类型为整数类型 typedefstruct KeyTypekey 关键字项InfoTypeotherinfo 其它数据项 RcdType 记录类型 typedefstruct RcdTyper MAXSIZE 1 r 0 闲置intlength 顺序表长度 SqList 顺序表类型 s SqLists MAXSIZE 1 0 9 2插入排序 插入排序的基本思想是 插入排序有多种具体实现算法 1 直接插入排序2 折半插入排序3 表插入排序4 希尔排序 每步将一个待排序的对象 按其关键码大小 插入到前面已经排好序的一组对象的适当位置上 直到对象全部插入为止 简言之 边插入边排序 保证子序列中随时都是有序的 1 直接插入排序 新元素插入到哪里 例1 关键字序列T 13 6 3 31 9 27 5 11 请写出直接插入排序的中间过程序列 13 6 3 31 9 27 5 11 6 13 3 31 9 27 5 11 3 6 13 31 9 27 5 11 3 6 13 31 9 27 5 11 3 6 9 13 31 27 5 11 3 6 9 13 27 31 5 11 3 5 6 9 13 27 31 11 3 5 6 9 11 13 27 31 在已形成的有序表中线性查找 并在适当位置插入 把原来位置上的元素向后顺移 最简单的排序法 例2 关键字序列T 21 25 49 25 16 08 请写出直接插入排序的具体实现过程 i 1 21 i 2 i 3 i 5 i 4 i 6 25 25 25 49 49 49 25 49 16 16 08 49 解 假设该序列已存入一维数组V 7 中 将V 0 作为缓冲或暂存单元 Temp 则程序执行过程为 初态 16 25 21 16 完成 从上面的演示可以得到其具体算法 为什么 注意其变化 稳定 voidInsertionSort SqList i if L r i key L r i 1 key InsertSort L r 0 L r i 复制为监视哨for j i 1 L r 0 key L r j key j L r j 1 L r j 记录后移L r j 1 L r 0 插入到正确位置 这个语句的位置和前面演示一致吗 算法评价时间复杂度若待排序记录按关键字从小到大排列 正序 关键字比较次数 记录移动次数 若待排序记录按关键字从大到小排列 逆序 关键字比较次数 记录移动次数 若待排序记录是随机的 取平均值关键字比较次数 记录移动次数 T n O n 空间复杂度 S n O 1 稳定性 稳定 例9 3 有待排关键字序列如下 49 66 35 76 25 85 76 32利用直接插入排序算法进行排序 考察它的稳定性 A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 初始状态 49 66357625857632 第1次扫描 4966 第2次扫描 354966 第3次扫描 35496676 第4次扫描 2535496676 第5次扫描 253549667685 第6次扫描 25354966767685 第7次扫描 2532354966767685 最终结果 2532354966767685 2 折半插入排序 在已形成的有序表中折半查找 并在适当位置插入 把原来位置上的元素向后顺移 新元素插入到哪里 1436495280 5861239775 i low high m m low low m high 14364952586180 239775 i low high m high m high m low 例如 再如 插入位置 L r L r 插入位置hight 1 voidBiInsertionSort SqList L BInsertSort 在L r 1 i 1 中折半查找插入位置 for i 2 i L length i for L r 0 L r i 将L r i 暂存到L r 0 for j i 1 j high 1 j L r j 1 L r j 记录后移 L r high 1 L r 0 插入 hight 1或low low 1 high i 1 while low high m low high 2 折半 if L r 0 key L r m key high m 1 插入点在低半区elselow m 1 插入点在高半区 在L r 1 i 1 中折半查找插入位置 是否可以考虑设计一个 黄金分割 插入算法 程序中的47题 完成下列程序 并说出该算法所完成的功能 voidweizhisort structnoder n intn intlow high mid j i for i 2 i low j r j 1 r j r low r 0 习题 算法评价时间复杂度 空间复杂度 S n O 1 稳定性 稳定 T n O n 14364952586180 149775 i low high m high m high m low 再如 插入位置 L r 已知一组元素的关键字 46 74 16 53 14 26 40 38 86 65 27 34 利用直接插入排序法 写出每次向前面有序表插入一个元素后的排列结果 习题 46 74 16 53 14 26 40 38 86 65 27 34 46 74 16 53 14 26 40 38 86 65 27 34 16 46 74 53 14 26 40 38 86 65 27 34 16 46 53 74 14 26 40 38 86 65 27 34 14 16 46 53 74 26 40 38 86 65 27 34 14 16 26 46 53 74 40 38 86 65 27 34 14 16 26 40 46 53 74 38 86 65 27 34 14 16 26 38 40 46 53 74 86 65 27 34 14 16 26 38 40 46 53 74 86 65 27 34 14 16 26 38 40 46 53 65 74 86 27 34 14 16 26 27 38 40 46 53 65 74 86 34 14 16 26 27 34 38 40 46 53 65 74 86 3 表插入排序 静态链表排序 基本思想 表插入排序的基本思想 是在记录的存储结构里增加一个指针域next 通过它的链接 让记录按照关键字的大小加以排列 避免排序中的记录移动 55 Ar 1 44 Ar 2 72 Ar 3 68 Ar 4 36 Ar 5 84 Ar 6 41 Ar 7 1 1 1 1 1 1 1 key next 1 head 例如 把记录存放在一维数组Ar里 初始时所有元素的next域都为 1 head总是包含关键字最小的那个记录的下标 初始时指向第1个元素 3 表插入排序 静态链表排序 开始 根据head里的1 用Ar 2 的key与Ar 1 的key比较 由于44 55 因此head应调整为2 Ar 2 的next应指向1 这样一步步做下去 如图所示 由head知道最小关键字是Ar 5 里的记录 然后通过各自的next域知道后面是Ar 7 继续下去是Ar 2 Ar 1 Ar 4 Ar 3 最大的是Ar 6 里的记录 算法评价时间复杂度 空间复杂度 采用静态链表 每个单元增加的辅助空间 稳定性 稳定 T n O n 4 希尔 shell 排序 又称缩小增量排序 基本思想 先将整个待排记录序列分割成若干子序列 分别进行直接插入排序 待整个序列中的记录 基本有序 时 再对全体记录进行一次直接插入排序 技巧 子序列的构成不是简单地 逐段分割 而是将相隔某个增量dk的记录组成一个子序列 让增量dk逐趟缩短 例如依次取5 3 1 直到dk 1为止 优点 让关键字值小的元素能很快前移 且序列若基本有序时 再用直接插入排序处理 时间效率会高很多 38 例 关键字序列T 49 38 65 97 76 13 27 49 55 04 请写出希尔排序的具体实现过程 初态 第1趟 dk 5 第2趟 dk 3 第3趟 dk 1 49 13 13 49 38 27 65 49 97 55 76 04 27 38 65 49 97 55 13 55 76 04 55 13 27 04 27 04 49 49 49 49 76 38 76 65 65 97 97 13 27 04 49 76 97 r i 算法分析 开始时dk的值较大 子序列中的对象较少 排序速度较快 随着排序进展 dk值逐渐变小 子序列中对象个数逐渐变多 由于前面工作的基础 大多数对象已基本有序 所以排序速度仍然很快 voidShellInsert SqList 插入 if 一趟Shell排序的算法 dk为步长因子 每趟排序的增量 和直接插入排序比较 看两者之间的关系 voidInsertionSort SqList 插入到正确位置 InsertionSort voidShellInsert SqList 插入 ShellSort 假设dk 1 voidShellSort SqList 一趟增量为dlta k 的插入排序 ShellSort 希尔排序算法 dk有规律 多次 t 调用一趟Shell排序 voidShellSort SqList 一趟增量为dlta k 的插入排序 ShellSort 希尔排序算法 dk无规律 多次 t 调用一趟Shell排序 算法评价时间复杂度 与增量有关 如果步长取上次的一半 空间复杂度 S n O 1 稳定性 不稳定 T n O n3 2 T n O nlog2n 9 3交换排序 两两比较待排序记录的关键码 如果发生逆序 即排列顺序与排序后的次序正好相反 则交换之 直到所有记录都排好序为止 交换排序的主要算法有 1 冒泡排序2 快速排序 交换排序的基本思想是 1 冒泡排序 假设在排序过程中 记录序列R 1 n 的状态为 第i趟冒泡排序 无序序列R 1 n i 1 有序序列R n i 2 n n i 1 无序序列R 1 n i 有序序列R n i 1 n 比较相邻记录 将关键字最大的记录交换到n i 1的位置上 冒泡排序排序过程将第一个记录的关键字与第二个记录的关键字进行比较 若为逆序r 1 key r 2 key 则交换 然后比较第二个记录与第三个记录 依次类推 直至第n 1个记录和第n个记录比较为止 第一趟冒泡排序 结果关键字最大的记录被安置在最后一个记录上对前n 1个记录进行第二趟冒泡排序 结果使关键字次大的记录被安置在第n 1个记录位置重复上述过程 直到 在一趟排序过程中没有进行过交换记录的操作 为止 例1 关键字序列T 21 25 49 25 16 08 请写出冒泡排序的具体实现过程 21 25 49 25 16 0821 25 25 16 08 4921 25 16 08 25 4921 16 08 25 25 4916 08 21 25 25 4908 16 21 25 25 49 初态 第1趟第2趟第3趟第4趟第5趟 voidBubbleSort1 SqList L intn BubbleSort for i 1 i n 1 i for j 1 j n i j if L r j 1 key L r j key Swap L r j L r j 1 思考 该算法有没有什么缺欠 L r 0 L r j 1 L r j 1 L r j L r j L r 0 例2 关键字序列T 08 16 49 21 25 25 请写出冒泡排序的具体实现过程 08 16 49 21 25 25 08 16 21 25 25 4908 16 21 25 25 4908 16 21 25 25 4908 16 21 25 25 4908 16 21 25 25 49 初态 第1趟第2趟第3趟第4趟第5趟 结论 上述算法在上例中 从第2趟开始就已经没有继续的必要了 voidBubbleSort2 SqList 引入标志 1为有逆序 BubbleSort pd 0 for j 1 j n i j if L r j 1 key L r j key Swap L r j L r j 1 if pd 0 break pd 1 for i 1 i n 1 08 16 49 21 25 25 08 16 21 25 25 4908 16 21 25 25 4908 16 21 25 25 4908 16 21 25 25 4908 16 21 25 25 49 如果前面的所以元素都为正序 PD的值为0 只有至少一个逆序 PD才能不为0 算法描述 算法评价时间复杂度最好情况 正序 比较次数 n 1移动次数 0最坏情况 逆序 比较次数 移动次数 空间复杂度 S n O 1 稳定性 稳定 T n O n 思考 能否设计一个双向起泡排序算法 致使一趟排序之后 记录的无序序列R s t 将变为 R s 最小 R t 最大 初态 21 25 49 25 16 08第1趟21 25 25 16 08 49 08 21 25 25 16 49 第2趟08 21 25 16 25 49 08 16 21 25 25 49 第3趟08 16 21 25 25 49 08 16 21 25 25 49 voiddbubble 注意其中b 0和b 1的作用 已知一组元素的关键字 46 74 16 53 14 26 40 38 86 65 27 34 利用冒泡法排序法 写出前三次排序后的排列结果 习题 原有序列 46 74 16 53 14 26 40 38 86 65 27 34第一次 46 16 53 14 26 40 38 74 65 27 34 86第二次 16 46 14 26 40 38 53 65 27 34 74 86第三次 16 14 26 40 38 46 53 27 34 65 74 86 2 快速排序 思路 找一个记录 以它的关键字作为 轴 凡其关键字小于轴的记录均移动至该记录之前 反之 致使一趟排序之后 记录的无序序列R s t 将分割成两部分 R s i 1 和R i 1 t 且R k key R i key R j key s k i 1 枢轴 i 1 j t 思路 找一个记录 以它的关键字作为 轴 凡其关键字小于轴的记录均移动至该记录之前 反之 凡关键字大于枢轴的记录均移动至该记录之后 s t low high 设L r s 52为枢轴 high 23 low high low 例如 L r 0 52 low high high high low 52 1 将L r high key和枢轴的关键字进行比较 要求L r high key 枢轴的关键字否则与枢轴元素互换 52 2 将L r low key和枢轴的关键字进行比较 要求L r low key 枢轴的关键字否则与枢轴元素互换 80 52 14 52 可见 经过 一次划分 将关键字序列52 49 80 36 14 58 61 97 23 75调整为 23 49 14 36 52 58 61 97 80 75 在调整过程中 设立了两个指针 low和high 它们的初值分别为 s和t 之后逐渐减小high 增加low 并保证L r high key 52 和L r low key 52 否则进行记录的 交换 intPartition SqList L intlow inthigh Partition L r 0 L r low pivotkey L r low key 枢轴 while low high while low pivotkey high 从右向左搜索 L r low L r high while low high 从左向右搜索 L r high L r low L r low L r 0 returnlow 一趟快速排序算法 s t low high 设L r s 52为枢轴 high 23 low high low 例如 L r 0 52 low high high high low 52 1 将L r high key和枢轴的关键字进行比较 要求L r high key 枢轴的关键字否则与枢轴元素互换 52 2 将L r low key和枢轴的关键字进行比较 要求L r low key 枢轴的关键字否则与枢轴元素互换 80 52 14 52 voidQSort Sqlist L intlow inthigh 对记录序列L r low high 进行快速排序if low high 长度大于1 QSort pivotloc Partition L low hight 对L r low high 进行一次划分 QSort L low pivotloc 1 对低子序列递归排序 QSort L pivotloc 1 high 对高子序列递归排序 voidQuickSort SqList L Qsort L 1 L length 快速排序的递归算法 例 以关键字序列 256 301 751 129 937 863 742 742 076 438 为例 写出执行快速算法的各趟排序结束时 关键字序列的状态 原始序列 256 301 751 129 937 863 742 742 076 438 快速排序 第1趟第2趟第3趟第4趟 256 301 751 129 937 863 742 742 076 438 076 129 256 751 937 863 742 742 301 438 要求模拟算法的实现步骤 256 076 301 129 751 256 076 129 256 438 301 742 742 742 863 937 751 076 129 256 438 301 742 742 751 863 937 076 129 256 301 301 742 742 751 863 937 438 076 129 256 301 438 742 742 751 863 937 用快速排序算法对数据表从小到大进行排序 A 12 5 4 19 25 1 34 7 10 23 8 5 9 3交换排序 快速排序实例 解 125419251347102385 5 x 12 12 5 4 19 8 25 23 10 1 34 7 7 1 5 4 8 10 5 12 19 23 25 34 4 5 1 5 7 8 10 12 25 23 19 34 1 4 5 5 8 7 10 12 19 25 23 34 算法评价时间复杂度最好情况 每次总是选到中间值作枢轴 T n O nlog2n 最坏情况 每次总是选到最小或最大元素作枢轴 T n O n 空间复杂度 需栈空间以实现递归最坏情况 S n O n 一般情况 S n O logn 稳定性 不稳定 一般也将其看成平均值 9 4选择排序 基本类型 基本思想 在待排的n i 1个记录中 依次选择关键字最小的记录作为有序序列的第i条记录 逐渐缩小范围直至全部记录选择完毕 第i趟 简单选择排序堆排序 一 简单选择排序 1 基本思想 有序序列L r 1 i 1 无序序列L r i n 第i趟简单选择排序 从中选出关键字最小的记录 有序序列L r 1 i 无序序列L r i 1 n 选择过程中记录不交换 选择后只和第i个记录交换 2 简单选择排序示例 初始态 4938659776132749 第1趟 13 38659776492749 第2趟 1327 659776493849 第3趟 132738 9776496549 第4趟 13273849 76976549 第5趟 1327384949 976576 第6趟 132738494965 9776 第7趟 1327384949657697 稳定 3 简单选择排序的算法描述 voidSelectSort SqList i 选择第i小的记录 并交换到位 SelectSort min SelectMinKey L i 在L r i L length 中选择关键字最小的记录 if min i L r min L r i 与第i个记录交换 3 简单选择排序的算法描述 voidSelectSort SqList i 选择第i小的记录 并交换到位 SelectSort min i for j i 1 j n j if L r j key L r min key min j if min i L r min L r i 与第i个记录交换 f if f j f min min j 49 13 min 表示待排序列中 最小值的下标 min i for j i 1 j n j if L r j key L r min key min j 算法评价时间复杂度T n O n 空间复杂度 S n O 1 稳定性 不稳定 如 初始态 494913 第1趟 13 4949 第2趟 134949 王 李 王 赵 李 周 王 赵 钱 孙 李 周 吴 郑 王 比赛过程示意图 郑 0 郑 李 9 4 2 堆排序 堆是满足下列性质的数列 r1 r2 rn 或 1 堆的定义 12 36 27 65 40 34 98 81 73 55 49 例如 是小顶堆 12 36 27 65 40 14 98 81 73 55 49 不是堆 小顶堆 大顶堆 判断起来比较麻烦 能否找到一个简单的方法 回忆 二叉树性质5 若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号 则对完全二叉树中任意一个编号为i的结点 1 若i 1 则该结点是二叉树的根 无双亲 否则 编号为 i 2 的结点为其双亲结点 2 若2i n 则该结点无左孩子 否则 编号为2i的结点为其左孩子结点 3 若2i 1 n 则该结点无右孩子结点 否则 编号为2i 1的结点为其右孩子结点 ri r2i r2i 1 若将该数列视作完全二叉树 则r2i是ri的左孩子 r2i 1是ri的右孩子 12 36 27 65 49 81 73 55 40 34 98 例如 是堆 14 不 9 4选择排序 堆排序 将此序列对应到编号的完全二叉树 则堆的定义可用完全二叉树中的有关术语解释为 每一结点均不大于 或不小于 其左右孩子结点的值 若序列 a1 a2 an 是堆 则堆顶 完全二叉树的根 必为序列中的最小或最大值 将根最大的堆称为大根堆 根最小的堆称为小根堆 2 堆排序 是利用堆的特性对记录序列进行排序的一种排序方法 堆排序 若进行增排序 则采用大根堆 如果初始序列是堆 则可通过反复执行如下操作而最终得到一个有序序列 输出根 即将根 第一个元素 与当前子序列中的最后一个元素交换 调整堆 将输出根之后的子序列调整为堆 如果初始序列不是堆 则首先要将其先建成堆 然后再按 1 的方式来实现 例如 升序输出 1 如何 筛选 2 如何 建堆 3 堆的类型定义 typedefSqListHeapType 堆采用顺序表表示之 4 堆排序需解决的两个问题 1 筛选 指的是 对一棵左 右子树均为堆的完全二叉树 调整 根结点使整个二叉树也成为一个堆 98 81 49 73 55 64 12 36 27 40 例如 是大顶堆 12 但在98和12进行互换之后 它就不是堆了 因此 需要对它进行 筛选 98 12 81 73 64 12 98 比较 比较 筛选 完毕 上述过程是 自堆顶到叶子的筛选 voidHeapAdjust HeapType H ints intm 已知H r s m 中记录的关键字除H r s 之外 均满足堆的特征 本函数自上而下调整H r s 的关键字 使H r s m 也成为一个大顶堆 HeapAdjust rc H r s 暂存H r s for j 2 s j m j 2 j初值指向左孩子自上而下的筛选过程 H r s rc 将调整前的堆顶记录插入到s 堆的调整算法 if rc key H r j key break 再作 根 和 子树根 之间的比较 若 成立 则说明已找到rc的插 入位置s 不需要继续往下调整 H r s H r j s j 否则记录上移 尚需继续往下调整 if j m 左 右 子树根 之间先进行相互比较 令j指示关键字较大记录的位置 自上而下的筛选过程 2 建堆 通过反复调用筛选操作来实现 建堆过程要从下往上逐棵子树地进行筛选 即根的下标按照从n 2到1的次序将各子树调整为堆 如何由一个无序序列建成一个堆 2 建堆是一个从下往上进行 筛选 的过程 40 55 49 73 81 64 36 12 27 98 例如 排序之前的关键字序列为 12 36 81 73 49 98 81 73 55 现在 左 右子树都已经调整为堆 最后只要调整根结点 即使整个二叉树变成 堆 98 49 40 64 36 12 27 建大顶堆 再例 含8个元素的无序序列的建堆过程 49 38 65 97 76 13 27 50 建小顶堆 小顶堆 从第4个记录开始 算法评价时间复杂度 最坏情况下T n O nlog2n 空间复杂度 S n O 1 稳定性 不稳定 归并排序通常采用2 路归并排序 即 将两个位置相邻的记录有序子序列 归并为一个记录的有序序列 有序序列R l n 有序子序列R l m 有序子序列R m 1 n 这个操作对顺序表而言 是轻而易举的 9 5归并排序 归并排序归并 将两个或两个以上的有序表组合成一个新的有序表 叫 2 路归并排序排序过程设初始序列含有n个记录 则可看成n个有序的子序列 每个子序列长度为1两两合并 得到 n 2 个长度为2或1的有序子序列再两两合并 如此重复 直至得到一个长度为n的有序序列为止 例 初始关键字 49 38 65 97 76 13 27 一趟归并后 3849 6597 1376 27 二趟归并后 38496597 132776 三趟归并后 13273849657697 算法评价时间复杂度 T n O nlogn 空间复杂度 S n O n 稳定性 稳定 15 18 25 60 18 75 100 23 64 8 150 解 1518 2560 1875 23100 864 150 15182560 182375100 864150 15181823256075100 864150 81518182325606475100150 9 5归并排序 二路归并示例 79 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 01234 49 13 65 97 76 7 80 A B 01234567 C i j k 80 01234 49 13 65 97 76 7 80 A B 01234567 C i j k 7 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 81 01234 49 13 65 97 76 7 80 A B 01234567 C 7 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 82 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 83 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 49 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 84 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 49 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 85 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 49 65 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 86 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 49 65 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 87 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 49 65 76 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 88 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 49 65 76 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 89 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 49 65 76 80 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 90 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 49 65 76 80 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 91 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 49 65 76 80 至此B表的元素都已移入C表 只需将A表的剩余部分移入C表即可 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 92 01234 49 13 65 97 76 7 80 A B 01234567 C 7 13 49 65 76 80 至此B表的元素都已移入C表 只需将A表的剩余部分移入C表即可 97 将下属两个已排序的顺序表合并成一个有序表 顺序比较两者的相应元素 小者移入另一表中 反复如此 直至其中任一表都移入另一表为止 一 多关键字的排序 n个记录的序列 R1 R2 Rn 对关键字 Ki0 Ki1 Kid 1 有序是指 其中 K0被称为 最主 位关键字 Kd 1被称为 最次 位关键字 对于序列中任意两个记录Ri和Rj 1 i j n 都满足下列 词典 有序关系 Ki0 Ki1 Kid 1 Kj0 Kj1 Kjd 1 9 6基数排序 基数排序是一种借助 多关键字排序 来实现 单关键字排序 的排序 包括 多关键字排序 链式基数排序 例如 对52张扑克牌按以下次序排序 2 3 A 2 3 A 2 3 A 2 3 A两个关键字 花色 面值 2 3 A 并且 花色 地位高于 面值 实现多关键字排序的两种作法 2 最低位优先LSD法 1 最高位优先MSD法 先对K0进行排序 并按K0的不同值将记录序列分成若干子序列之后 分别对K1进行排序 依次类推 直至最后对最次位关键字排序完成为止 先对Kd 1进行排序 然后对Kd 2进行排序 依次类推 直至对最主位关键字K0排序完成为