清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 线性表的分割 输入:待分割的子表P(m:n)。 输出:分割后的分界线位置i PROCEDURE SPLIT(P, m, n, i) 选取P(k)其中m≤k≤n T=P(k P(k)=P(m) 1=m;
9.1 互换类排序 线性表的分割 输入：待分割的子表P(m：n)。 输出：分割后的分界线位置i。 PROCEDURE SPLIT(P，m，n，i) 选取P(k) 其中m≤k≤n T＝P(k)；P(k)＝P(m) i＝m；j＝n
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 WHILE(i≠j)D0 I WHILE (P(j>)and (i<j) d0 j=j-1 iF (i<j) THEN P(i)=P(j);i=i+1 WHIle (P(i)>T)and(i<j)Do i=i+1 IF(i<j THEN P(j)=P(i);j=j-1} P(i)=t RETURN
9.1 互换类排序 WHILE (i≠j) DO { WHILE (P(j)≥T)and(i＜j) DO j＝j－1 IF (i＜j) THEN { P(i)＝P(j)；i＝i＋1 WHILE (P(i)≥T)and(i＜j) DO i＝i＋1 IF (i＜j) THEN { P(j)＝P(i)；j＝j－1 } } } P(i)＝T RETURN
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 快速排序的递归算法 输入:待排序的子表P(m:n)。 输出:有序子表P(m:n)。 PROCEDURE QKSORT1(P, m, n) IF(n>m)THN[子表不空] I SPLIT(P, m, n, i) [分割] QKSORTI1(P,m,i-1);[对前面子表进行快速排序] QKSORT1(p,i+1,n);[对后面子表进行快速排序] RETURN
9.1 互换类排序 快速排序的递归算法 输入：待排序的子表P(m：n)。 输出：有序子表P(m：n)。 PROCEDURE QKSORT1(P，m，n) IF (n＞m) THEN [子表不空] { SPLIT(P，m，n，i)； [分割] QKSORT1(P，m，i－1)；[对前面子表进行快速排序] QKSORT1(p，i＋1，n)；[对后面子表进行快速排序] } RETURN
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 gksort1(p, m, n) int m, n; Et pl; i int if(n>m)/*子表不空* i= split(p,m,n);/*分割*/ qksort1(p,m,i-1);/*对前子表进行快速排序来/ gksort1(p,i+1,n);/*对后子表进行快速排序来/ return:
9.1 互换类排序 qksort1(p，m，n) int m，n； ET p[]； { int i； if (n＞m) /*子表不空*/ {i＝split(p，m，n)； /*分割*/ qksort1(p，m，i－1)；/*对前子表进行快速排序*/ qksort1(p，i＋1，n)；/*对后子表进行快速排序*/ } return； }
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 static int split(p,m,n)/米返回分界线位置* int m, n; Et pL] i int i,j, k, u; Et t: i=m-1;j=n-1;k=(i+j/2; if(p[i>=p[j)&&(p[j>=p[k]) u=j;/*选取一个元素* else if ((pli]>=plk]&&(pkk]>=pled)u=k else u=i: p plu=pLl
9.1 互换类排序 static int split(p，m，n) /*返回分界线位置*/ int m，n； ET p[]； { int i，j，k，u； ET t； i＝m－1； j＝n－1； k＝(i＋j)/2； if ((p[i]＞＝p[j])&&(p[j]＞＝p[k])) u＝j； /*选取一个元素*/ else if ((p[i]＞＝p[k])&&(p[k]＞＝p[j])) u＝k； else u＝i； t＝p[u]； p[u]＝p[i]；