第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