第九章内部排序 甚本概念 插入排序 快速排序 ·选择排序 归并排序 甚数排序
第九章 内部排序 • 基本概念 • 插入排序 • 快速排序 • 选择排序 • 归并排序 • 基数排序
9.1基本概念 设含有m个记录的文件{R1R2,Rn},其相应的关 键字为{K1,K2,,K},将记录按关键字值非递减(或 非递增)顺序排列的过程,称为排序。 对所有的K=K(,若排序前R领先于R排序后 R仍领先于R1,则称该排序方法是稳定的,反之,称 为不稳定的。 稳定性是对序列中的两个相同的关键字在初始序 列和最终有序序列中相对位置(即领先关系)是否 变化
9.1 基本概念 设含有n个记录的文件{R1,R2,...,Rn}，其相应的关 键字为{K1,K2,...,Kn}，将记录按关键字值非递减(或 非递增)顺序排列的过程，称为排序。 对所有的Ki=Kj (i≠j),若排序前Ri领先于Rj,排序后 Ri仍领先于Rj,则称该排序方法是稳定的，反之，称 为不稳定 的。 稳定性是对序列中的两个相同的关键字在初始序 列和最终有序序列中相对位置（即领先关系）是否 变化
9.1基本概念 内部摊序:待排序文件的全部记录存放在内存 进行的排序,称为内部排序。 外部排序:排序过程中需要进行内外存数据交 换的排序,称为外部排序
9.1 基本概念 内部排序：待排序文件的全部记录存放在内存 进行的排序，称为内部排序。 外部排序：排序过程中需要进行内外存数据交 换的排序，称为外部排序
9.1基本概念 内排序分类 按排序过程依据的原则分为:插入排序 交换排序 选择排序 归并排序 计数排序 按排序过程所需的工作量分:简单排序O(n2) 先进排序O(mogm 基数排序O(d.n)
9.1 基本概念 内排序分类 按排序过程依据的原则分为：插入排序 交换排序 选择排序 归并排序 计数排序 按排序过程所需的工作量分：简单排序 O(n2 ) 先进排序 O(nlogn) 基数排序 O(d．n)
92插入排序 直接插入排序(最简单的排序方法) 1.基本思想:依次将每个待排序的记录插入到一个有 序子文件的合适位置(有序子文件记录数增1) 例如:已有待排序文件为:38,65,49,76,97 首先将文件的第一个记录,视为有序文件,然后从第 二个记录开始,直到最后一个记录,依次将他们插 入到有序文件的合适位置
9.2 插入排序 一. 直接插入排序(最简单的排序方法） ⒈ 基本思想：依次将每个待排序的记录插入到一个有 序子文件的合适位置(有序子文件记录数增1) 例如：已有待排序文件为：38，65，49，76，97 首先将文件的第一个记录，视为有序文件，然后从第 二个记录开始，直到最后一个记录，依次将他们插 入到有序文件的合适位置
92插入排序 2.直接插入排序算法 void Insertsort(sqlist &l); {for(i=2;i<=n;i++) dro=; j=i1;/r[1!~ri1为有序子文件* while(r[.<rljlkey) {rj+ 1=rail;jj-1};/确定插入位置并移动 r|i+1l=r10; 3//strainsort
9.2 插入排序 ⒉ 直接插入排序算法 void InsertSort(SqList &L)； {for( i=2;i<= n;i++) { r[0]=r[i]; j=i-1; /*r[1]～r[i-1]为有序子文件*/ while (r[0].key＜r[j].key) { r[j+1]=r[j]; j=j-1 }; /*确定插入位置并移动*/ r[j+1]=r[0]; } }//strainsort
92插入排序 3.算法分析 (1)空间上,只需i,j两个整型变量和一个记录的辅助空间r0],r0 作为“监视哨”,控制待插入元素相对于有序子文件为最小时 WHE循环的结束,同时也用于暂存待插入元素。 (2)时间上,只包含比较关键字和移动记录两种操作。 ①比较次数: 1/.当待初始文件按关键字递增有序(正序时: a对每个记录只进行一次比较,整个排序过程共 进行了∑1=n-1次比较(最少); 2 b每个记录都要进行r移到r0和r0移到r+1两次移动, 因此共移动2(n-1)次(最少)
9.2 插入排序 ⒊ 算法分析 ⑴ 空间上，只需i，j两个整型变量和一个记录的辅助空间r[0], r[0] 作为“监视哨” ，控制待插入元素相对于有序子文件为最小时 WHILE循环的结束，同时也用于暂存待插入元素。 ⑵ 时间上，只包含比较关键字和移动记录两种操作。 ①比较次数: 1/. 当待初始文件按关键字递增有序(正序)时： a.对每个记录只进行一次比较，整个排序过程共 n 进行了∑1=n-1次比较(最少)； i=2 b.每个记录都要进行r[i]移到r[0]和r[0]移到r[j+1]两次移动， 因此共移动2(n-1)次(最少)
92插入排序 2.当待排序文件按关键字非递增有序(逆序)时 ①记录r(i=2,3,n)均要和前i-1个记录及r进行比较,整个 排序过程共进行了 i=(n+2)(n-1)2次比较最多); ②移动记录次数:每个记录都要进行r移动到r0和r0移动 到rj+1两次移动,另外当 rl.key< rij- key时,还将rj移 动到r+1,所以,当初始文件为正序时,移动记录次数最 少为2(n-1)次,当初始文件为逆序时移动记录次数最多为 (-1)+2(m1)(n+4(m1/2次(最多
9.2 插入排序 2/. 当待排序文件按关键字非递增有序(逆序)时 ① 记录r[i](i=2,3,...n)均要和前i-1个记录及r[0]进行比较，整个 排序过程共进行了 n ∑ i=(n+2)(n-1)/2次比较(最多)； i=2 ② 移动记录次数：每个记录都要进行r[i]移动到r[0]和r[0]移动 到r[j+1]两次移动，另外当r[i].key＜r[j].key时，还将r[j]移 动到r[j+1]，所以，当初始文件为正序时，移动记录次数最 少为2（n-1）次，当初始文件为逆序时移动记录次数最多为 n ∑ (i-1)+2(n-1)=(n+4)(n-1)/2次(最多)。 i=2
92插入排序 (3)结论 1.直接插入排序的效率与待排文件的关键字排列有关; 2/.直接插入排序的时间复杂度为O(m2); 3/.直接插入排序是稳定的这一点由过程中WHE语 句的条件“<”保证的)。 void InsertSort(sqlist&L); {for(i=2;i<=n;i++) {r|0=r[il: while(r[o- key<rlilkey frlj+l=rljl; j=j-1;3 3//strainsort
9.2 插入排序 ⑶ 结论 1/. 直接插入排序的效率与待排文件的关键字排列有关； 2/. 直接插入排序的时间复杂度为O(n2 )； 3/. 直接插入排序是稳定的(这一点由过程中WHILE语 句的条件“＜”保证的)。 void InsertSort(SqList &L)； {for( i=2;i<= n;i++) { r[0]=r[i]; j=i-1; while (r[0].key＜r[j].key) { r[j+1]=r[j]; j=j-1; }; r[j+1]=r[0];} }//strainsort
92插入排序 二.折半插入排序 由于是在有序子文件中确定插入的位置,因此 可用折半查找来代替直接插入排序法中的顺序查找, 从而可减少比较次数
9.2 插入排序 二. 折半插入排序 由于是在有序子文件中确定插入的位置，因此 可用折半查找来代替直接插入排序法中的顺序查找， 从而可减少比较次数