10.2插入排序 10.2.1直接插入排序 基本思想:将一个记录插入到已排好序的 有序表中。(个数增1) 例,已知待排序的一组记录。 R(49),R(38),R(65),R(97)R(76)R(13) R(27)R(49)设前4个记录已重新排序: {R(38),R(49),R(65),R(97)
10.2 插入排序 10.2.1 直接插入排序 基本思想：将一个记录插入到已排好序的 有序表中。（个数增1） 例，已知待排序的一组记录。 R(49),R(38),R(65),R(97),R(76),R(13), R(27),R(49)设前4个记录已重新排序： {R(38),R(49),R(65),R(97)}
现要插入第5个记录R(76)。由65< 476<97,则R(76)应插入在R(65)和 R(97)之间,而得新的有序序列: {R(38),R(49),R(65),R(76)R(97) 上述插入过程为一趟直接插入序列,在i 1个有序记录中插入第i个为第i个趟直接插 入排序,在找插入位置时,为防数据下标 出界,设[0为监视哨,在搜索过程中,同 时后移记录。整个过程为n-1趟插入
现要插入第5个记录R(76)。由65< 76<97，则R(76)应插入在R(65)和 R(97)之间，而得新的有序序列： {R(38), R(49),R(65),R(76),R(97)} 上述插入过程为一趟直接插入序列，在i- 1个有序记录中插入第i个为第i个趟直接插 入排序，在找插入位置时，为防数据下标 出界，设r[0]为监视哨，在搜索过程中，同 时后移记录。整个过程为n-1趟插入
实现过程 (49)38659776132749 i=2(38)(3849)6597761327 3(65)(384965)9776132749 =4(97)(38496597)76132749 i=5(6)(3849657697)1327 1=6(13)(133849657697)2749 =7(27)(13273849657697)49 =8(啊(132738494965769 监视哨
实现过程： (49) 38 65 97 76 13 27 49 i=2 (38) (38 49) 65 97 76 13 27 49 i=3 (65) (38 49 65) 97 76 13 27 49 i=4 (97) (38 49 65 97) 76 13 27 49 i=5 (76) (38 49 65 76 97) 13 27 49 i=6 (13) (13 38 49 65 76 97) 27 49 i=7 (27) (13 27 38 49 65 76 97) 49 i=8 (49) (13 27 38 49 49 65 76 97) 监视哨
算法实现 中 Insertsort(L) t for(i=2; i<=Llength; ++i) if(LT(L r[. key, L r[i-1].key)) /*<需将L.r[订插入有序列表* {Lr[0]=L.r[i;/*复制为哨兵*/ L.r[门]=L.r[i-1; for(j=i-2: LT (L r[O].key, Lr[].key);--j L+1]=Lrj;/*记录后移* Lr+1]=Lr[0];/*插入正确位置* S//Insertsort
算法实现： Insertsort(L) { for(i=2;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-1].key)) /*<需将L.r[i]插入有序列表*/ { L.r[0]= L.r[i]; /*复制为哨兵*/ L.r[i]= L.r[i-1]; for(j=i-2; LT(L.r[0].key,L.r[j].key); --j) L.r[j+1]= L.r[j]; /*记录后移*/ L.r[j+1]= L.r[0]; /* 插入正确位置*/ }//Insertsort