数据结构浙江大学整理（1）

10.1 快速排序

10.1.1 算法概述

策略：分而治之。

下面举个例子，假如一组数为13/81/92/43/65/31/57/26/75/0，我们对其进行排序。那么首先选择出一个主元，这里我们选择为65，那么将这组数的其他成员分为了两组，一组是小于主元的13/43/31/57/26/0，一组是大于主元的81/92/75.然后将其递归处理，两边各选一个主元再进行分组……倒数第二步的时候，我们在第一步选择出来的主元左侧已经排好了顺序，右侧也排好了顺序，这样将它们放在同一个数组中，就完成了排序。

以下是上面这段话的伪码描述：

这个方法的关键在于主元的选取（选取不好，快速算法会很慢）和子集划分（这个过程也是耗费时间的一个地方）。

快速排序算法的最好情况就是每次正好中分，T(N)=O(NlogN)。

10.1.2 选主元

选取头、中、尾的中位数，也可以选取5个、7个等数字的中位数。例如8/12/3的中位数就是8。伪码描述如下：

10.1.3 子集划分

为了便于理解，还是举一个例子：

定义两个指针i（指向第一个元素）和j（指向中位数左侧的元素）。（继续强调，这里的i和j不是实际的指针，而是存储所需要元素下标的整数。）先比较i代表的元素和主元的大小，发现8大于6，那么i这个指针不变；然后看j代表的元素和主元比较，发现7大于6，将j减一（即左移一位），然后再比较，发现2小于6，这样就不对了，j停止移动。在i和j都停止移动后，将其所指向的两个元素交换位置，变成了下面这个样子。

然后i加1（右移一位），1小于6，正常，i继续加1（右移一位），4小于6，正常，i继续加1（右移一位），此时9大于6，不正常，i停止；再看j减1（左移一位），5小于6，不正常，j停止，然后交换此时i和j所代表的元素，变成下面这个样子。

然后i加1（右移一位），发现正常，i继续加1，发现正常，i再加1，发现9小于6，不正常，i停止；然后j左移一位，发现3小于6，不正常，停止。

此时发现i-j

快速算法的“快速”在于，划分完成后其主元被一次性放到了正确的位置再也不会移动；例如插入算法等都需要一步一步往后移。

如果有元素正好等于pivot怎么办？停下来处理。

对于小规模数据还不如用插入排序。当递归的数据规模充分小，则停止递归，直接调用简单排序。在程序中定义一个Cutoff的阈值。

10.1.4 算法实现

伪码描述：

为了统一接口，在上段程序后面再加一个：

快速排序算法是不稳定算法！

以下给出另外的C语言编写的代码，它是直接调用函数库：