插入算法如下: 方法:K与K1,K12K1依次比较直到找到应插入的位置。 void insertSort(RedType ll, int n) f int i,j; for(i=2; K<n; i++) if(Ll. key<Li-1.key {L0=I[; *作为监视哨* for(j=1-1; LIO.key<Ll. key;--j) L[i+1]-L|ji;记录后移* Lj+1|=L|0l;插入* 2021/2/22
2021/2/22 9 void insertSort(RedType L[ ],int n) { int i ,j; for(i=2; i<=n; i++) if(L[i].key<L[i-1].key) { L[0]=L[i]; /* 作为监视哨*/ for( j=i-1; L[0].key<L[j].key; − −j ) L[j+1]=L[j]; /* 记录后移*/ L[j+1]=L[0]; /* 插入 */ } } 插入算法如下： 方法:Ki与Ki-1 ,K i-2 ,…K1依次比较,直到找到应插入的位置
10 2、折半插入排序 折半插入排序在寻找插入位置时,不是逐 个比较而是利用折半查找的原理寻找插入位置。 待排序元素越多,改进效果越明显。 折半插入排序的条件: 在有序序列中插入一个关键字 举例,图8-2-2 2/22 202l/2/
2021/2/22 10 2、折半插入排序 折半插入排序在寻找插入位置时，不是逐 个比较而是利用折半查找的原理寻找插入位置 。 待排序元素越多，改进效果越明显。 折半插入排序的条件： 在有序序列中插入一个关键字。 举例，图8-2-2
2、折半插入排序 ll 折半插入排序在寻找插入位置时,不是逐个比较而是利用折半 查找的原理寻找插入位置。待排序元素越多,改进效果越明显 例:有6个记录,前5个已排序的基础上,对第6个记录排序 1527365369142 ↑low ↑mid high (42>36) 1527365369]42 ↑ow↑high ↑mid (42<53) 1527365369]42 个high↑ow( high<low!查找结束,插入位置为ow或hgh+1) 152736425369
2021/2/22 11 2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半 查找的原理寻找插入位置。待排序元素越多，改进效果越明显。 例：有6个记录，前5个已排序的基础上，对第6个记录排序。 [ 15 27 36 53 69 ] 42 low mid high [ 15 27 36 53 69 ] 42 low high mid [ 15 27 36 53 69 ] 42 high low [ 15 27 36 42 53 69 ] (high<low，查找结束，插入位置为low或high+1 ) ( 42>36 ) ( 42<53 )
void BinsertSort(RedType LI l,int n) 折半插入排序减少 i int i, low, high, mid; 了关键字的比较次 for(i=2;i<=n;++i){ 数,但记录的移动 L|0=L[i;/r0作为监视哨* 次数不变,其时间 复杂度与直接插入 low=l; high=1-1; 排序相同。 While(low<=high) (mid=(low+high)/2; /折半后的位置 if(L0] key<Lmid. key)high=mid-1;/插入点在低半区 else low=mid+l; for(j=i-1;j>=high+1; --j) L[j+1=L[l; 记录后移 Lhigh+lOI 插入* or }/折半插入排序* 2/22 202l/2/
2021/2/22 12 void BinsertSort(RedType L[ ],int n) { int i,low,high,mid; for(i=2; i<=n; ++i){ L[0]=L[i]; /* r[0]作为监视哨*/ low=1; high=i-1; While(low<=high) {mid=(low+high)/2; if (L[0].key<L[mid].key) high=mid-1; //插入点在低半区 else low=mid+1; } for( j=i-1; j>=high+1; − −j ) L[j+1]=L[j]; /* 记录后移*/ L[high+1]=L[0]; /* 插入*/ } /* for*/ }/*折半插入排序*/ 折半插入排序减少 了关键字的比较次 数，但记录的移动 次数不变，其时间 复杂度与直接插入 排序相同。 /*折半后的位置*/