第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 直接插入排序