原创力文档- 1、本文档共97页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
注： 算法对集合A(m:p-1)进行划分。并使用待划分区间的第一个元素A(m)作为划分元素 A(p)不在划分区间内，但被定义，且A(p）≥A(m)，用于限界 两点改进（参见严蔚敏的教材） （1）可以不交换元素； （2）无需假设A(p)。 例4.5 划分实例 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i p A: 65 70 75 80 85 60 55 50 45 +∞ 2 9 |……………………………………| A: 65 45 75 80 85 60 55 50 70 +∞ 3 8 |…………………………| A: 65 45 50 80 85 60 55 75 70 +∞ 4 7 |………………| A: 65 45 50 55 85 60 80 75 70 +∞ 5 6 |……| A: 65 45 50 55 60 85 80 75 70 +∞ 6 5 |……………………| A: 60 45 50 55 65 85 80 75 70 +∞ 划分元素定位于此 交换划分元素 (1) (2) (3) (4) (5) (6) (7) (8) (9) A: 45 70 75 80 85 60 55 50 45 A: 45 70 75 80 85 60 55 50 70 A: 45 50 75 80 85 60 55 50 70 A: 45 50 75 80 85 60 55 75 70 A: 45 50 55 80 85 60 55 75 70 …………………………………………….. A: 45 50 55 60 85 85 80 75 70 划分元素定位于此 交替移动元素 例4.5 划分实例（不交换元素） Pivot=65 65 65 70 75 80 85 60 55 50 45 经过一次“划分”后，实现了对集合元素的调整：其中一个子集合的所有元素均小于等于另外一个子集合的所有元素。 按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类过程称为快速分类。 3.快速分类 通过反复使用划分过程PARTITION实现对集合元素分类的算法。 算法3.13 快速分类 procedure QUICKSORT(p,q) //将数组A(1:n)中的元素A(p),…A(q)按递增的方式分类。 A(n+1)有定义，且假定A(n+1)←+∞// integer p,q;global n,A(1:n) if pq then j←q+1 //进入时，A(j)定义了划分区间[p,q]的上界，初次调用时j=n+1 call PARTITION(p,j) //出口时，j待出此次划分后划分元素所在的坐标位置// call QUICKSORT(p,j-1) //前一子集合上递归调用 call QUICKSORT(j+1,q
文档评论（0）