．設有字母序列{QDFXAPNBYMCW}請寫出按路歸並排序方法對該序列進行一趟掃描後的結果_______ 【北方交通大學 二】
閱讀下列程序說明和PASCAL程序把應填入其中______處的字句寫在答題紙上程序說明
本題給出的是將數組a的元素aa…an從大到小排序的子程序子程序采用改進的選擇排序方法該方法基於以下思想
在選擇第一大元過程中 a與aj(j=nn…)逐個比較若發現aj>a則aj與a變換變換後新的aj有性質aj≥at(j<t≤n)若再有aj>a (j<j)aj與a交換則交換後的aj也有性質aj≥at(j<t≤n)如在挑選第一大元過程中與a交換的元素有k(k≥)個依次為ajaj…ajk則它們都滿足這一性質它們的下標滿足n≥j>j>…>jk>有了這些下標在確定第二大元時可只考慮a與aj (j=jkjk…) 逐個比較倘若jk=則可不經比較就知道它是第二大元在選擇第二大元過程中將與a交換過的元素下標也標記下來可供選擇其他大元使用但在選擇第二大元時應保證與a交換的那些位置上的新值也都滿足上述性質依次類推順序選擇第一第二…第n大元實現對a的排序
設程序包含有常量和類型定義
CONST maxn=;
TYPE vector=ARRAY[maxn] OF integer;
index= maxn;
PROCEDURE sort(VAR a:vector;n:index)
VAR p:vector; ijkmt:integer;
BEGIN
k:=; i:=; m:=n;
WHILE i<n DO
BEGIN
FOR j:=m DOWNTO i+ DO
IF a[i]<a[j] THEN
BEGIN t:=a[i]; a[i]:=a[j]; a[j]:=t; k:=k+;(____()____)END;
REPEAT(____()____);
IF(____()____)THEN(____()____)
ELSE BEGIN m:=p[k]; k:=k; END;
UNTIL (i<m) OR (i=n);
IF (____()___)
BEGIN t:=a[i];(____()____);(____()____)END
END
END;【上海海運學院 七(分)】
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [
