第11章内排序 11.1排序的基本概念 11.2插入排序 11.3交换排序 11.4选择排序 11.5归并排序 11.6基数排序 11.7各种内排序方法的比较和选择 本章小结
第11章 内 排 序 11.6 基数排序 本章小结 11.1 排序的基本概念 11.2 插入排序 11.3 交换排序 11.4 选择排序 11.5 归并排序 11.7 各种内排序方法的比较和选择
11.1排序的基本概念 所谓排序就是要整理表中的记录使之按关键字递增(或递减) 有序排列。其确切定义如下: 输入:n个记录,R0,R1…Rn1,其相应的关键字分别为 05k15 n-1 输出:R,R,,R,使得kk≤≤k(或kk≥,k)
11.1 排序的基本概念 所谓排序,就是要整理表中的记录,使之按关键字递增(或递减) 有序排列。其确切定义如下： 输入： n 个 记 录 ,R0 ,R1 ,…,Rn-1 , 其 相 应 的 关 键 字 分 别 为 k0 ,k1 ,…,kn-1。 输出：R,R,…,R,使得k≤k≤…≤k(或k≥k≥…≥k)
当待排序记录的关键字均不相同时排序的结果是惟一的 否则排序的结果不一定惟一。如果待排序的表中存在有多个 关键字相同的记录经过排序后这些具有相同关键字的记录之 间的相对次序保持不变则称这种排序方法是稳定的;反之若 具有相同关键字的记录之间的相对次序发生变化则称这种排 序方法是不稳定的。 在排序过程中若整个表都是放在内存中处理排序时不涉及 数据的内、外存交换则称之为内排序;反之若排序过程中要 进行数据的内、外存交换则称之为外排序
当待排序记录的关键字均不相同时,排序的结果是惟一的, 否则排序的结果不一定惟一。如果待排序的表中,存在有多个 关键字相同的记录,经过排序后这些具有相同关键字的记录之 间的相对次序保持不变,则称这种排序方法是稳定的；反之,若 具有相同关键字的记录之间的相对次序发生变化,则称这种排 序方法是不稳定的。 在排序过程中,若整个表都是放在内存中处理,排序时不涉及 数据的内、外存交换,则称之为内排序；反之,若排序过程中要 进行数据的内、外存交换,则称之为外排序
待排序的顺序表类型的类型定义如下: typedef int KeyType;/定义关键字类型 ypedef struct 记录类型 Key Type key;/关键字项* InfoType data;/其他数据项类型为 InfoType*/ 3 Rectype; /排序的记录类型定义
待排序的顺序表类型的类型定义如下： typedef int KeyType; /*定义关键字类型*/ typedef struct /*记录类型*/ { KeyType key; /*关键字项*/ InfoType data; /*其他数据项,类型为 InfoType*/ } RecType; /*排序的记录类型定义*/
11.2插入排序 插入排序的基本思想是:每次将一个待排序的记录按其关 键字大小插入到前面已经排好序的子表中的适当位置直到全 部记录插入完成为止。 两种插入排序方法 (1)直接插入排序 (2)希尔排序
11.2 插入排序 插入排序的基本思想是：每次将一个待排序的记录,按其关 键字大小插入到前面已经排好序的子表中的适当位置,直到全 部记录插入完成为止。 两种插入排序方法： (1)直接插入排序 (2)希尔排序