第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)希尔排序
1.2.1直接插入排序 假设待排序的记录存放在数组R0.n-1中,排序过程的某一中 间时刻,R被划分成两个子区间R0.i1和R[in-1,其中:前一 个子区间是已排好序的有序区后一个子区间则是当前未排序 的部分不妨称其为无序区。直接插入排序的基本操作是将当 前无序区的第1个记录R插入到有序区R0.1中适当的位置 上,使R0.变为新的有序区。这种方法通常称为增量法,因为 它每次使有序区增加1个记录 直接插入排序的算法如下:
11.2.1 直接插入排序 假设待排序的记录存放在数组R[0..n-1]中,排序过程的某一中 间时刻,R被划分成两个子区间R[0..i-1]和R[i..n-1],其中：前一 个子区间是已排好序的有序区,后一个子区间则是当前未排序 的部分,不妨称其为无序区。直接插入排序的基本操作是将当 前无序区的第1个记录R[i]插入到有序区R[0..i-1]中适当的位置 上,使R[0..i]变为新的有序区。这种方法通常称为增量法,因为 它每次使有序区增加1个记录。 直接插入排序的算法如下：
void insertsort( RecType ri,int-n)/对R0.,n-1按递增有序进行 直接插入排序* int Rectype temp; for(i=l; i=0 & temp key<riil. key) R+1=Rji;/将关键字大于R[key的记录后移*/ Ri+1temp;/在j+1处插入R[/
void InsertSort(RecType R[],int n) /*对R[0..n-1]按递增有序进行 直接插入排序*/ { int i,j; RecType temp; for (i=1;i=0 && temp.key<R[j].key) { R[j+1]=R[j]; /*将关键字大于R[i].key的记录后移*/ j--; } R[j+1]=temp; /*在j+1处插入R[i]*/ } }
例11设待排序的表有10个记录其关键字分别为 9,8,76,5,4,3,2,1,0}。说明采用直接插入排序方法进行排序的 过程。 初始关键字9876432 i-289654 21 i=3 8954 7894 3333 21 2 i=5 67891 21 =6 3I 5678921 =7 765432 543 654 0000000009 i=8 6789 12 5678
例11.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]
11.2.2希尔排序 希尔排序也是一种插入排序方法实际上是一种分组插入方法。 其基本思想是:先取定一个小于n的整数d1作为第一个增量,把 表的全部记录分成d个组所有距离为d1的倍数的记录放在同 个组中,在各组内进行直接插入排序;然后取第二个增量d24(< d1),重复上述的分组和排序,直至所取的增量d=1(d4d K…<d2<d1即所有记录放在同一组中进行直接插入排序为止 希尔排序的算法如下:
11.2.2 希尔排序 希尔排序也是一种插入排序方法,实际上是一种分组插入方法。 其基本思想是：先取定一个小于n的整数d1作为第一个增量,把 表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一 个组中,在各组内进行直接插入排序；然后,取第二个增量d2 (＜ d1 ), 重 复 上 述 的 分 组 和 排 序 , 直 至 所 取 的 增 量 dt =1(dt<dt- 1<…<d2<d1 ),即所有记录放在同一组中进行直接插入排序为止。 希尔排序的算法如下：
void Shellsort( RecType rubin n)/希尔排序算法 int i,j, d; RecType temp; d=n/2 /d取初值n/2* while(d>o for(i=d;i=0 & riikey>R[j+d. key {temp=Rjl;/R与Rj计d交换* RIl-R+d; rlj+d=temp; d=d/2; /递减增量d*
void ShellSort(RecType R[],int n) /*希尔排序算法*/ { int i,j,d;RecType temp; d=n/2; /*d取初值n/2*/ while (d>0) { for (i=d;i=0 && R[j].key>R[j+d].key) { temp=R[j]; /*R[j]与R[j+d]交换*/ R[j]=R[j+d];R[j+d]=temp; j=j-d; } } d=d/2; /*递减增量d*/ } }