8.md

1

for(i=dk+1;i<=L.length;++i)
		if(L.r[i].key<L.r[i-dk].key)
		{										//需将L.r[i]插入有序增量子表
			L.r[0]=L.r[i];						//暂存在L.r[0]
			for(j=i-dk;j>0&& L.r[0].key<L.r[j].key;j-=dk)
				L.r[j+dk]=L.r[j];				//记录后移，直到找到插入位置
			L.r[j+dk]=L.r[0];					//将r[0]即原r[i]，插入到正确位置
		}

2

while(low<high)
	{										//从表的两端交替地向中间扫描
		while(low<high&&L.r[high].key>=pivotkey) --high;
		L.r[low]=L.r[high];					//将比枢轴记录小的记录移到低端
		while(low<high&&L.r[low].key<=pivotkey) ++low;
		L.r[high]=L.r[low];					//将比枢轴记录大的记录移到高端
	}//while

3

  for(i=1;i<L.length;++i) 
	{  												//在L.r[i..L.length] 中选择关键字最小的记录
		k=i;                 
        for(j=i+1;j<=L.length;++j)
			if(L.r[j].key<L.r[k].key)  k=j;			//k指向此趟排序中关键字最小的记录
		if(k!=i) {t=L.r[i];L.r[i]=L.r[k];L.r[k]=t;} //交换r[i]与r[k]        
     }	

4

 while(i<=mid&&j<=high)
	{                 	
		//将R中记录由小到大地并入T中 
		if(R[i].key<=R[j].key) T[k++]=R[i++]; 
        else T[k++]=R[j++]; 
	} 

5

    for(j=2*s;j<=m;j*=2)
	{												//沿key较大的孩子结点向下筛选
		if(j<m&&L.r[j].key<L.r[j+1].key) ++j;		//j为key较大的记录的下标
        if(rc.key>=L.r[j].key) break;      			//rc应插入在位置s上
		L.r[s]=L.r[j]; s=j; 
    }
	L.r[s]=rc;                          			//插入

6

	int i,j;
	for(i=2;i<=L.length;++i)
		if(L.r[i].key<L.r[i-1].key)
		{   										//"<"，需将r[i]插入有序子表
			L.
      ];				 			//将待插入的记录暂存到监视哨中
            L.r[i]=L.r[i-1];	            		//r[i-1]后移
            for(j=i-2; L.r[0].key<L.r[j].key;--j)			//从后向前寻找插入位置
				L.r[j+1]=L.r[j];					//记录逐个后移，直到找到插入位置
            L.r[j+1]=L.r[0];						//将r[0]即原r[i]，插入到正确位置
		}

7

    while((m>0)&&(flag==1))
	{
		flag=0;           				//flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序
        for(j=1;j<=m;j++)
			if(L.r[j].key>L.r[j+1].key) 
			{
				flag=1;					//flag置为1，表示本趟排序发生了交换
				t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t;	//交换前后两个记录
			}							//if
		--m;
    }