第10章内排序 10.1排序的基本概念 10.2插入排序 10.3交换排序 10.4选择排序 10.5归并排序 10.6基数排序 10.7各种内排序方法的比较和选择
1 第10章 内 排 序 10.6 基数排序 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.7 各种内排序方法的比较和选择
10.1排序的基本概念 ·所谓排序,就是要整理表中的记录,使之按关键字递增(或递 减)有序排列 当待排序记录的关键字均不相同时,排序的结果是唯一的, 否则排序的结果不一定唯一。 稳定和不稳定 如果经过排序后具有相同关键字的记录之间的相对次序保 持不变,则称这种排序方法是稳定的;反之,称这种排序方 法是不稳定的。 内排序和外排序 在排序过程中,若整个表都是放在内存中处理,排序时不 涉及数据的内、外存交换,则称之为内排序; 反之,若排序过程中要进行数据的内、外存交换,则称之 为外排序
2 • 所谓排序，就是要整理表中的记录，使之按关键字递增(或递 减)有序排列。 • 当待排序记录的关键字均不相同时，排序的结果是唯一的， 否则排序的结果不一定唯一。 • 稳定和不稳定 • 如果经过排序后具有相同关键字的记录之间的相对次序保 持不变，则称这种排序方法是稳定的；反之，称这种排序方 法是不稳定的。 • 内排序和外排序 • 在排序过程中，若整个表都是放在内存中处理，排序时不 涉及数据的内、外存交换，则称之为内排序； • 反之，若排序过程中要进行数据的内、外存交换，则称之 为外排序。 10.1 排序的基本概念
内部排序的分类 1.插入排序;2.选择排序; 3.交换排序;4.归并排序; 5.基数排序; 待排序的顺序表类型的类型定义如下: typedef int KeyType;//定义关键字类型 typedef struct//记录类型 KeyType key;//关键字项 InfoType data;//其他数据项,类型为工 nfofype 3 Recfypei //排序的记录类型定义
3 内部排序的分类 • 1. 插入排序； 2. 选择排序； • 3. 交换排序； 4. 归并排序； • 5. 基数排序； 待排序的顺序表类型的类型定义如下： typedef int KeyType; //定义关键字类型 typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; //排序的记录类型定义
10.2插入排序 插入排序的基本思想是: ·每次将一个待排序的记录,按其关键字大小插入 到前面已经排好序的子表中的适当位置,直到全 部记录插入完成为止。 两种插入排序方法 (1)直接插入排序(含二分插入排序) (2)希尔排序
4 • 插入排序的基本思想是： •每次将一个待排序的记录，按其关键字大小插入 到前面已经排好序的子表中的适当位置，直到全 部记录插入完成为止。 • 两种插入排序方法： •(1)直接插入排序（含二分插入排序） •(2)希尔排序 10.2 插入排序
10.2.1直接插入排序 假设待排序的记录存放在数组R.n-1中,排序过 程的某一中间时刻,R被划分成两个子区间R0.-1和 Ri n-1 其中,前一个子区间是已排好序的有序区,后一个 子区间则是当前未排序的部分,不妨称其为无序区 直接插入排序的基本操作是将当前无序区的第1个记 录R[插入到有序区R|0.i-1中适当的位置上,使R|0.i 变为新的有序区。 这种方法通常称为增量法,因为它每次使有序区增 加1个记录
5 • 假设待排序的记录存放在数组R[0..n-1]中，排序过 程的某一中间时刻，R被划分成两个子区间R[0..i-1]和 R[i..n-1]； • 其中，前一个子区间是已排好序的有序区，后一个 子区间则是当前未排序的部分，不妨称其为无序区。 • 直接插入排序的基本操作是将当前无序区的第1个记 录R[i]插入到有序区R[0..i-1]中适当的位置上，使R[0..i] 变为新的有序区。 • 这种方法通常称为增量法，因为它每次使有序区增 加1个记录。 10.2.1 直接插入排序
直接插入排序 趟直接插入排序的基本思想 有序区R|0.1 无序区Ri.n-11 RI 有序区R0 无序区R[i+1.n-11
6 有序区R[0..i-1] R[i] 无序区 R[i..n-1] ◆ 一趟直接插入排序的基本思想： 有序区R[0..i] 无序区 R[i+1..n-1] 直接插入排序
在有序区中插入R的过程 实现“一趟直接插入排序”可分三步进行: 1.在R0i-1查找R[的插入位置计1,使得 RO.jl. key sRi. key <rij+li-1.key ◆2将R+1-中的所有记录均后移一个位置; ◆3.将R[插入(复制)到R+1的位置上 mp□ RI 插入位置
7 tmp j R[i] 插入位置 j=i-1 在有序区中插入R[i]的过程 ◆实现“一趟直接插入排序”可分三步进行： ◆ 1. 在R[0..i-1]中查找R[i]的插入位置 j+1，使得 R[0..j].key R[i].key < R[j+1..i-1].key ◆ 2.将R[j+1..i-1]中的所有记录均后移一个位置； ◆ 3. 将R[i] 插入(复制)到R[j+1]的位置上
示例 初始关键字序列:513362968717281 i=1(33) 3351629687172851 i=2(62) 335162]9687172851 i=3(96) 3351629687172851 =4(87) 3351628796172851 i=5(17 733516287962851 i=6(28) 728335162879651 i=7(5 728335151628796 稳定的排序
8 示 例 初始关键字序列： [51] 33 62 96 87 17 28 51 i=1(33) [33 51] 62 96 87 17 28 51 i=2(62) [33 51 62] 96 87 17 28 51 i=3(96) [33 51 62 96] 87 17 28 51 i=4(87) [33 51 62 87 96] 17 28 51 i=5(17) [17 33 51 62 87 96] 28 51 i=6(28) [17 28 33 51 62 87 96] 51 i=7(51) [17 28 33 51 51 62 87 96] 稳定的排序
void Insertsort(Recfype R[]int n) //对R[0..n-1]按递增有序进行直接插入排序 t int i,ji Recf'ype tmp; for(i=1;=0&& tmp. key<R[j].key) R[j+1]=R[j];//将关键字大于R[i]key的记录后移 R[]+1]=tmp i //在j+1处插入R[i]
9 void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i,j; RecType tmp; for (i=1;i=0 && tmp.key<R[j].key) { R[j+1]=R[j]; //将关键字大于R[i].key的记录后移 j--; } R[j+1]=tmp; //在j+1处插入R[i] } }
例10.1设待排序的表有10个记录其关键字分别为 {9,87,6,5,4,3,2,10}。说明采用直接插入排序方法进行 排序的过程。 初始关键字9 5 ;l.l.l..l 123 8987 5 4444 333333 222 56789 4321 8765432 6669876543 87654 8765 876 0000000009 8
10 例10.1 设待排序的表有10个记录,其关键字分别为 {9,8,7,6,5,4,3,2,1,0}。说明采用直接插入排序方法进行 排序的过程。 初始关键字 9 8 7 6 5 4 3 2 1 0 i=1 [8 9] 7 6 5 4 3 2 1 0 i=2 [7 8 9] 6 5 4 3 2 1 0 i=3 [6 7 8 9 ] 5 4 3 2 1 0 i=4 [5 6 7 8 9] 4 3 2 1 0 i=5 [4 5 6 7 8 9 ] 3 2 1 0 i=6 [3 4 5 6 7 8 9 ] 2 1 0 i=7 [2 3 4 5 6 7 8 9] 1 0 i=8 [1 2 3 4 5 6 7 8 9] 0 i=9 [0 1 2 3 4 5 6 7 8 9 ]