第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排序的基本概念所谓排序，就是要整理表中的记录，使之按关键字递增(或递减）有序排列。其确切定义如下：输入：n个记录,R,R.…,R.-1,其相应的关键字分别为ko,kj....,kn-1o输 出：R,Ri..,Rin-1,使得 kio≤ki≤...≤kin-1 （或kio≥kii≥...≥kin-1)
2 10.1 排序的基本概念 所谓排序,就是要整理表中的记录,使之按关键字递 增(或递减)有序排列。其确切定义如下： 输入：n个记录,R0 ,R1 ,.,Rn-1 ,其相应的关键字分别为 k0 ,k1 ,.,kn-1。 输出： Ri0 ,Ri1,.,Rin-1, 使 得 ki0≤ki1≤.≤kin-1 ( 或 ki0≥ki1≥.≥kin-1)
当待排序记录的关键字均不相同时，排序的结果是惟一的，否则排序的结果不一定惟一。如果待排序的表中存在有多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的：反之若具有相同关键字的记录之间的相对次序发生变化则称这种排序方法是不稳定的。在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序；反外存交换，则称之之，若排序过程中要进行数据的内、为外排序3
3 当待排序记录的关键字均不相同时,排序的结果是 惟一的,否则排序的结果不一定惟一。如果待排序的 表中,存在有多个关键字相同的记录,经过排序后这些 具有相同关键字的记录之间的相对次序保持不变,则 称这种排序方法是稳定的；反之,若具有相同关键字 的记录之间的相对次序发生变化,则称这种排序方法 是不稳定的。 在排序过程中,若整个表都是放在内存中处理,排序 时不涉及数据的内、外存交换,则称之为内排序；反 之,若排序过程中要进行数据的内、外存交换,则称之 为外排序
内排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程无序序列区有序序列区经过一趟排序有序序列区无序序列区
4 内排序的方法 内部排序的过程是一个逐步扩大记录的 有序序列长度的过程。 经过一趟排序 有序序列区 无 序 序 列 区 有序序列区 无 序 序 列 区
待排序的顺序表类型的类型定义如下：/*定义关键字类型*typedef intKeyType;/*记录类型*/typedefstruct/*关键字项*/KeyType key;/*其他数据项，类型为InfoType data;InfoType*//*排序的记录类型定义*/RecType;5
5 待排序的顺序表类型的类型定义如下： typedef int KeyType; /*定义关键字类型*/ typedef struct /*记录类型*/ { KeyType key; /*关键字项*/ InfoType data; /*其他数据项,类型为 InfoType*/ } RecType; /*排序的记录类型定义*/