第9章排序 9.1排序的基本概念 9.2插入排序 9.3选择排序 94交换排序 9.5归并排序 9.6基数排序 9.7性能比较
1 9.1 排序的基本概念 9.2 插入排序 9.3 选择排序 9.4 交换排序 9.5 归并排序 9.6 基数排序 9.7 性能比较 第9章 排序
9.1排序的基本概念 1排序:将一组杂乱无章的数据按一定的规律顺次排列 起来的过程。 存放在数据表中 按关键字排序 2.排序的目的:便于查找。 3.排序算法好坏的衡量标准: (1)时间复杂度—它主要是分析记录关键字的比较次数和记 录的移动次数 (2)空间复杂度—算法中使用的内存辅助空间的多少。 (3)稳定性—若两个记录A和B的关键字值相等,但排序后A、 B的先后次序保持不变,则称这种排序算法是稳定的。 4、排序的种类:分为内部排序和外部排序两大类 若待排序记录都在内存中,称为内部排序;若待排序 记录一部分在內存,一部分在外存,则称为外部排序。 注:外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外 存,显然外部排序要复杂得多
2 9.1排序的基本概念 1.排序: 将一组杂乱无章的数据按一定的规律顺次排列 起来的过程。 存放在数据表中 按关键字排序 2. 排序的目的：便于查找。 3.排序算法好坏的衡量标准： (1)时间复杂度—— 它主要是分析记录关键字的比较次数和记 录的移动次数。 (2)空间复杂度——算法中使用的内存辅助空间的多少。 (3)稳定性——若两个记录A和B的关键字值相等，但排序后A、 B的先后次序保持不变，则称这种排序算法是稳定的。 4、排序的种类：分为内部排序和外部排序两大类。 若待排序记录都在内存中，称为内部排序；若待排序 记录一部分在内存，一部分在外存，则称为外部排序。 注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外 存，显然外部排序要复杂得多
5.待排序记录在内存中怎样存储和处理? ①顺序排序排序时直接移动记录; ②链表排序排序时只移动指针 ③地址排序排序时先移动地址,最后再移动记录 注:地址排序中可以增设一维数组来专门存放记录的地址。 6.内部排序的算法有哪些? 按排序的规则不同,可分为5类: 插入排序、交换排序、选择排序、归并排序、基数排序 按排序算法的时间复杂度不同,可分为3类 令简单的排序算法:时间效率低,O(n2) 先进的排序算法:时间效率高,O(mog2n) 基数排序算法:时间效率高,Od×n) d=关键字的位数(长度)
3 5.待排序记录在内存中怎样存储和处理？ ① 顺序排序——排序时直接移动记录； ② 链表排序——排序时只移动指针； ③ 地址排序——排序时先移动地址，最后再移动记录。 注：地址排序中可以增设一维数组来专门存放记录的地址。 6. 内部排序的算法有哪些？ ——按排序的规则不同，可分为5类： 插入排序、交换排序、选择排序、归并排序、基数排序 ——按排序算法的时间复杂度不同，可分为3类： ❖ 简单的排序算法：时间效率低，O(n2 ) ❖ 先进的排序算法: 时间效率高，O( nlog2n ) ❖ 基 数 排 序 算法：时间效率高，O( d×n) d＝关键字的位数(长度)
9.2插入排序 插入排序的基本思想是:每步将一个待排序的对象,按 其关键码大小,插入到前面已经排好序的一组对象的适当位 置,直到对象全部插入为止。 简言之,边插入边排序,保证子序列中随时都是排好序的。 常用的插入排序有:直接插入排序和希尔排序两种。 直接插入排序 最简单的排序法! 1、其基本思想是: 顺序地把待排序的数据元素按其关键字值的大小插入到已排 序数据元素子集合的适当位置
4 9.2 插入排序 插入排序的基本思想是：每步将一个待排序的对象，按 其关键码大小，插入到前面已经排好序的一组对象的适当位 置上，直到对象全部插入为止。 简言之，边插入边排序，保证子序列中随时都是排好序的。 常用的插入排序有：直接插入排序和希尔排序两种。 一、直接插入排序 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,,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,2731 注:方括号[|中为已排序记录的关键字,下划横线的关键字 表示它对应的记录后移一个位置
5 初始关键字序列：【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】 例1：关键字序列T=（13，6，3，31，9，27，5，11）， 请写出直接插入排序的中间过程序列。 注：方括号[ ]中为已排序记录的关键字，下划横线的关键字 表示它对应的记录后移一个位置