[算法討論]本題用一維數組存儲線性表結果線性表B和C中分別有j+和k+個元素若采用教材中的線性表則元素的表示作相應改變例如Aelem[i]而最後B和C表應置上表的長度如Blength=j和Clength=k
() 本題與第題本質上相同第題要求分開正數和負數這裡要求分開奇數和偶數判別方式是a[i]%==滿足時為偶數反之為奇數
() 本題與第題相同只是敘述不同
() 本題與第題基本相同不同之處在於這裡的分界元素是整數(鏈表中並不要求一定有)本題要求用標准pascal描述算法如下所示
TYPE arr=ARRAY[] OF integer;
VAR aarr;
PROCEDURE Rearrange(VAR aarr);∥a是n(設n=)個整數組成的線性表用一維數組存儲本算法將n個元素中所有大於等於的整數放在所有小於的整數之後
VAR ijt: integer;
BEGIN
i:=;j:=n;t:=a[];∥ij指示順序表的首尾元素的下標t暫存分界元素
WHILE(i<j)DO
BEGIN
WHILE (i<j)AND(a[j]>=) DO j:=j;
IF(i<j)THEN BEGIN A[i]:=A[j];i:=i+ END;
WHILE (i<j)AND(a[i] <) DO i:=i+;
IF(i<j)THEN BEGIN A[j]:=A[i];j:=j END;
END;
a[i]:=t;
END;
[算法討論] 分界元素t放入a[i]而不論它的值如何算法中只用了一個t中間變量符合空間復雜度O()的要求算法也滿足時間復雜度O(n)的要求
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23345.html
