清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 原序列 5173169 286 第1遍(从前往后)5←→17←→3←→1←→69←→4→2←→8←→6 结果15316742869 从后往前)15←→3←→16←→7←-←→28+→69 结果11532674689 第2遍(从前往后)115←→3←→267←→4←→689 结果113125646789 〔从后往前)113+→25←→6←→46789 结果11234566789 第3遍(从前往后)11234566789 最后结果11234566789
9.1 互换类排序
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 bubsort(p, n) int n; et pl; I int m, k, j,i; et d k=0;m=n-1; while(k<m)/*子表未空*/ j=m-1;m=0; for(i=k;i<=j;i++)/米从前往后扫描*/ if(p[i]>p[i+1])/*发现逆序进行交换* d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;}
9.1 互换类排序 bubsort(p，n) int n； ET p[]； { int m，k，j，i； ET d； k＝0； m＝n－1； while (k＜m) /*子表未空*/ { j＝m－1； m＝0； for(i＝k；i＜＝j；i＋＋) /*从前往后扫描*/ if (p[i]＞p[i＋1]) /*发现逆序进行交换*/ {d＝p[i]；p[i]＝p[i+1]；p[i+1]＝d；m＝i；}
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 j=k+1;k=0; for(i=m;i>=j;i--)/*从后往前扫描* if(p[i-1]>p[i])/*发现逆序进行交换*/ d=p[i];p[i]=p[i-1];p[i-1]=d;k=i; return:
9.1 互换类排序 j＝k＋1； k＝0； for (i＝m；i＞＝j；i－－) /*从后往前扫描*/ if (p[i－1] ＞p[i]) /*发现逆序进行交换*/ {d＝p[i]；p[i]＝p[i-1]；p[i-1]＝d；k＝i；} } return； }
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 9.1.2快速排序 分割 无 序 分制 线 分制
9.1 互换类排序 9.1.2 快速排序
清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 首先,在表的第一个、中间一个与最后一个元素中选取 中项,设为P(k),并将P(k)赋给T,再将表中的第一个 元素移到P(k)的位置上。 然后设置两个指针i和j分别指向表的起始与最后的 位置。反复作以下两步: (1)将j逐渐减小,并逐次比较P(j)与T,直到发现 个P(j)<T为止,将P(j)移到P(i)的位置上。 (2)将i逐渐增大,并逐次比较P(i)与T,直到发现 个P(i)>T为止,将P(i)移到P(j)的位置上。 上述两个操作交替进行,直到指针i与j指向同一个 位置(即i=j)为止,此时将T移到P(i)的位置上
9.1 互换类排序 首先，在表的第一个、中间一个与最后一个元素中选取 中项，设为P(k)，并将P(k)赋给T，再将表中的第一个 元素移到P(k)的位置上。 然后设置两个指针i和j分别指向表的起始与最后的 位置。反复作以下两步： (1)将j逐渐减小，并逐次比较P(j)与T，直到发现一 个P(j)＜T为止，将P(j)移到P(i)的位置上。 (2)将i逐渐增大，并逐次比较P(i)与T，直到发现一 个P(i)＞T为止，将P(i)移到P(j)的位置上。 上述两个操作交替进行，直到指针i与j指向同一个 位置（即i＝j）为止，此时将T移到P(i)的位置上