SOFTWARE

—PRACTICE AND EXPERIENCE, VOL. 23(11), 1249–1265 (NOVEMBER 1993)

Engineering a Sort Function

原文： 

译者：黑狗      Email:blackdog1987@gmail.com

JON L. BENTLEY

M. DOUGLAS McILROY

AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ 07974, U.S.A.

简述

    我们重写了一个新的快排函数来替换C包中原有的。我们的函数比现存的排序方法更加清晰，快速和健壮。他利用新的抽样组合选择了划分元素；它的划分是根据Dijkstra的荷兰国旗问题来的。他的交换也变得更加高效了。我们已经根据时间，调试台来评估了他，同时用了一个程序来证明它。这个设计技术已经从很多领域中都超越了排序的范畴。

介绍

    快排在很长一段时间里都被包含在C包中，用于数组排序。通常都是使用由Hoare实现的快排1。由于现存的排序存在着缺陷，所有我们重新创建了一个。本文概述了他演变的过程。

    和现存的排序相比，我们的新方法更快——通常快两倍；在非随机的输入时，更清晰和健壮。他采用了标准的快排技巧，放弃了其他的，同时也介绍了一些我们自己的新的技巧。我们创造一个快排是和创建其他算法是有联系的。

    我们本地系统中的快排以Scowen的‘QuickerSort’2为基础。大约从20年前Lee McMahon完成他以后开始，它（Scowen快排）就忠实的服役着。在Unix系统第七版3采用这个快排以后，它更是变成了快排的一个模型。不过1991年夏天，我们的同事Allan Wilks和Rick Becker发现，这种快排可能会花费数分钟，而同时占据CPU数小时。如果他们不手动中断他的话，他可能会运行数周4。他们发现当对一个叫做organ-pipe（wiki上还没有organ pipe的中文版，谁去补充下）的数组进行排序的时候，他会花费n^2。这个数组含有2n个元素，他的排列就像这样：1,2,3，...n，n...，3,2,1。

    在寻找一个更好的快排方法的时候，我们发现Berkeley在1983年编写的快排，如果数组中存在许多重复的元素——特别是由随机个0和1组成的数组，将耗费二次方的时间。事实上，在众多不同的unix包里，我们从Berkeley的83年的第七版快排可以推断出，没有哪个快排可以驾驭这种二次方的行为。而且第七版中的快排和很多其他版本还有一个其他的毛病。因为他采用的是静态的存储方式，所以他在对比函数中被递归的调用或者在多线程中被调用的话会失败。

    我们没有找到一个足够好的快排方法，我们打算自己创造一个更好的。这个算法应该避免在特定的输入情况下性能于极限下降，在随机的输入时，他有也应该非常的快。他在数据空间和代码空间上应该非常高效。他也不需要太稳定，他的规格说明中没有承诺要保证相同元素的原始顺序。

0038-0644/93/111249–17$13.50                        Received 21 August 1992

©1993 by John Wiley & Sons, Ltd.                       Revised 10 May 1993

快排接口

    我们摆脱掉他的暗示性的名字，一个快排函数兵不一定要实现Quicksort（这里的Quicksort应该是某个接口）。我们首先用插入排序来实现他，尽管他慢了一些，但接下来我们将发现他可以提供一种优质的排序。我们先从iisort这个函数开始，将数组a中的n个元素进行排序。不过这里的排序缺少排序接口。（整篇将采用这样的命名规则，iisort中的第一个i表示整型，第二个表示插入，也就是integerInsertSort。）这个算法中，变量i从第二个一直到数组的最后一个元素；变量j用于将第i个元素插入到之前的子数组的适当位置。

void iisort(int *a, int n) { int i, j; for (i = 1; i < n; i++) for (j = i; j > 0 && a[j-1] > a[j]; j--) iswap(j, j-1, a); }

   Iswap函数用于交换a[i]和a[j]，插入排序在任何排列的数组情况下，都花费n^2/4，而决不会花费n^2/2。Iisort函数只能对整型排序，现在我们用一种通用的接口，像这样[1]：

void qsort(char *a, int n, int es, int (*cmp)());

    第一个指针参数表示需要排序的数组，后两个参数代表元素个数和元素的比特大小。最后一个参数表示一个需要两个指针参数的比较函数。根据第一个参数和第二个参数的小于，等于，大于关系分别返回小于，等于，大于0。以下是一个典型的比较函数和非负整数数组的排序例子。

void swap(char *i, char *j, int n) { do { char c = *i; *i++ = *j; *j++ = c; } while (--n > 0); } * Program 1. A simple swap function int intcomp(int *i, int *j) { return *i - *j; } ... qsort((char *) a, n, sizeof(int), intcomp);

[1]We have used simple parameter declarations for readability. The official prototype in the ANSI standard

header file, <stdlib.h>, is6

void qsort(void *, size_t, size_t, int (*)(const void *, const void *));

This declaration can be used no more honestly than ours. The first argument compels casting in the source of

qsort; the last compels casting in programs that call it. In practical terms, though, our declaration precludes

portable compatibility with library qsorts. Hence we will change the int parameters to size_t in our production model, Program 7.

   我们利用标准的字符串比较函数strecmp来对一个以空字符结尾的长度为len字节的字符串数组来排序。

qsort(a, n, len, strcmp);

    用另一个级别上的strcmp来间接的对字符串指针数组排序。

int pstrcmp(char **i, char **j) { return strcmp(*i, *j); } ... qsort(a, n, sizeof(char *), pstrcmp);

    我们将iisort改变为一个类似于qsort的函数，以此来简单的进行重写。

void isort(char *a, int n, int es, int (*cmp)()) { char *pi, *pj; for (pi = a + es; pi < a + n*es; pi += es) for (pj = pi; pj > a && cmp(pj-es, pj) > 0; pj -= es) swap(pj, pj-es, es); }

    在Program 1中定义的函数swap(i,j,n)用于交换指向i和j后的n字节数据域。在后文中我们将进一步讨论交换。

一个简单的快排

    快排是一个分治的算法：划分数组，将小元素置于左边，大元素置于右边，然后对两个子数组进行递归。Sedgewick在他的博士论文7和此后的文章8-10中研究了快排；在文章11, 12和参考文献13中进行了大量的描述。

    Program 2是一个零碎的快排，他采用了Lomuto的划分策略。14代码从数组的第一个元素进行花费，最后将他置于a[j]。我们调用iqsort0(a, j)对左子数组a[0..j-1]进行排序。用C指针算法和iqsort0(a+j+1, n-j-1)对右子数组a[j+1..n-1]进行排序。Hoare证明了在n个随机排列的元素，快排将花费Cn≈2nlnn≈1.386nlgn次比较。不幸的是Program 2在有的时候会更慢。对一个有序数组进行排序时，大致会进行0.5*n^2。为避免此情况，Hoare建议利用随机元素进行划分。不过Program 2对相同数组进行排序时仍然用了平方级的时间。

void iqsort0(int *a, int n) { int i, j; if (n <= 1) return; for (i = 1, j = 0; i < n; i++) if (a[i] < a[0]) swap(++j, i, a); swap(0, j, a); iqsort0(a, j); iqsort0(a+j+1, n-j-1); } Program 2. A toy Quicksort, unfit for general use

    一个更加高效的（也是更为常见的）划分方法是利用两个索引变量i和j。索引i从数组的地步开始扫描，直到一个大元素（大于或等于划分元素）停止，j向下扫描，直到小元素停止。然后将这两个数组元素交换，继续扫描，直到这两个指针相遇。

    这个算法很容易被描述，也很容易出错——Knuth讲述了关于低效划分算法的故事。15我们根据Sedgewick的不变式7来避免这些问题：

 

    在元素a[0]进行划分，图中标注为T。增长到i，之前的元素都小于T；在找到大于或等于T的元素时，j开始向下扫描。当他们都停止时，交换两个元素，继续扫描的过程。（在两个内部的循环中，在相等元素处停止是非常重要的，Berkeley的快排在处理随机个0和1的数组时，花费平方级的时间是因为他扫描了相等元素；试试举一个例子来理解他的原因。）在划分循环的最后，i=j+1.交换a[0]和a[j]：

    现在在子数组a[0..j-1] 和a[j+1..n-1]中递归调用qsort。

    Program 3结合了这些理念，运用到了一个清晰，高效的专用于整型的Quicksort方法——对于创建一个更为精心制作的方法来说这是一个好的开端。Program 4就是这样的一个函数，他支持qsort接口。它只有第七版的qsort的三分之一大小，平均速度仍然快20%，同时避免了低效的平方级的情况。这是我们最终算法的雏形。

一个开销模型

void iqsort1(int *a, int n) { int i, j; if (n <= 1) return; i = rand() % n; swap(0, i, a); i = 0; j = n; for (;;) { do i++; while (i < n && a[i] < a[0]); do j--; while (a[j] > a[0]); if (j < i) break; swap(i, j, a); } swap(0, j, a); iqsort1(a, j); iqsort1(a+j+1, n-j-1); } Program 3. A simple Quicksort for integers

void qsort1(char *a, int n, int es, int (*cmp)()) { int j; char *pi, *pj, *pn; if (n <= 1) return; pi = a + (rand() % n) * es; swap(a, pi, es); pi = a; pj = pn = a + n * es; for (;;) { do pi += es; while (pi < pn && cmp(pi, a) < 0); do pj -= es; while (cmp(pj, a) > 0); if (pj < pi) break; swap(pi, pj, es); } swap(a, pj, es); j = (pj - a) / es; qsort1(a, j, es, cmp); qsort1(a + (j+1)*es, n-j-1, es, cmp); } Program 4. A simple qsort

    在我们提高Program 4的速度之前，我们需要了解关键操作的开销。Bentley，Kernighan和Van Wyk描述了一个程序，他可以对特定的硬件/软件系统通常的C操作进行开销评估。我们修改了这个程序以便测量大约40个一般排序操作。Table 1显示了在VAX 8550上用ANSI C的lcc编译器时数十个典型操作的开销。

    在这系统中，固定操作花费了数十微秒；比较操作从从数十微秒后开销继续增加，交换4字节域也花费了数十微妙。（strcmp的开销用于比较2个只在最后一个字节不相同的10字节字符串）

    和Program 1的差异之处在于swap函数。如附录所示，在其他的系统中甚至开销更大。这里有几个原因：循环中的4字节的交换，循环维护了两个指针和一个计数变量，函数的调用序列花费了数微秒。作为一个基准，在内联的代码中交换两个整型仅仅只需要不到1微秒。在附录中，swap代码进行了调整，以处理这些普遍性的特殊情况。我们使用了内联的交换方式处理整型大小的对象，否则才调用函数。这使得交换两个4字节域开销降低到了大概1微秒。

    调整以后的交换函数花费了大约3倍于固定操作时间，比较过程花费了3倍于交换函数的时间。非常戏剧性的是这个专门处理整型排序的开销比率在教科书式的分析中被认为是非常沉重的，不过（实际上）他的比率却不是这样。在Knuth的MIX程序中的经典例子中12就有这个整型的模型，他的比较过程开销几乎和固定操作一样，交换操作却花费了数倍的时间。这两个模型可以这样来概括：

MIX:  overhead≈comparisons < swaps qsort:  overhead < swaps < comparisons

    第二个模型反映出，通常以函数方式进行比较的qsort接口并不是机器原语。Linderman在他对Unix的排序功效的论述中认为这种和MIX模型不相称的原因是：‘因为比较…是解释性的，他通常比直接用标准的范式来比较两个整型要花费更多的时间。当一个同事和我在对排序进行修改以增强他的可靠性和高效性时，我们发现有时候一些用于提高其他排序应用的技术在对排序（Unix的排序）进行处理时反而起到了反作用’。18

选择一个划分元素

    采用随机元素划分大约会花费Cn≈1.386n lg n次比较。我们现在对函数中的常数进行削减。如果我们足够好的话，每次都选择了子数组中的中值，我们可以讲比较次数降低到nlgb。在缺少真正的中值时——他的计算太过耗时，我们寻找一个快捷的近似值。

           Hoare打算使用数组元素中的一个小例子的中值。Singleton建议使用数组开始，中间和最后一个元素的中值。在随机的元素中进行花费，在中值附近的期望值降低到了Cn, 3≈12/7nlnn≈1.188nlgn。不过和Quicksort最初的Cn/6次交换比起来，三个数的中值花费将交换的效率提高到了Cn, 3/5，大约提高了3%。12

static char *med3(char *a, char *b, char *c, int (*cmp)()) {  return cmp(a, b) < 0 ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a) : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a); } Program 5. Decision tree and program for median of three

    Program 5通过qsort比较函数找到了三个数中的中值。决策树评估比较了2-3次（平均8/3次）而不进行交换。

    通过更多的努力来寻找中央元素，我们可以讲比较的效率提高到接近nlgn。我们采纳了Tukey的“9分法”，从3段中的中值中再选择其中值。Weide分析了这种伪中值的质量。这种九分法提供了一个在开销上更加平衡的递归树，他最多只额外比较了12次。虽然他在大数组中非常高效，不过在小数组中效率就低了。因此，我们的最终代码中选择了较小数组中的中间元素，中型数组中选择了首位和中间元素的中值作为划分元素，对于大数组则采用了九等间距的伪中值。在下面的代码中，对于大小的划分是凭借经验所决定的。

pm = a + (n/2)*es; /* Small arrays, middle element */ if (n > 7) { pl = a; pn = a + (n-1)*es; if (n > 40) { /* Big arrays, pseudomedian of 9 */ s = (n/8)*es; pl = med3(pl, pl+s, pl+2*s, cmp); pm = med3(pm-s, pm, pm+s, cmp); pn = med3(pn-2*s, pn-s, pn, cmp); } pm = med3(pl, pm, pn, cmp); /* Mid-size, med of 3 */ }

    这个方案在递增，递减等很多非随机输入的情况下表现得很好。我们可以找到更具想象力和随机化的例子，不过库排序的随机数产生器没有业务上的副作用。

    我们尝试着寻找这种算法关于比较的平均次数的平均值。我们将n设置为2的幂，从128到65536。用随机的30比特的整型创建了11组n，然后利用Program 4对比较的次数进行记录。我们采用赋权最小二乘法回归后的结果符合这样的函数1.362nlgn − 1.41n，而这和理论上的1.386nlgn+O(n)相近。同样我们选择合适的方案对Program 7进行了实验，结果是他花费了1.094nlgn-0.74n次比较。这比起随机选择一个元素来说是一个本质上的提高，他接近了下限的nlgn-1.44n。

一个时序测试

    我们创建了一个简单的测试台来处理随机数据的快排。他有5个输入：排序程序的名称，被排数据的数量、类型，需要被减少的系数，被实验的次数。下面就是这个交互会话。

                                               q7   10000   i   50000   3

                                               q7   10000   i   50000   3   73   77   68   9.11

                                               q1   10000   i   50000   3

                                               q1   10000   i   50000   3   55   56   58   7.07

    用户键入第一行，请求第七版的qsort（q7）函数处理10000个整型的数组，模5000，执行三次试验。程序打印出第二行，回显出5个输入域和3次执行后所花费的软件时间（VAX上它代表1/60秒。最后一个域表明拍苏所花费的平均时间为9.11nlgn微秒。第三行请求和Program 4（q1）相似，第四行表明了执行的平均时间为7.07nlgn微秒，大约比第七版的qsort快20%。

    整型的比较和交换都很便利；排序的主要开销在于固定操作。对于对相同的集合进行排序时的性能，测试台揭示了他们的固定操作，交换和比较相关表现中的开销列表。单精度浮点型数字的交换和整型需要相同的空间，不过比较的时候稍微费时一些。双精度比这两种类型更慢。对于20字节的记录，其前4字节为整型键的数据，他的比较较快，交换较慢。20字符的字符串，其前5个空间为十进制整数，他的比较和交换都较慢。最终，指向后者的指针，比较较慢，交换较快。

相等元素的机会

    我们最初的性能目标是对于大多数输入都有很好的运行时间。再三考虑后，我们决定不为特定种类的输入的快速执行而调整代码，比如“几乎已排序的数组”，尽管别人已经发现了这种有效的方法。21,22我们很快就屈服于极限位置了。

    我们在本地第一次提出的快排版本是本质上就是采用适当划分的Program 4。一个友善的朋友发现新的快排在特别的情况下比现存的快30%-40%。不过他也报告了在很多相同元素的情况下，我们的快排性能会轻微的降低，而第七版会骤减。我们对这个聪明的位置选择做出了解释，对此他公正的回答道，很多用户常常恰巧引入了很多相同元素作为输入，在这种情况下库程序是如此的低劣。而对其进行替换真是难以想象的。

    我们的试验台显示了对100,000个随机的模2的整数（0和1）进行排序，Program 4花费的时间是第七版排序的8倍。

                                              q1  100000  i  2  3  768  756  756  7.63

                                              q7  100000  i  2  3   96   93   91  0.94

    在相同元素的数组中，Program 4在一个完美平衡递归树中对所有可能的元素进行交换。然而第七版快排使用了‘丰满划分’，仅仅在对元素进行了一次扫描。因此我们进一步的寻找排序众多相同元素的高效方法，在处理不同元素的时候性能不至于下降。（Sedgewick分析了对相同元素进行标准快排的性能。9）

    在我们之前的代码中，划分将输入分为了两个子序列，丰满划分将他划分为了三个：

    在划分以后，相同的元素被放在了子数组的末尾，在中部的相同元素被忽略。

    三等分划分和Dijkstra的‘荷兰国旗问题’是相同的。许多程序（包括Dijkstra的和第七版快排）采用下面这种不变式：

   这个所给的代码是复杂并且低效的。在左边相同的元素需要花费额外的O（n）用于筛选他们并交换到中部。为了得到一种更高效的丰满划分，我们转向另外一种不变式。

 

    在划分完成以后，交换两边划分的外部相同元素到中部。尽管这个不变式已经可以工作了，不过一种对称的版本会使得代码更清晰：

    随着下标b的移动，扫描所有较小元素（小于所选的划分元素），将相同元素移动到外围，用小标a进行记录，当碰到较大元素时停止。将c小标向前移动，交换b和c所指元素，调整指针，继续执行（像左半部一样）（Wegner恰好建议这种不变式，不过采用了更复杂的三向交换法来维护他。24）如此达到了将相同元素从末尾交换到中部的目的。Program 6展现了这种‘尾部分离’划分的整型快排。简单起见，他选择了一个随机的划分元素。

void iqsort2(int *x, int n) { int a, b, c, d, l, h, s, v; if (n <= 1) return; v = x[rand() % n]; a = b = 0; c = d = n-1; for (;;) { while (b <= c && x[b] <= v) { if (x[b] == v) iswap(a++, b, x); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) iswap(d--, c, x); c--; } if (b > c) break; iswap(b++, c--, x); } s = min(a, b-a); for(l = 0, h = b-s; s; s--) iswap(l++, h++, x); s = min(d-c, n-1-d); for(l = b, h = n-s; s; s--) iswap(l++, h++, x); iqsort2(x, b-a); iqsort2(x + n-(d-c), d-c); } Program 6. An integer qsort with split-end partitioning

    尾部分离划分通常都很高效。当所有元素均不相同时，他只交换未排序的元素。当元素主要为相同元素的时候，他花费时间用于把他们从尾部交换至中部。不过我们可以将开销进行分摊，以此，在递归调用中不处理这些相同元素。对1,0数组，我们最终的，采用尾部分离划分（Program 7）的快排大约比第七版快排快两倍。

    丰满划分允许我们减轻Program 3，Program 4中的另外一个缺点。在倒序排列或者几乎是倒序的排列中，交换划分元素到头部所带来的乱序是耗时的。（试试举一个例子来悄悄为什么。）Program 6将划分元素拷贝到一个变量v中，而不是交换他。通过这个诀窍，加速效果是难以置信的，甚至是另一个数量级。尽管如此，平均情况会轻微的降低性能，因为划分扫描的是n个而不是n-1个元素。我们在平均速度上证明了这个小小的损失——在最后的程序中他在2%以下。用户抱怨说对于简单的输入他的排序并不快。相同的心理促使我们首先采用了丰满划分。

另一些改进

    现在我们有了一些高效排序所需的成分：将尾部分离划分和一个适当抽样划分元素结合起来。Program 7结合了一些额外的特征，以增加速度和可移植性。

    1. 我们采用了一种高效的swap宏和一个另外的宏SWAPINIT来建立他；他们在附录中已经给出

    2. 如果方便的话，在Program 6使用宏PVINIT将划分元素保存于临时变量中，而不是像Program 4那样保存在a[0]中。

    3. 尽管快排处理大数组非常高效，但他的固定操作（overhead）对于小数组来说就显得太严苛了。因此对小数组排序时我们使用了老的技巧，插入排序。

    4. 我们使用了一个测试if(n>1)来监控对第n个元素的快排的递归调用

    5. 在Program 6中，在循环中使用swap来将相等元素交换到数组中部的时候，我们采用了一个新的方法，vecswap。在数据存在大量重复的键时，vecswap在整个排序过程中将节省20%时间。

    6. Program 7在使用了三个整数（7,7,40）来选择采用插入排序和多种划分方式。尽管这三个值是根据我们本地机器来调整的，这个设置仍然是显得健壮的。（组成这种范围的整数7是可以被废除，但也是可调的，因为在有的机器上大范围表现的更好。）

    7. 在VAX上，第七版快排的目标代码占了500字节，而Berkeley快排需要1000字节。在我们的排序的早期版本中，代码更是增加到了3000字节。在一个‘空间分析器’的帮助下显示出了每一行所占的字节数，我们将代码精简到1000字节。最大的精简之处在于将代码从宏移动到函数中。

    8. 参数size_t符合标准头文件<stdlib.h>中的原型，而其他的参数不符合。保持一致性需要更多的强制转换。参数不匹配将会常常发生。但Program 7在大多数系统中可以完全作为库函数使用。

    我们还没有采用很多习惯性的改进。通过管理私有栈，我们可以将栈空间从每级20个变量削减到2个。通过最后对划分元素较大边进行处理和消除尾递归的方式，我们可以将最坏情况的栈增量从线性降低到对数级。他们都不值得我们这样努力来做。（非性能瓶颈）因为所需的栈是logn，跟数据比起来他就显得微不足道了——当n=1,000,000时只需要2000字节。在下一章的描述中，栈深度至多达到最小可能深度的三倍。另外，如果最坏情况性能是重要的话，快排算法是错误的选择。（对于一个快速内存故障来说，在执行最坏情况操作时甚至情愿花费数周的周期来运行。）

    这是一些优化的其他著名方式，而我们并没有涉及的。

    1. 在递归的底层，Sedgewick使用了大数组的最终插入排序，而不是采用小数组的7。他用一个在数组元素中简单的比较，替换了很多固定操作。他在MIX开销模型中很好，而在我们的模型中他失败了。

    2. 在MIX开销模型中数组末尾哨兵增加了速度，在我们的模型中他失败了。总之他违背了快排的规格说明。

    3. 在插入排序中许多的改进都没有起到作用，包括二分查找，循环展开，将n=2作为特殊情况处理。最简单的代码是最快速的。

    4. 在选择划分元素时，更加详尽的采样方案比九分法更低效。

    5. 我们知道在有的情况下他会成功，但拒绝对特殊机器和编译器8做特殊情况处理（#ifdef和register）

void qsort(char *a, size_t n, size_t es, int (*cmp)()) { char *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv; int r, swaptype; WORD t, v; size_t s; SWAPINIT(a, es); if (n < 7) { /* Insertion sort on smallest arrays */ for (pm = a + es; pm < a + n*es; pm += es) for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es) swap(pl, pl-es); return; } pm = a + (n/2)*es; /* Small arrays, middle element */ if (n > 7) { pl = a; pn = a + (n-1)*es; if (n > 40) { /* Big arrays, pseudomedian of 9 */ s = (n/8)*es; pl = med3(pl, pl+s, pl+2*s, cmp); pm = med3(pm-s, pm, pm+s, cmp); pn = med3(pn-2*s, pn-s, pn, cmp); } pm = med3(pl, pm, pn, cmp); /* Mid-size, med of 3 */ } PVINIT(pv, pm); /* pv points to partition value */ pa = pb = a; pc = pd = a + (n-1)*es; for (;;) { while (pb <= pc && (r = cmp(pb, pv)) <= 0) { if (r == 0) { swap(pa, pb); pa += es; } pb += es; } while (pc >= pb && (r = cmp(pc, pv)) >= 0) { if (r == 0) { swap(pc, pd); pd -= es; } pc -= es; } if (pb > pc) break; swap(pb, pc); pb += es; pc -= es; } pn = a + n*es; s = min(pa-a, pb-pa ); vecswap(a, pb-s, s); s = min(pd-pc, pn-pd-es); vecswap(pb, pn-s, s); if ((s = pb-pa) > es) qsort(a, s/es, es, cmp); if ((s = pd-pc) > es) qsort(pn-s, s/es, es, cmp); } Program 7. The final qsort; see Appendix for macro and type definitions

性能证明

    我们很好的留意到了Wirth的建议：“很明显基于快排的算法就像是赌博一样，大家都应该知道自己在运气非常差的时候需要付出多大代价”25。不过我们确信我们的快排不会因为某种输入导致性能急剧下降。因此我们模仿Knuth的演讲来测试TeX：“我们陷入了我能想象的最低劣的恶心的心情中，写出了我能想象的最恶心的代码，转过身将它嵌入到了更加恶心的构造之中，他是那么的令人怒不可遏”26。对于相对简单的快排，和关心正确性一样我们同样关心性能。我们的证明过程被Lyness和Kaganove称为一个“性能概况”27。他产生了最不利的输入，这是我们在各个文献中能找到的最困难的情况。对他进行排序，抱怨他产生了过多的比较。我们测试了整型和双精度类型，以此来评估对不同划分元素的处理情况。详细情况在Figure 1中进行了补充。

for n in { 100, 1023, 1024, 1025 } for (m = 1; m < 2*n; m *= 2) for dist in { sawtooth, rand, stagger, plateau, shuffle } for (i = j = 0, k = 1; i < n; i++) switch (dist) case sawtooth: x[i] = i % m case rand: x[i] = rand() % m case stagger: x[i] = (i*m + i) % n case plateau: x[i] = min(i, m) case shuffle: x[i] = rand()%m? (j+=2): (k+=2) for type in { int, double } test copy(x) /* work on a copy of x */ test reverse(x, 0, n) /* on a reversed copy */ test reverse(x, 0, n/2) /* front half reversed */ test reverse(x, n/2, n) /* back half reversed */ test sort(x) /* an ordered copy */ test dither(x) /* add i%5 to x[i] */ Figure 1. A qsort certification program in pseudocode

    在Figure 1中的每个调用qsort的测试中，使用了cmp函数，计算比较次数，超过Anlgn的情况，A代表1.2。如果比较的次数过多（A代表10），排序被终止（使用C longjmp）。尽管程序只列举了4种不同的n值，快排递归调用了很多小于n的值，这将冲掉算法中n=7和n=40附近的潜在故障。函数test检查了一个可信排序的答案，通过这种方式我们找到了许多故障。

    这个性能测试报告了第七版快排的organ-pipe故障，发现了Berkeley的代码中，关于随机的多个0和1的故障以及其他问题。（例如，前半部分倒序排列，模4的“锯齿”比期望的慢8*n倍）

    相比之下，Program 7显得比Program 4，堆排序（正如预料的那样）和冒泡排序更健壮[1]。Program 7中使用的比较次数超过了阀值1.2nlgn。long-size情况下不到1%，总共不到2%。数值并没有超过1.5nlgn。最彻底的不利测试是双精度的翻转洗牌。

排序比较

    和两个主要的竞争对手，第七版和Berkeley快排，我们的程序除了划分元素选择策略以外，更精简和友好。主要的函数仅仅包含48行代码，而第七版中需要80行，Berkeley需要117行。（由Unix的cb工具打印出，所有不含注释的代码，依次为89,102,153。）我们的程序展示了对于简单输入无二次方情况的表现，这令他的前辈们感到非常难受。

    为了对时间进行评估，我们在不同架构的计算机中运行：VAX8550，40MHz MIPS R3000（64-千字节数据，指令缓存，一兆字节的二次缓存），均采用lcc编译器。Table II显示了对10,000个从0-999,999中的整数进行排序的情况。每个时间都是执行10次的平均时间。在两种机器上，我们的快排确实比Berkeley和第七版快。但是快多少呢？执行时间上的改进根据不同的机器和数据类型快20%到12*n%。（最大的n主要是由swap操作所决定的，在附录中有所说明）在所有情况下，新的代码在我们的和Berkeley的快排中都进行了足够的改进。

    我们所考虑的快排实现不是根据Quicksort而实现的。P.Mcllroy的归并排序保证了最差性能为O（nlogn），这几乎是处理剩余元素最佳的方法（他在运行Figure 1这种高度非随机化的证明式数据时，比Program 7快2倍），但需要额外的O（n）的内存21。Floyd提出了一个高效的但是并不是太出名的堆排序变种，他花费nlgn+O(n)比较，但需要几乎同样多的交换操作，是Quicksort的4倍5。这些算法在某些上下文时击败了我们的快排，在其他的一些情况中却输了。权衡之下我们的方法是一个一般快排的实现选择。

    为了说明一般快排接口的开销和Program 7中的优化，我们专门从两个方面来进行说明。第一种特别的排序只针对指针大小的对象，因此消除了参数es，降低了交换的开销。一种更进一步的排序只针对整型，因此消除了参数cmp和调用他的固定操作。Table III对这几种情况进行了比较，采用了基本的Program 3来对100,000个随机整型进行排序。对于通常的VAX，唯一有用的特殊化是消除调用cmp的固定操作。对于高度管道化的MIPS，更有用的特殊化是简化swap代码，他能消除一个条件语句分支。相对于简单的Program 3，Program 7的改进取得了一定的成功。这并不令人感到难以置信，他的改进在于在面对非随机输入和需要大量开销进行交换的输入时，保持其高效性。随机的整数不做如此要求。

[1] Of course, quadratic behavior is still possible. One can generate fiendish inputs by bugging Quicksort: Consider key values to be unknown initially. In the code for selecting a partition element, assign values in increasing order as unknown keys are encountered. In the partitioning code, make unknown keys compare high.

    理论上讲，Program 7比我们所希望的情况拥有更多的变量也更依赖宏。注意到这一点以后，Ken Thompson延展了Program 4，使用更简单的取值来达到高度一致的性能。Thompson的程序采用了三段中值划分，一个内嵌的带有函数参数的过程。这些参数同时处理了交换和比较的过程。他使用了迭代而不是尾递归。他的编译只占到了Program 7的一半空间，但在平均情况下只慢了很少的程度。不过在Program 7中，低熵的输入却戏剧性的击败了他（Thompson的方法）。（在Figure 1中比较总次数超过了1.5nlgn）在这里他成为了Program 7中并发症的缘由。

结论

    在Quicksort包中我们增加了一些新的技巧：一个适当的采样用于选择划分元素，一个新的划分算法，快速的交换代码，更恰当的开销模型。我们将其和一些老的技巧相结合，放弃了很多其他的技巧，最终找到了优胜者，Program 7。许多的这些技术直接御用到了其他的排序和选择算法中。这个算法的历史向我们阐述了排序以外更多的东西：

 1.简单。性能的关键是高雅而不是针对特殊情况的特种营。促使可怕的调整的情况应该被避免，除非结果非常的显而易见。

 2.性能分析工具。一个函数时间概况告诉了我们CPU的运行周期，线性计数概况告诉了我们原因。一个开销模型让我们队关键操作进行了大概的评估。我们有时会使用算法动画系统来制造排序函数的影片4。

 3.计时和调试试验台。一个很小的驱动程序让我们瞥见到程序；一个更复杂的调试台使用更有趣的方式来实验他。试验台检查了正确性，比较次数和CPU占用时间。

 4.测试和证明。关键算法的正确性和性能的有效性应该被程序所证明。

鸣谢

  我们非常感谢Daniel Carrai，Clarkson，Steve Fortune，Chris Fraser，Eric Grosse，Dave Hanson，Andrew Hume，David Johnson，Brian Kernighan， John Linderman，Peter McIlroy，Bob Sedgewick，Ken Thompson，Howard Trickey and Peter Weinberger，感谢他们提供了有帮助的输入。

附录：调试swap函数

    在所有的调试问题中，交换是在不同的硬件和编译器上最为敏感的。Table IV显示了交换能有多大的区别。第一个入口显示了以内嵌方式交换4字节的开销；其他的入口显示了通过子程序交换单词敏感和字节敏感的字符串。VAX的世界是可预见的：内嵌的交换更快，其次是调用无进位加减法固定操作，根据字符来交换整型比交换长整型多花费3倍时间。不过在MIPS机器中，时间比大约是15。总共有4个因素决定：第一个因素是长整型到字符型的比率，第二个因素是将一个字节写入到单词中，便于下一次读取时采用了缓冲接口。不过，第七版和Berkeley快排常常交换字符敏感的，在这种机器上他们会慢很多。

    Table IV引导我们采用内嵌交换和字长块的交换。因此，对于重要的字长对象的特殊情况（特别是指针或者整型）我们使用内嵌交换。对于更复杂的交换，我们调用一个函数swapfunc，他按照顺序对对象进行区分，确认实际占据多少个正确对其的字。我们选择了长整型作为一般字长。这种交换采用一个swaptype变量，在单独的对象时他为0，在按字交换时他是1，按字节交换时，他是2。这个变量的设置是通过宏SWAPINIT：

typedef long WORD; #define W sizeof(WORD) /* must be a power of 2 */ #define SWAPINIT(a, es) swaptype = \ (a-(char*)0 | es) % W ? 2 : es > W ? 1 : 0

    交换函数变为了一个宏，选择函数调用还是内嵌交换。

#define exch(a, b, t) (t = a, a = b, b = t) #define swap(a, b) \ swaptype != 0 ? swapfunc(a, b, es, swaptype) : \ (void)exch(*(WORD*)(a), *(WORD*)(b), t)

    另一个宏交换记录的序列：

#define vecswap(a, b, n) if (n > 0) swapfunc(a, b, n, swaptype)

    这些宏的函数调用是直接的：

#include <stddef.h> static void swapfunc(char *a, char *b, size_t n, int swaptype) { if (swaptype <= 1) { WORD t; for( ; n > 0; a += W, b += W, n -= W) exch(*(WORD*)a, *(WORD*)b, t); } else { char t; for( ; n > 0; a += 1, b += 1, n -= 1) exch(*a, *b, t); } }

    作为“相等元素的机会”的解释，我们不按照一致性存储划分元素而不是将他和a[0]交换。这个改进在C中是麻烦的，除非元素的被解决，这样我们就可以仅仅在对字长对象特殊的情况下进行调整。变量pv用于指向a[0]或者已经被使用的变量v。这个宏像这样进行设置：

#define PVINIT(pv, pm) \ if (swaptype != 0) pv = a, swap(pv, pm); \                              else pv = (char*)&v, v = *(WORD*)pm

参考文献

1. C. A. R. Hoare, ‘Quicksort’, Computer Journal, 5, 10-15 (1962).

2. R. S. Scowen, ‘Algorithm 271: quickersort’, Communications of the ACM, 8, 669-670 (1965).

3. B. W. Kernighan and M. D. McIlroy (eds), UNIX Programmer’s Manual, 7th Edition, Bell Telephone Laboratories, Murray Hill, NJ (1979). Republished by Holt, Rinehart and Winston, 1983.

4. J. L. Bentley, ‘Software exploratorium: the trouble with qsort’, UNIX Review, 10, (2), 85-93 (1992).

5. J. L. Bentley, ‘Software exploratorium: history of a heapsort’, UNIX Review, 10, (8), 71-77 (1992).

6. American National Standards Institute, American National Standard for Information Systems — Programming Language — C, ANSI X3.159-1989, New York (1979).

7. R. Sedgewick, ‘Quicksort’, PhD Thesis, Stanford University (1975).

8. R. Sedgewick, ‘Implementing quicksort programs’, Communications of the ACM, 21, 847-857 (1978).

9. R. Sedgewick, ‘Quicksort with equal keys’, SIAM J. Comp, 6, 240-267 (1977).

10. R. Sedgewick, ‘The analysis of quicksort programs’, Acta Informatica, 7, 327-355 (1977).

11. R. Sedgewick, Algorithms in C, Addison-Wesley, Reading, MA (1990).

12. D. E. Knuth, The Art of Computer Programming, volume 3: Sorting and Searching, Addison-Wesley,

Reading, MA (1975).

13. R. L. Rivest and D. E. Knuth, ‘Bibliography 26: computer sorting’, Computing Reviews, 13, 283-289

(1972).

14. J. L. Bentley, Programming Pearls, Addison-Wesley, Reading, MA (1986).

15. D. E. Knuth, ‘Structured programming with goto statements’, Computing Surveys, 6, 261-301 (1974).

16. J. L. Bentley, B. W. Kernighan, and C. J. Van Wyk, ‘An elementary C cost model’, UNIX Review, 9, (2),

38-48 (1991).

17. C. W. Fraser and D. R. Hanson, ‘A retargetable compiler for ANSI C’, ACM SIGPLAN Notices, 26, (10),

29-43 (1991).

18. J. P. Linderman, ‘Theory and practice in the construction of a working sort routine’, Bell System Technical

Journal, 63, 1827-1843 (1984).

19. R. C. Singleton, ‘Algorithm 347: an efficient algorithm for sorting with minimal storage’, Communications

of the ACM, 12, 185-187 (1969).

20. B. W. Weide, ‘Space-efficient on-line selection algorithms’, Computer Science and Statistics: Eleventh

Annual Symposium on the Interface, (1978), pp. 308-312.

21. P. McIlroy, ‘Optimistic sorting and information theoretic complexity’, Proceedings of the Fourth Annual

ACM-SIAM Symposium on Discrete Algorithms, Austin, (1993), pp. 467-474.

22. O. Petersson and A. Moffat, ‘A framework for adaptive sorting’, Proc. Third Scandinavian Workshop on

Algorithms and Theory, O. Nurmi and E. Ukkonen (eds), Springer-Verlag Lecture Notes in Comp. Sci.

#621, (1992), pp. 422-433.

23. E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, Englewood Cliffs, NJ (1976).

24. L. M. Wegner, ‘Quicksort for equal keys’, IEEE Transactions on Computers, C-34, 362-367 (1985).

25. N. Wirth, Algorithms + Data Structures = Programs, Prentice-Hall, Englewood Cliffs, NJ (1976).

26. D. E. Knuth, ‘The errors of Tex’, Software—Practice and Experience, 19, 607-685 (1989).

27. J. N. Lyness and J. J. Kaganove, ‘Comments on the nature of automatic quadrature routines’, ACM Transactions on Mathematical Software, 2, 65-81 (1976).