．[題目分析]順序存儲結構的線性表的插入其時間復雜度為O(n)平均移動近一半的元素線性表LA和LB合並時若從第一個元素開始一定會造成元素後移這不符合本題高效算法的要求另外題中敘述線性表空間足夠大也暗示出另外合並方式即應從線性表的最後一個元素開始比較大者放到最終位置上設兩線性表的長度各為m和n 則結果表的最後一個元素應在m+n位置上這樣從後向前直到第一個元素為止
PROC Union(VAR LA:SeqList;LB:SeqList)∥LA和LB是順序存儲的非遞減有序線性表本算法將LB合並到LA中元素仍非遞減有序
m:=LAlast;n:=LBlast;∥mn分別為線性表LA和LB的長度
k:=m+n;∥k為結果線性表的工作指針(下標)
i:=m;j:=n;∥ij分別為線性表LA和LB的工作指針(下標)
WHILE(i>)AND(j>)DO
IF LAelem[i]>=LBelem[j]
THEN[LAelem[k]:=LAelem[i];k:=k;i:=i;]
ELSE[LAelem[k]:=LBelem[j];k:=k;j:=j;]
WHILE(j>) DO [LAelem[k]:=LBelem[j];k:=k;j:=j;]
LAlast:=m+n;
ENDP;
[算法討論]算法中數據移動是主要操作在最佳情況下(LB的最小元素大於LA的最大元素)僅將LB的n個元素移(拷貝)到LA中時間復雜度為O(n)最差情況LA的所有元素都要移動時間復雜度為O(m+n)因數據合並到LA中所以在退出第一個WHILE循環後只需要一個WHILE循環處理LB中剩余元素第二個循環只有在LB有剩余元素時才執行而在LA有剩余元素時不執行本算法利用了題目中線性表空間足夠大的條件最大限度的避免移動元素是一種高效算法
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23355.html
