文件名称：快速排序-1985-2020历年数学建模美赛赛题（中文版）
文件大小：3MB
文件格式：PDF
更新时间：2024-07-13 19:24:44
程序设计 方法 架构 编程 面向对象
25．2 快速排序 生成递归的一个经典例子是霍尔快速排序算法。与第 12.2 章中的 sort 一样，qsort 是一个排序函数， 它读入一个数表，返回升序排列的表，表中包含相同的数。两个函数之间的区别是，sort 是基于结构递归 的，而 qsort是基于生成递归的。 生成步骤的基本思想是一种古老的策略：分而治之。换一种说法，我们把非平凡可解问题的实例分解 为相关的两个小问题，分别解决这两个小问题，再把它们的解结合起来，从而得到原问题的解。以 qsort 为例，先把数表分为两个表：一个表包含所有严格小于第一个元素的元素，而另一个表包含所有严格大于 第一个元素的元素；然后，对这两个（小的）表使用同样的方法排序；一旦这两个小表的排序完成了，只 需简单地把它们连接起来。由于第一个元素的特殊角色，我们把它称为关键元素。 (list 11 8 14 7) (list 8 7) (list 7) empty 7 Empty (list 7) 8 empty (list 7 8) 11 (list 14) empty 14 empty (list 14) (list 7 8 11 14) 图 25.2 quick-sort一个表格式的说明 为了更好地理解这个过程，我们用手工来计算其中的一个步骤。假设输入是 (list 11 8 14 7) 那么关键元素就是 11。把这个表分为大于和小于 11的两部分，可得如下两个表： (list 8 7) 和 (list 14) 这第二个表已经是按升序排列的了；对第一个表排序，可得(list 7 8)。这样，我们就把原来的表分成了三个 部分： 1． (list 7 8)，由小数组成的有序表； 2． 11；