20

10.23 PROC TwoWayInsertSort(Var r:listtype; d:listtype; n:integer);

{对r[1..n]进行2-路插入排序，d是与r具有相同空间的辅助向量。设first和}

{final两个指针，先将r[1]放到d[1]。然后，从第2元素起，逐个与d[1]比较,}

{大于d[1]者在1..final 间进行折半插入，反之在first..n间进行折半插入}

[ d[1]:=r[1]; first:=final:=1;

FOR i:=2 TO n DO {从2开始，逐个插入}

IF r[i].key>=d[1].key THEN bipasssrch(r,1,final,i,1)

ELSE IF first=1 THEN [ first:=n; d[n]:=r[i] ]

ELSE bipasssrch(r,first,n,i,2)

FOR i:=1 TO n DO r[i]:=d[i]; {最终排序结果在r中}

]

ENDP;

PROC bipasssrch(r: listtype; VAR low,high:integer; j,k:integer)

{在low和high区间折半查找第j个元素的位置,k等于1或2表示}

{在1..final 间或first..n间折半插入}

WHILE (low<=high) DO

[m:=(low+high) DIV 2;

IF r[m].key<r[j].key THEN low:=m+1 ELSE high:=m-1;

]

IF k=1 {在 1..final 间插入}

THEN [FOR jj:=final DOWNTO low DO d[jj+1]:=d[jj]

d[low]:=r[j]; final:=final+1;

]

ELSE [FOR jj:=first TO high DO d[jj-1]:=d[jj]

d[high]:=r[j]; first:=first-1;

]

ENDP;

10.25 PROC StlinkedInsertSort(VAR s:StlinkedList; n:integer);

{对静态链表s[1..n]进行表插入排序，并调整结果，使表物理上排序}

s[0].key:=maxint; s[1].next:=0; i:=2;

WHILE i<=n DO

[q:=0; p:=s[0].next;{ p指向当前最小元素，q是p的前驱}

WHILE (p<>0) AND (s[p].key<s[i].key) DO [ q:=p; p:=s[p].next ];

s[i].next:=p; s[q].next:=i;

i:=i+1

]

ENDP;

PROC rearrange(VAR s:StlinkedList){重排静态链表，使之物理有序}

i:=1; p:=s[0].next;

WHILE i<=n DO

[ WHILE p<i DO p:=s[p].next;

q:=s[p].next;

IF i<>p THEN [ s[i]ßàs[p]; s[i].next:=p;

p:=q;

i:=i+1;

]

ENDP;

10.27 PROC BubbleSort( VAR r:Listype; n:integer)

{对r[1..n]进行冒泡排序。两两比较，直到一趟排序中无交换为止}

i:=1; exchange:=false; {设标记，一趟排序中无交换时排序结束}

WHILE （i<=n-1）AND NOT exchange DO

[ j:=1; exchange:=true; {假定本趟无交换}

WHILE j<=n-i DO {循环次数确定，也可如下题那样用FOR循环}

[ IF r[j]>r[j+1] THEN [ r[j]ß>r[j+1]; exchange:=false{有交换}; ]

j:=j+1;

]

i:=i+1;

] {end of WHILE (I<=n-1) }AND NOT exchange DO}

ENDP;

PROC TwoWayBubbleSort( VAR r:Listype; n:integer)

{对r[1..n]进行双向冒泡排序。即相邻两遍向两个相反方向起泡}

i:=1; exchange:=true; {设标记}

WHILE exchange DO

[ exchange:=false; {假定本趟无交换}

FOR j:=n-i+1 DOWNTO i+1 DO {向前起泡，一趟有一最小冒出}

IF r[j]<r[j-1] THEN [ r[j]ß>r[j-1]; exchange:=true{有交换}; ]

FOR j:= i+1 TO n-i DO {向后起泡，一趟有一最大沉底}

IF r[j]>r[j+1] THEN [ r[j]ß>r[j+1]; exchange:=true{有交换}; ]

i:=i+1;

] {end of WHILE exchange DO}

ENDP;

10.29 PROC SwapSort( VAR r:Listype; n:integer)

{对r[1..n]进行奇偶交换排序}

exchange:=false;

WHILE NOT exchange DO

[exchange:=true; i:=1;{奇数项排序}

WHILE i<n DO

[ IF r[i]>r[i+1] THEN [r[i]ß>r[i+1]; exchange:=false ];

i:=i+2;

]

i:=2;

WHILE i<n DO {偶数项排序}

[IF r[i]>r[i+1] THEN [r[i]ß>r[i+1]; exchange:=false ];

i:=i+2;

]

] {end of WHILE NOT exchange DO}

讨论：1 排序结束的条件是一趟排序中无交换

2 正序时需n-1次比较，无交换；

10．30 PROC QuickSort(VAR r:Listype; n:integer);

{对r[1..n]进行快速排序的非递归算法}

TYPE node=RECORD

low,high:integer;

END;

stack=ARRAY[1..n] OF node；

VAR s:stack; top:integer;

[ top:=1; s[top].low:=1; s[top].high:=n;

WHILE top<>0 DO

[ss:=s[top].low; tt:=s[top].high; top:=top-1; flag:=true;

WHILE flag DO

[quickpass(r,ss,tt,k);

IF k-ss>tt-k {一趟排序后分割成左右两部分}

THEN IF k-ss>1 {子序列长度大于1，长的先进栈}

THEN [top:=top+1; s[top].low:=ss; s[top].high:=k-1;

IF tt-k>1 THEN ss:=k+1 {短的直接处理}

ELSE flag:=false {需退栈}

]

ELSE IF tt-k>1 {子序列长度大于1，长的先进栈}

THEN [ top:=top+1; s[top].low:=k+1; s[top].high:=tt;

IF k-ss>1 THEN tt:=k-1 {短的直接处理}

ELSE flag:=false {需退栈}

]

] {end of WHILE top<>0 }

]

ENDP；

PROC quickpass(VAR r:Listype;s,t: integer;VAR k:integer);

i:=s; j:=t; rp:=r[i]; x:=r[i].key;

WHILE i<j DO

[ WHILE (i<j) AND (x<=r[j].key) DO j:=j-1;

IF (i<j) THEN [r[i]:=r[j]; i:=i+1;

WHILE (I<j) AND (x>=r[i].key) DO i=i+1;

IF (I<j) THEN [r[j]:=r[i]; j:=j-1;

] r[I]:=rp; k:=I

ENDP; {end of quickpass}

10.31 PROC arrange(VAR r:Listype; n:integer);

{对r[1..n]进行整理，使关键字为负值的记录排在关键字为非负值的记录之前}

[ i:=1; j:=n;

WHILE r[i].key>0 DO i:=i+1; {找第一个关键字为负值的记录}

IF i<>1 THEN [ r[1]ßàr[i] ]; {枢轴应为负值}

r[0]:=r[i]; rp:=r[i]; x:=r[i].key;

WHILE i<j DO

[ WHILE (i<j) AND (r[j].key>=0) DO j:=j-1;

IF (i<j) THEN [r[i]:=r[j]; i:=i+1;

WHILE (I<j) AND (r[i].key<0) DO i=i+1;

IF (I<j) THEN [r[j]:=r[i]; j:=j-1;

]

r[i]:=rp;

ENDP; {end of arrange }

10.33 PROC LinkedListSelectSort( ra: LinkedList);

{设la是带头结点的链表的指针，本算法对la进行简单选择排序}

{本算法一趟找出一个关键字最小的结点，数据和当前结点进行交换;}

{若要交换指针，则须记下当前结点和最小结点的前驱指针}

p:=la^.next;

WHILE p<>NIL DO

[q:=p^.next; r:=p^.data; {设r是指向关键字最小的结点的指针}

WHILE <q<>NIL) DO

[ IF q^.data<r^.data THEN r:=q;

q:=q^.next;

]

IF r<>p THEN [r^.dataßàp^.data]

p:=p^.next;

] {end OF WHILE}

ENDP;

10.34 PROC HeapSort(VAR h: HeapType);

{堆排序算法}

PROC AdjustHeap(VAR h: HeapType; n: integer);

{已知h[1..n]是堆，本算法将 h[1..n+1] 调整为堆}

f:=(1+n) DIV 2; { f是n的双亲结点}; finished:=false;

WHILE (f>0) AND NOT finished DO

IF h[f].key>h[n].key THEN [h[n]:=h[f]; n:=f; f:=f DIV 2]

ELSE finished:=true;

h[f]:=rc;

ENDP; {end AdjustHeap}

[ FOR i:=1 TO n DO AdjustHeap(h,i); {end HeapSort}

10.42 PROC MiddleElem(VAR r:Listype; n:integer);

{求记录序列r[1..n]中关键字取中值的记录，中值的意思是该记录排在}

{记录序列的中间位置上,返回该记录的关键字}

s:=1; t:=n; m:=n DIV 2 { m为记录的中间位置}

quickpass( r,s,t,k)

WHILE k<>m DO

IF k<m THEN quickpass( r,k+1,t,

ELSE quickpass( r,s,k-1,k)

ENDP;

PROC quickpass(VAR r:Listype;s,t: integer;VAR k:integer);

i:=s; j:=t; rp:=r[i]; x:=r[i].key;

WHILE i<j DO

[ WHILE (i<j) AND (x<=r[j].key) DO j:=j-1;

IF (i<j) THEN [r[i]:=r[j]; i:=i+1;

WHILE (i<j) AND (x>=r[i].key) DO i=i+1;

IF (i<j) THEN [r[j]:=r[i]; j:=j-1;

] r[i]:=rp; k:=i

ENDP; {end of quickpass}

10.43 PROC CountSort(VAR r:Listype; n:integer);

{对r[1..n]进行计数排序}

c[1..n]:=0; {c数组初始化，元素值指其在r中的位置。如c[i]=j,(0<=i,j<=n)}

{则意味着 r中有 j 个比 r[i] 小，即 r[i] 应在r的第 j+1 位置上}

FOR i:=1 TO n-1 DO {一趟比较选出大小，给数组 c 赋值}

FOR j:=i+1 TO n DO

IF r[i]>r[j] THEN c[i]:=c[i]+1 ELSE c[j]:=c[j]+1;

i:=1;

WHILE i<n DO {若c[i]+1= i，则r[i] 正好是第i个元素;否则，需要调整}

[IF c[i]+1<>i

THEN [ j:=i; rc:=r[i];

WHILE c[j]+1<>i DO

[k:=c[j]+1;rt:=r[k]; {暂时保存r[k]}

r[k]:=rc; j:=c[k]; {取下一 j 值}

c[k]:=k-1; {第k个已排好}

rc:=rt

]

r[i]:=rc; c[i]:=i-1； {完成了一个小循环，第i个已排好}

]

i:=i+1

]

上述调整也可用如下逻辑简单但效率低下的算法：

c[1..n]:= c[1..n]+1 {c数组元素值指其在r中的位置。

WHILE i<n DO

[ WHILE c[i]<>i DO [j:=c[i]; c[i]ßà c[j]; r[i]ßà r[j] ]

i:=i+1

]