直接插入排序 趟直接插入排序的基本思想 有序区R|0.1 无序区Ri.n-11 RI 有序区R0 无序区R[i+1.n-11
6 有序区R[0..i-1] R[i] 无序区 R[i..n-1] ◆ 一趟直接插入排序的基本思想： 有序区R[0..i] 无序区 R[i+1..n-1] 直接插入排序
在有序区中插入R的过程 实现“一趟直接插入排序”可分三步进行: 1.在R0i-1查找R[的插入位置计1,使得 RO.jl. key sRi. key <rij+li-1.key ◆2将R+1-中的所有记录均后移一个位置; ◆3.将R[插入(复制)到R+1的位置上 mp□ RI 插入位置
7 tmp j R[i] 插入位置 j=i-1 在有序区中插入R[i]的过程 ◆实现“一趟直接插入排序”可分三步进行： ◆ 1. 在R[0..i-1]中查找R[i]的插入位置 j+1，使得 R[0..j].key R[i].key < R[j+1..i-1].key ◆ 2.将R[j+1..i-1]中的所有记录均后移一个位置； ◆ 3. 将R[i] 插入(复制)到R[j+1]的位置上
示例 初始关键字序列:513362968717281 i=1(33) 3351629687172851 i=2(62) 335162]9687172851 i=3(96) 3351629687172851 =4(87) 3351628796172851 i=5(17 733516287962851 i=6(28) 728335162879651 i=7(5 728335151628796 稳定的排序
8 示 例 初始关键字序列： [51] 33 62 96 87 17 28 51 i=1(33) [33 51] 62 96 87 17 28 51 i=2(62) [33 51 62] 96 87 17 28 51 i=3(96) [33 51 62 96] 87 17 28 51 i=4(87) [33 51 62 87 96] 17 28 51 i=5(17) [17 33 51 62 87 96] 28 51 i=6(28) [17 28 33 51 62 87 96] 51 i=7(51) [17 28 33 51 51 62 87 96] 稳定的排序
void Insertsort(Recfype R[]int n) //对R[0..n-1]按递增有序进行直接插入排序 t int i,ji Recf'ype tmp; for(i=1;<n;i++) t tmp=Rli]i j=i-1;//从右向左在有序区中找R[豆的插入位置 while (3>=0&& tmp. key<R[j].key) R[j+1]=R[j];//将关键字大于R[i]key的记录后移 R[]+1]=tmp i //在j+1处插入R[i]
9 void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i,j; RecType tmp; for (i=1;i<n;i++) { tmp=R[i]; j=i-1; //从右向左在有序区中找R[i]的插入位置 while (j>=0 && tmp.key<R[j].key) { R[j+1]=R[j]; //将关键字大于R[i].key的记录后移 j--; } R[j+1]=tmp; //在j+1处插入R[i] } }
例10.1设待排序的表有10个记录其关键字分别为 {9,87,6,5,4,3,2,10}。说明采用直接插入排序方法进行 排序的过程。 初始关键字9 5 ;l.l.l..l 123 8987 5 4444 333333 222 56789 4321 8765432 6669876543 87654 8765 876 0000000009 8
10 例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 ]