第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）， 请写出直接插入排序的中间过程序列。 注：方括号[ ]中为已排序记录的关键字，下划横线的关键字 表示它对应的记录后移一个位置
2、C语言程序 void InsertSort(Data Type all, int n) /*用直接插入法对a[0]-a[n-1排序* f int i,]; Data Type temp for(=0;i-1 & temp. key <all key)i aj+1=all alj+1= temp
6 2、C语言程序 void InsertSort(DataType a[], int n) /*用直接插入法对a[0]--a[n-1]排序*/ { int i, j; DataType temp; for(i = 0; i -1 && temp.key < a[j].key) { a[j+1] = a[j]; j--; } a[j+1] = temp; } }
7
7 void main(void) { DataType test[6]={64,5,7,89,6,24}; int i, n = 6; SeqList myList; ListInitiate(&myList); for(i = 0; i typedef int KeyType; typedef struct {KeyType key; } DataType; #define MaxSize 100 #include "SeqList.h
3、直接插入排序算法分析 (1)时间效率:因为在最坏情况下,所有元素的比较次数总 和为(0+1+…+n-1)→0(n2)。其他情况下也要 考虑移动元素的次数。故时间复杂度为o(n2) (2)空间效率:仅占用1个缓冲单元0(1) (3)算法的稳定性:稳定 希尔(she11)排序(又称缩小增量排序 1、基本思想:把整个待排序的数据元素分成若干个小组,对同 小组内的数据元素用直接插入法排序;小组的个数逐次缩小, 当完成了所有数据元素都在一个组内的排序后排序过程结束。 2、技巧:小组的构成不是简单地“逐段分割”,而是将相隔某 个增量dk的记录组成一个小组,让增量dk逐趟缩短(例如依次取 5,3,1),直到dk=1为止。 3、优点:让关键字值小的元素能很快前移,且序列若基本有序 时,再用直接插入排序处理,时间效率会高很多
8 (1)时间效率： 因为在最坏情况下，所有元素的比较次数总 和为（0＋1＋…＋n-1)→O(n2 )。其他情况下也要 考虑移动元素的次数。 故时间复杂度为O(n2 ) (2)空间效率：仅占用1个缓冲单元——O（1） (3)算法的稳定性：稳定 3、直接插入排序算法分析 二、希尔（shell）排序（又称缩小增量排序） 1、基本思想：把整个待排序的数据元素分成若干个小组，对同 一小组内的数据元素用直接插入法排序；小组的个数逐次缩小， 当完成了所有数据元素都在一个组内的排序后排序过程结束。 2、技巧：小组的构成不是简单地“逐段分割”，而是将相隔某 个增量dk的记录组成一个小组,让增量dk逐趟缩短（例如依次取 5,3,1），直到dk＝1为止。 3、优点：让关键字值小的元素能很快前移，且序列若基本有序 时，再用直接插入排序处理，时间效率会高很多
例2:设待排序的序列中有1个记录,它们的关键字序列T=(65, 34,25,87,12,38,56,46,14,77,92,23),请写出 希尔排序的具体实现过程 算法分析:开始时d的值较大,子序列中的对象较少,排序速度 较快;随着排序进展,d值逐渐变小,子序列中对象个数 逐渐变多,由于前面工作的基础,大多数记录已基本有序 所以排序速度仍然很快。 通常,d+1=d2(结果取整) 时间效率:O(m(log2n)2 空间效率:0(1)—因为仅占用1个缓冲单元 算法的稳定性:不稳定 下面给出希尔排序的具体实现过程:
9 例2：设待排序的序列中有12个记录，它们的关键字序列 T=(65， 34，25，87，12，38，56，46，14，77，92，23），请写出 希尔排序的具体实现过程。 算法分析：开始时d 的值较大，子序列中的对象较少，排序速度 较快；随着排序进展，d 值逐渐变小，子序列中对象个数 逐渐变多，由于前面工作的基础，大多数记录已基本有序， 所以排序速度仍然很快。 通常，di+1=di/2 (结果取整） 时间效率：O(n(log2n)2 ) 空间效率：O（1）——因为仅占用1个缓冲单元 算法的稳定性：不稳定 下面给出希尔排序的具体实现过程：
第1趟(d=6) 77 结果序列5 12 第2趟(d=3) 6546 结果序列56 14 46 87 92 (b 第3趟(d=1)【511684274625893 结果序列12 (c
10 65 34 25 87 12 38 56 46 14 77 92 23 结果序列 56 34 14 77 12 23 65 46 25 87 92 38 56 34 14 77 12 23 65 46 25 87 92 38 结果序列 56 12 14 65 34 23 77 46 25 87 92 38 56 12 14 65 34 23 77 46 25 87 92 38 结果序列 12 14 23 25 34 38 46 56 65 77 87 92 (a) (b) (c) 第1趟 (d=6) 第2趟 (d=3) 第3趟 (d=1)