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、插入排序 利用辅助地址表的对结点进行物理重排
3、交换排序 (1)直接交换排序冒泡排序的间复亲度:0m2) void bubblesort(RECTYPE rLl, int n) f RECTYPE temp; int i, j for(i=1; i<n; 1++) for(j=0; j<n-1; j++) ifr[i]. key>r[j+1]. key) temp=rL] r[j]=r[j+1] Lj+l=temp
void bubblesort(RECTYPE r[],int n) { RECTYPE temp; int i, j; for(i=1;i<n;i++) for(j=0;j<n-i;j++) if(r[j].key>r[j+1].key) {temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; } } 时间复杂度：O(n2 ) 内排序(cont’d) 3、交换排序 (1) 直接交换排序(冒泡排序)
3、交换排序(1)直接交换排序冒泡排序 改进思想: (1)一旦某趟起泡过程中没有发生冒泡,就结束算法 (2)记下没有发生冒泡的区间kni,下次冒泡终点就 是k-1 (3)利用传送代替交换,当遇到a需要上冒时,并不 交换数据,而是将后序比它小的数据向前移动,直 到遇到a比a大为止,然后将a放到a1的前面 (4)可以交替地从左向右上冒和从右向左下沉
(1) 直接交换排序(冒泡排序) 改进思想： (1) 一旦某趟起泡过程中没有发生冒泡，就结束算法 (2) 记下没有发生冒泡的区间k..n-i，下次冒泡终点就 是k-1 (3) 利用传送代替交换，当遇到ak需要上冒时，并不 交换数据，而是将后序比它小的数据向前移动，直 到遇到aj比ak大为止，然后将ak放到aj的前面。 (4) 可以交替地从左向右上冒和从右向左下沉 内排序(cont’d) 3、交换排序