数据结构考研分类复习真题 第十章 答案[38]

void sort (RecType K[]int n)

{ for (i=;i<=n;i++) T[i]=i;

for (i=;i<n;i++)

for (j=;j<=ni;j++)

if (K[T[j]]>K[T[j+]]) {t=T[j];T[j]=T[j+];T[j+]=t;}

}//sort

[算法讨论] 上述算法得到辅助地址表T[i]的值是排序后K的第i个记录要使序列K有序则要按T再物理地重排K的各记录算法如下

void Rearrange(RecType K[]int T[]n)

//对有n个记录的序列K按其辅助地址表T进行物理非递减排序

{for(i=;i<=n;i++)

if (T[i]!=i)

{j=i; rc=K[i]; //暂存记录K[i]

while (T[j]!=i) //调整K[T[j]]到T[j]=i为止

{m=T[j]; K[j]=K[m]; T[j]=j; j=m;}

K[j]=rc; T[j]=j; //记录R[i]到位

}//if

}//Rearrange

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []