中国地质大学（武汉）：《数据结构和VC编程》课程教学资源（课件讲稿）第七章 排序

第7章排序 定义待排序的记录的类型如下： #define N 50 /心待排序序列中记录的最大个数， 可根据需要定义*/ typedef struct node int key; /~表示排序关键字*/ elemtype otheritem; *代表待排序记录中的 其他所有数据项*/ RECTYPE; PT PRESS 续下一

第7章 排 序 定义待排序的记录的类型如下： #define N 50 /*待排序序列中记录的最大个数， 可根据需要定义*/ typedef struct node { int key; /*表示排序关键字*/ elemtype otheritem; /*代表待排序记录中的 其他所有数据项*/ }RECTYPE;

7.1内排序 7.1.1内排序的分类 按排序过程中所需的工作量来分（设待排序 结点总数为n) 2、 按排序过程中所依据的不同原则来分 3、 按是否改变结点的物理位置分 PT PRESS 退出 然东续下一配

7.1内排序 7．1．1内排序的分类 1、 按排序过程中所需的工作量来分(设待排序 结点总数为n) 2、 按排序过程中所依据的不同原则来分 3、 按是否改变结点的物理位置分 退出

R[1] R[2] R[3] R[1] R[2] R[3] 89 37 41 89 37 41 。 i 1 2 3 i 1 2 3 [叼 1 2 3 [闭 2 3 1 辅助地址表 c 1 1 1 c[] 3 2 计数数组 (a)排序前 (b)排序后 图7-1 PT PRESS 然东续了一 n

图7-1

开始排序前：（mim,91),67,351,62,29,352, 72,46,31,47,25,73.… 第一趟：(min,67,91),351,62,29,352, 72,46,31,47,25,73. 第二趟：(min,351,67,91),62,29,352, 72,46,31,47,25,73.. 第三趟：(min,351,62,67,91),22,352, 72,46,31,47,25,73.… 第四趟：（mim,29,351,62,67,91),352; 72,46,31,47,25,73.… 第五趟：(min,29,351,352,62,67,91), 72,46,31,47,25,73.… 第六趟：(min,29,351,352,62,67,72, 91),46,31,47,25,73... PT PRESS

开始排序前：（min，91），67，351，62，29，352， 72，46，31，47，25，73…… 第 一 趟：（min，67，91），351，62，29，352， 72，46，31，47，25，73…… 第 二 趟：（min，351，67，91），62，29，352， 72，46，31，47，25，73…… 第 三 趟：（min，351，62，67，91），29，352， 72，46，31，47，25，73…… 第 四 趟：（min，29，351，62，67，91），352， 72，46，31，47，25，73…… 第 五 趟：（min，29，351，352，62，67，91）， 72，46，31，47，25，73…… 第 六 趟：（min，29，351，352，62，67，72， 91），46，31，47，25，73……

算法7.1 如书第206页所示 算法7.2 如书第207页所示 PT PRESS 然东续下一配 n

算法 7．1 如书第206页所示 算法 7．2 如书第207页所示

下面是一组插入排序中，辅助地址表]的变化实例 (括号内的部分代表有序子表的地址集合)： 0 1234 5 ri.key min 40 50 20 10 30 0 (1)2345初态 叮 0 (1 2) 第一趟，插入50 叫 0 (3 2） 第二趟，插入20 t 0 (4 2) 第三趟，插入10 3 5 2 第四趟，插入30 由辅助地址表得到排序结果为： rti]].key min 10 203040 50 算法7.3 如书第209页所示 PT PRESS 续下一

下面是一组插入排序中，辅助地址表t[i]的变化实例 （括号内的部分代表有序子表的地址集合）： i 0 1 2 3 4 5 r[i].key min 40 50 20 10 30 t[i] 0 （1） 2 3 4 5 初态 t[i] 0 （1 2 ） 第一趟，插入50 t[i] 0 （3 1 2 ） 第二趟，插入20 t[i] 0 （4 3 1 2 ） 第三趟，插入10 t[i] 0 4 3 5 1 2 第四趟，插入30 由辅助地址表得到排序结果为： r[t[i]].key min 10 20 30 40 50 算法 7．3 如书第209页所示

排序结束后，物理重排之前： 123456 77 rl].key35141242 2650 3117 t 32857146 i=1调整后： rll.key12141742 26353150 t叮 12357648 i=4 调整后： r[il.key1214172631354250 t训 12345678 算法7.4 如书第210页所示 PT PRESS 按续不一列

排序结束后，物理重排之前： i 1 2 3 4 5 6 7 7 r[i].key 35 14 12 42 26 50 31 17 t[i] 3 2 8 5 7 1 4 6 i=1 调整后： r[i].key 12 14 17 42 26 35 31 50 t[i] 1 2 3 5 7 6 4 8 i=4 调整后： r[i].key 12 14 17 26 31 35 42 50 t[i] 1 2 3 4 5 6 7 8 算法 7．4 如书第210页所示

7.1.3交换排序 1、直接交换排序 算法7.5 如书第211页所示 PT PRESS 按续不一列 n

7．1．3 交换排序 1、 直接交换排序 算法 7．5 如书第211页所示

1、对直接交换排序的改进考虑： 算法7.6 如书第212页所示 PT PRESS 然东续下一配 n

1、对直接交换排序的改进考虑： 算法 7．6 如书第212页所示

74 ∥91 91 91 91 91 91 91 91 18 74 74 83 83 83 83 83 83 18 80 74 80 80 80 80 80 1 80 18 80 74 79 79 79 79 98 18 79 74 7 74 74 72 为6行9wf出心88 93 79 22 72 67 67 67 67 25736 2 47 25 62 62 5716292 47 316 36 47 316 47 47 31 31 46 . 46 62 46 35 67 62 29 35 31 2925 292 62j 35 29 29 3 3 25 25 25 . 5 18 18 18 18 67 13 13 13 13 13 13 13 图7-2 PT PRESS

图7-2