AsF contd 入排序利用辅助地表的对结点递行物理 算法思想 (1)对于n个结点的序列来说,扫描辅助地址表t的n个单元,如果发现 t[i]=i,则r[不需要调整,如果til=i,不能直接将rj复制成r[t[j, 需要进入第2步 (2)首先,执行temp=[,保存[,将赋值给j, 循环执行下面的操作: k=tj,这时r可以覆盖,覆盖成k],同时令tk]=k,j=k 这样循环直到遇到订=i为止。这时跳出循环,执行j=temp;并 转到(1 34667 351424226503117 2174603 s 01234567
算法思想： (1)对于n个结点的序列来说，扫描辅助地址表t的n个单元，如果发现 t[i]=i，则r[i]不需要调整，如果t[i]!=i，不能直接将r[i]复制成r[t[i]]， 需要进入第2步 (2)首先，执行temp=r[i]，保存r[i] ，将i赋值给j， 循环执行下面的操作： k=t[j], 这时r[j]可以覆盖，覆盖成r[k]，同时令t[k]=k，j＝k。 这样循环直到遇到t[j]＝i为止。这时跳出循环，执行r[j]=temp; 并 转到(1) 内排序(cont’d) 2、插入排序 利用辅助地址表的对结点进行物理重排 35 14 12 42 26 50 31 17 0 1 2 3 4 5 6 7 2 1 7 4 6 0 3 5 0 1 2 3 4 5 6 7 35
2,入序 利用辅助地址表的对结点进行物理重排 void rearrange(RECTYPE r[, int tI, int n) f RECTYPE temp: int i,j, k for(i=0; K<=n; 1++) if(t1=1) i temp=ri]:= while(t[l!=i) ik=tl; r[l-r[k]; tL=j;j=k, i GI-temp: tll=
void rearrange(RECTYPE r[], int t[], int n) { RECTYPE temp; int i, j, k; for(i=0;i<=n;i++) if(t[i]!=i) { temp=r[i]; j=i; while(t[j]!=i) {k=t[j]; r[j]=r[k]; t[j]=j; j=k;} r[j]=temp; t[j]=j; } } 内排序(cont’d) 2、插入排序 利用辅助地址表的对结点进行物理重排