《数据结构》课程教学资源：第十一章 内排序

第十一章 排序 11排⑧的害惑 11.2围久绑感 13换排愿 114选择排感 115详排感 116含数排感 117各种的排序法的匙较和择

1 11.6 基数排序 11.1 排序的基本概念 11.2 插入排序 11.3 交换排序 11.4 选择排序 11.5 归并排序 11.7 各种内排序方法的比较和选择 第十一章 内排序

11排序的基本概念 排序是计算机内经常进行的一种操作,其目的 是将一组“无序”的记录序列调整为“有序”的 记录序列。 所谓排就是要整理表中的记录使之按关键字 递增(或递减)有序排列。其确切定义如下 物入:n个记录,R,R1…,Rn1其相应的关键字 分别为kk1,…,kn1 轴出:RnR12,Rn1,使得ko≤k1≤≤kn1 2 (或k≥k1≥…≥kn1)

2 所谓排序,就是要整理表中的记录,使之按关键字 递增(或递减)有序排列。其确切定义如下： 输入：n个记录,R0 ,R1 ,…,Rn-1 ,其相应的关键字 分别为k0 ,k1 ,…,kn-1。 输出：Rio,Ri1 ,…,Ri,n-1 ,使得ki0≤ki1≤…≤ki,n-1 (或ki0≥ki1≥…≥ki,n-1 )。 排序是计算机内经常进行的一种操作，其目的 是将一组“无序”的记录序列调整为“有序”的 记录序列。 11.1 排序的基本概念

当待排序记录的关键字均不相同时排序的结果 是惟一的否则排序的结果不一定惟 如果待排序的表中存在有多个关键字相同的记 录经过排序后这些具有相同关键字的记录之间的 相对次序保持不变则称这种排序方法是稳定的; 反之若具有相同关键字的记录之间的相对次序发 生变化则称这种排序方法是不稳定的 注意: 排序算法的稳定性是针对所有输入实例而言 的。即在所有可能的输入实例中,只要有一个实 例使得算法不满足稳定性要求,则该排序算法就 是不稳定的

3 当待排序记录的关键字均不相同时,排序的结果 是惟一的,否则排序的结果不一定惟一。 如果待排序的表中,存在有多个关键字相同的记 录,经过排序后这些具有相同关键字的记录之间的 相对次序保持不变,则称这种排序方法是稳定的； 反之,若具有相同关键字的记录之间的相对次序发 生变化,则称这种排序方法是不稳定的。 注意： 排序算法的稳定性是针对所有输入实例而言 的。即在所有可能的输入实例中，只要有一个实 例使得算法不满足稳定性要求，则该排序算法就 是不稳定的

内部排序:若整个排序过程不需要访问外存便能 完成,则称些类排序问题为内部排房。 外部排序待排序纪录的数量很大,以致内 次不能容纳全部纪录,在排序过程中尚需对外存 进行访问的排序过程。 内新排的方法 内部排序的过程是一个逐步扩大记录的有序序 列长度的过程。 有序序列区无序序列区 一趟排序 有序序列区无序序列区 逐步扩大记录有序序列长度的方法大致有下列几类 4入类进择类交换类归并类其他方法

4 ➢内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序 列长度的过程。 有序序列区 无 序 序 列 区 一趟排序 有 序 序列区 无 序 序列区 逐步扩大记录有序序列长度的方法大致有下列几类： 插入类 选择类 交换类 归并类 其他方法 内部排序：若整个排序过程不需要访问外存便能 完成，则称此类排序问题为内部排序。 外部排序：待排序纪录的数量很大，以致内存一 次不能容纳全部纪录，在排序过程中尚需对外存 进行访问的排序过程

1.插入类 将无序子序列中的一个或几个记录“插入 到有序序列中,从而增加记录的有序子序列的 长度。 2.选择类 从记录的无序子序列中“涉却关键字最小或 最大的记录,并将它加入到有序子序列中,以此 方法增加记录的有序子序列的长度。 3.交换类 通过“交”无序序列中的记录从而得到其中 关键字最小或最大的记录,并将它加入到有序子 序列中,以方法增加记录的有序子序列的长度

5 1.插入类 将无序子序列中的一个或几个记录“插入” 到有序序列中，从而增加记录的有序子序列的 长度。 3.交换类 通过“交换”无序序列中的记录从而得到其中 关键字最小或最大的记录，并将它加入到有序子 序列中，以此方法增加记录的有序子序列的长度。 2.选择类 从记录的无序子序列中“选择”关键字最小或 最大的记录，并将它加入到有序子序列中，以此 方法增加记录的有序子序列的长度

4归类 通过“归芹两个或两个以上的记录有序 子序列,逐步增加记录的有序序列的长度。 5.真他方法 112插入排序 入排序的基本思想:每次将一个待排序的 记录,按其关键字大小插入到前面已经排好序的 海有序表中,直到全部记录插入完成为止 6

6 4.归并类 通过“归并”两个或两个以上的记录有序 子序列，逐步增加记录的有序序列的长度。 5.其他方法 11.2 插入排序 插入排序的基本思想：每次将一个待排序的 记录，按其关键字大小插入到前面已经排好序的 有序表中，直到全部记录插入完成为止

11.2.1直入排房 一趟直插入排序的基本思想: 有序序列R01无序序列Rin1l Ri 有序序列R[无序序列R+n1 实现“一趟入排房”可分三步进行: 在R|0.1中查找R[的插入位置 R[0.]≤R[<R[i+1.i-1 2将Rj+1i-1中的所有记录均后移一个位置; 73将复制到R+的位置上

7 11.2.1 直接插入排序 • 一趟直接插入排序的基本思想： 有序序列R[0..i-1] 无序序列R[i,..n-1] R[i] 有序序列R[0..i] 无序序列R[i+1,..n-1] • 实现“一趟插入排序”可分三步进行： 1. 在R[0..i-1]中查找R[i]的插入位置; R[0..j] ≤R[i] <R[j+1..i-1] 2. 将R[j+1..i-1]中的所有记录均后移一个位置; 3. 将R[i]复制到R[j+1]的位置上

11.2.1直入排房 利用顺序查实现“在R.i-1中查找R[的插入位置 void Insertsort(RecType ri,int n) i int i, j; RecType temp; for(i=l;=0 & temp. key<riil. key {Ri+l|=Rljl;记录后移 Ri计+1}=temp;/插入到正确位置

8 11.2.1 直接插入排序 利用顺序查找实现“在R[0..i-1]中查找R[i]的插入位置” void InsertSort(RecType R[],int n) { int i, j; RecType temp; for (i=1;i=0 && temp.key<R[j].key) { R[j+1]=R[j]; //记录后移 j--; } R[j+1]=temp; //插入到正确位置 } }

void InsertSort(Rec Type RIl,int n) i int i, j; Rec Type temp; for(i=l;i=0&& temp. key<rii- key) iRI+l=rll; j-;) RIj+l=temp; j temp 0123456 49386597761327 i=13838496597761327 i=265(3849)6597761327 i=397(384965)97761327 =476(38496576971327 i=513(133849657697)27 9 =627(13273849657697)

9 void InsertSort(RecType R[],int n) { int i, j; RecType temp; for (i=1;i=0 && temp.key<R[j].key) { R[j+1]=R[j]; j--; } R[j+1]=temp; } } 49 38 65 97 76 13 27 i=1 (49) 38 38 65 97 76 13 27 49 temp 38 j j 0 1 2 3 4 5 6 i=3 (38 49 65） 97 76 13 27 i=2 (38 49） 65 97 76 13 27 i=4 (38 49 65 97） 76 13 27 i=5 13 (13 38 49 65 76 97) 27 i=6 27 (13 27 38 49 65 76 97) 76 76 97 65 97

·算法评价 ◇时间复杂度 若待排序记录按关键字从小到大排列正序) 关键字比较次数:∑ 记录移动次数:2(n-1) 着待排序记录按关键字从大到小排列逆序) 关键字比较次数: l 2 通记录移动次数:∑(+2=10+1= i=1 若待排序记录是随机的,取平均值 T(n)=O(n2) ◇空间复杂度:S(m)=O() 10

10 • 算法评价 ❖时间复杂度 »若待排序记录按关键字从小到大排列(正序) 关键字比较次数： 1 1 1 1  = − − = n n i 记录移动次数：2（n-1） 若待排序记录按关键字从大到小排列(逆序)  关键字比较次数： 2 ( 1) 1 1 −  = − = n n i n i  记录移动次数： »若待排序记录是随机的，取平均值 T(n)=O(n²) ❖空间复杂度：S(n)=O(1) 2 ( 4)( 1) ( 2) 1 1 + −  + = − = n n i n i