10. 2插入排序插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止两种插入排序方法：（1）直接插入排序（2）希尔排序6
6 10.2 插入排序 插入排序的基本思想是：每次将一个待排序的记 录,按其关键字大小插入到前面已经排好序的子表中 的适当位置,直到全部记录插入完成为止。 两种插入排序方法： (1)直接插入排序 (2)希尔排序
10. 2. 1直接插入排序假设待排序的记录存放在数组R[0..n-1中，排序过程的某一中间时刻,R被划分成两个子区间R[0.i-11和R[i..n-1],其中：前一个子区间是已排好序的有序区,后一个子区间则是当前未排序的部分，不妨称其为无序区直接插入排序的基本操作是将当前无序区的第1个记录Ri插入到有序区R0..i-1]中适当的位置上，使R[0.i变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录
7 10.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个记录
R[0]R[]插入位置在有序区中插入R[i的过程8
8 R[0] j R[i] 插入位置 j=i-1 在有序区中插入R[i]的过程
例10.1设待排序的表有10个记录，其关键字分别为说明采用直接插入排序方法进行9,8,7,6,5.4,3,2,1.01。i排序的过程879506321初始关键字4[8i=19]07653291i=286503241i=38509]3274189]i=47304261C89]320i=5675056789]2i=61314680i=7234579]1502346789]i=812356789]i=910419
9 例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]
voidInsertSort(RecTypeRll,intn）/*对R[0..n-1按递增有序进行直接插入排序*inti,j;RecType temp;for (i-l;i<n;i++)temp=R[i];i-i-1；/*从右向左在有序区R[0.i-1]找R[i的插入位置*while (j>=0 && temp.key<R[il.key)R[j+1]=R[il；/*将关键字大于R[i].key的记录后移*j--;/*在i+1处插入R[i]*R[i+1]=temp;10
10 void InsertSort(RecType R[],int n) /*对R[0.n-1]按递增有序进行 直接插入排序*/ { int i,j; RecType temp; for (i=1;i<n;i++) { temp=R[i]; j=i-1; /*从右向左在有序区R[0.i-1]找R[i]的插入位置*/ while (j>=0 && temp.key<R[j].key) { R[j+1]=R[j]; /*将关键字大于R[i].key的记录后移*/ j-; } R[j+1]=temp; /*在j+1处插入R[i]*/ } }