清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 while (i!=j) I while ((i<j)&&(plj>=t))j=j-1; if (i<j p[i]=p[j;i=i十1; while ((i<j)&&(pli]<=t))i=i+1 if (isj) p[j=p[i];j=j-1;} pli]=t; return (i)
9.1 互换类排序 while (i!＝j) { while ((i＜j)&&(p[j]＞＝t)) j＝j－1； if (i＜j) { p[i]＝p[j]； i＝i＋1； while ((i＜j)&&(p[i]＜＝t)) i＝i＋1； if (i＜j) { p[j]＝p[i]； j＝j－1；} } } p[i]＝t；return(i)； }
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 快速排序的非递归算法 输入:待排序的子表P(m:n)。 输出:有序子表P(m:n)。 PROCEDURE QKSORT2(P, m, n) 建立一个栈,并初始化 [栈中每一个元素有两个数据项:子表第一个元素下标与最后一个元素下标] 将下标m与n进栈 [子表进栈] WHILE栈非空D0 [还有子表需要分割] 从栈中退出两个下标m与n 从栈中退出一个子表进行分割] WHile (n>m) DO [子表不空 SPLIT(P,m,n,i)[进行分割] 将下标i+1与n进栈将分割出的后一个子表进栈] n=i-1 [对分割出前一个子表继续进行分割 RETURN
9.1 互换类排序 快速排序的非递归算法 输入：待排序的子表P(m：n)。 输出：有序子表P(m：n)。 PROCEDURE QKSORT2(P，m，n) 建立一个栈，并初始化 [栈中每一个元素有两个数据项：子表第一个元素下标与最后一个元素下标] 将下标m与n进栈 [子表进栈] WHILE 栈非空 DO [还有子表需要分割] { 从栈中退出两个下标m与n [从栈中退出一个子表进行分割] WHILE (n＞m) DO [子表不空] { SPLIT(P，m，n，i) [进行分割] 将下标i＋1与n进栈 [将分割出的后一个子表进栈] n＝i－1 [对分割出前一个子表继续进行分割] } } RETURN
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.2插入类排序 9.2.1简单插入排序 9.2.2希尔排序
9.2 插入类排序 9.2.1 简单插入排序 9.2.2 希尔排序
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.2插入类排序 9.2.1简单插入排序
9.2 插入类排序 9.2.1 简单插入排序
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.2插入类排序 简单插入排序 输入:待排序序列P(1:n) 输出:有序序列P(1:n)。 PROCEDURE INSORT(P, n) FOR j=2 to n DO it=P: k=j-1 While (k>0 and (P(k)>T) DO P(k+1)=P(k);k=k+1} P(k+1)=T RETURN
9.2 插入类排序 简单插入排序 输入：待排序序列P(1：n)。 输出：有序序列P(1：n)。 PROCEDURE INSORT(P，n) FOR j＝2 TO n DO { T＝P(j)；k＝j－1 WHILE (k＞0)and(P(k)＞T) DO { P(k＋1)＝P(k)；k＝k＋1 } P(k＋1)＝T } RETURN