low=1; high =1-1; while(lows=high)& m=(low+high)/2 ∥折半 if (Lro. key <Lrm.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 high lowl 再如 插入 m 位置 Lr14364952586180239775 high llow
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
三、表插入排序 为了减少在排序过程中进行的 “移动”记录的操作,必须改变排序过 程中采用的存储结构。利用静态链表 进行排序,并在排序完成之后,一次 性地调整各个记录相互之间的位置, 即将每个记录都调整到它们所应该在 的位置上
三、表插入排序 为了减少在排序过程中进行的 “移动”记录的操作，必须改变排序过 程中采用的存储结构。利用静态链表 进行排序，并在排序完成之后，一次 性地调整各个记录相互之间的位置， 即将每个记录都调整到它们所应该在 的位置上
void INsertion Sort(Elem Sll, int n) ∥对记录序列SL[1.n作表插入排序 SLIOJ. key= MAXINT SL[OJ. next=l; SL[I]. next=0 for (i=2, K-n; ++i for(j=0,k=sL[O next; SL[kkey<= SLlikey; j=k, k-SL[k]. next &SLliJnext=i: SLli . next=k; j ∥结点插入在结点和结点k之间 3//LinsertionSort
void LInsertionSort (Elem SL[ ]， int n){ // 对记录序列SL[1..n]作表插入排序 SL[0].key = MAXINT ; SL[0].next = 1; SL[1].next = 0; for ( i=2; i<=n; ++i ) for ( j=0, k = SL[0].next;SL[k].key<= SL[i].key ; j=k, k=SL[k].next ) { SL[j].next = i; SL[i].next = k; } // 结点i插入在结点j和结点k之间 }// LinsertionSort
如何在排序之后调整记录序列? 算法中使用了三个指针: 其中:p指示第个记录的当前位置 指示第个记录应在的位置 q指示第计+1个记录的当前位置
算法中使用了三个指针： 其中：p指示第i个记录的当前位置 i指示第i个记录应在的位置 q指示第i+1个记录的当前位置 如何在排序之后调整记录序列？