教育部—微软精品课程建设项目 void BilnsertionSort( SqList &l)i for(i-2, K=Llength; ++ii Lr[0]=L.r[i;∥将Lr暂存到Lr[0 在Lr[1-1中折半查找插入位置 for(j=1-1; j>=high+1; -j) Lr计+1]=Lrij;∥记录后移 L rhigh+1]=Lr[0];∥/插入 1// for 3// BInsertsort
void BiInsertionSort ( SqList &L ) { } // BInsertSort 在 L.r[1..i-1]中折半查找插入位置； for ( i=2; i<=L.length; ++i ) { } // for L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0] for ( j=i-1; j>=high+1; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入
教育部—微软精品课程建设项目 low=l, high =i-I while (low<=high)i m=(low+high)/2 ∥折半 if (LrOJ. key L r[m]. key) high=m-1;∥插入点在低半区 else low=m+1;∥/插入点在高半区 南京航空航天大学数据结构课题组版权所有
low = 1; high = i-1; while (low<=high) { } m = (low+high)/2; // 折半 if (L.r[0].key < L.r[m].key) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区
教育部—微软精品课程建设项目 例如 插入 位置 Lr14364952805861239775 igh I lowl 再如 插入 m 位置 Lr14364952586180239775 thigh low mn光aD 京航空天太学结种速题版权有
14 36 49 52 80 58 61 23 97 75 i low high m m low low m high 14 36 49 52 58 61 80 23 97 75 i low high m high m high m low 例如: 再如: 插入 位置 插入 位置 L.r L.r
教育部—微软精品课程建设项目 三、表插入排序 为了减少在排序过程中进行的 “移动”记录的操作,必须改变排序 过 程中采用的存储结构。利用静态链表 进行排序,并在排序完成之后,一次 性地调整各个记录相互之间的位置, 即将每个记录都调整到它们所应该在 的位置上。 南京航空航天大学数据结构课题组版权所有
三、表插入排序 为了减少在排序过程中进行的 “移动”记录的操作，必须改变排序 过 程中采用的存储结构。利用静态链表 进行排序，并在排序完成之后，一次 性地调整各个记录相互之间的位置， 即将每个记录都调整到它们所应该在 的位置上
教育部—微软精品课程建设项目 如何在排序之后调整记录序列? 算法中使用了三个指针: 其中:p指示第个记录的当前位置 指示第个记录应在的位置 q指示第计+1个记录的当前位置 南京航空航天大学数据结构课题组版权所有
算法中使用了三个指针： 其中：p指示第i个记录的当前位置 i指示第i个记录应在的位置 q指示第i+1个记录的当前位置 如何在排序之后调整记录序列？