C++语言程序设计

算法：
在这里，我们介绍一种快速排序算法来解决这个问题。快速排序算法是一种递归定义的过程，其算法的基本思想是：在数组中，任取一个元素作为主元素，将数组分为左右两个部分，即产生了两个子数组：左侧部分的子数组和右侧部分子数组，且左侧部分的子数组的每一个元素均小于或等于主元素，右侧部分子数组的每一个元素均大于主元素。例如，对于list数组，假定我们取8作为主元素，则划分出的左右两个子数组如下：

然后，我们分别对左侧部分的子数组和右侧部分子数组重复使用上面的过程，相同过程的重复应用导致了递归的定义。可见，数组分割是快速排序的关键，下面以list数组为例，详细地介绍如何生成从左侧部分的子数组和右侧部分子数组。
假定有一个待排序的、下标范围为first ~ last的数组A，需要选取一个主元素pivot，并将A分为左侧部分的子数组L和右侧部分子数组R，且L中的每一个元素均小于或等于pivot，R中的每一个元素均大于pivot。主元素的选取，可以简单地用下式计算其在A中的下标：
(first + last) / 2
first和last分别是待排序数组的第一个元素和最后一个元素的下标。为了便于生成L和R，我们还需要两个临时变量left_arrow和right_arrow，它们的初值分别为数组A的最小下标和最大下标值。例如，对于数组pivot即有：

| 图7-16

从右边开始，我们将right_arrow左移，直至遇到一个元素值小于或等于pivot为止：

| 图7-17