快速排序的杀手级对手

Q  你有经过原作者同意么？

A  没有……这不是翻译。只是将原作者的思想以汉语表现。本文中的思想是原作者的。

Q  原论文是什么？

A  《A Killer Adversary for Quicksort》，可以Google（虽然Google是什么我也不知道）

Q  动机？

A  心血来潮。

Q  原文好好的gas solid，你就给改成什么既定未定鬼了？

A  所以不是翻译。窃认为原文的英语和我熟知的英语不同，最开始敝人花了很久脑洞gas solid是什么。请忍耐我的自作主张。

胡诌一句，随机化快排是可以被卡掉的——如果出数据的人是知道你的程序将生成的随机数的未来人的话。

快速排序的杀手级对手

原著M.D.Mcilroy(Dartmouth College)

Hoblovski

众所周知，快速排序的最坏时间复杂度是O(n²)。人们采用随机化，中位数等方法避免快速排序退化。但Mcllory所写的论文《A Killer Adversary for Quicksort》介绍了一种方法，其使得快速排序的几乎所有实现都退化。本文以整数升序排序为例，对该方法进行简述。

本文并非原论文的纯翻译。想了想，这么小一篇文章没必要用LaTeX玩。

一般的快速排序分为三个部分，简单地叙述如下：

一、选择比较基准（下称主元），假设这个过程使用O(1)次比较操作；

二、划分过程：将数组中元素划分为小于、等于、大于基准的三部分；

三、对于小于和大于基准的部分，递归进行上述过程。

显然，如果要让快速排序达到平方级的时间复杂度，必须使得它的划分不平衡。这是该方法的核心思想。该方法观察主元的选择，与此同时对应地安排元素值，使得划分不平衡。其实现是通过一个特殊的比较函数cmp实现的。

注意该方法开始时，元素值是不确定的，排序过程中元素间的大小关系是由cmp函数给出的。算法结束后，元素值才会确定。所以对于每次更新随机种子的随机化快排，该方法无法给出一个hack的数据。然而，若快排选择主元的方法是确定的，譬如未更新随机种子的随机化快排，亦或三者中位数，亦或直接取中间元素，该方法在一次运行后能给出一个hack数据。

我们约定下文使用的专有名词：

未定项：至当前阶段，值还未确定的元素。原文称gas item，即“像气体一样漂浮而不定的元素”；

既定项：至当前阶段，值已确定的元素。原文称solid item，即“如固体一样固定的元素”。

同时我们规定比较大小的时候：

如果两者都是既定项，直接返回其已确定的值的比较结果；

如果一个是既定项另一个是未定项，则既定项小；

如果两个都是未定项，则比较时，一个会变成既定项，另一个保持未定项。变成既定项的那个元素小于保持未定项的元素。

方法如下：

最初所有元素都是未定项。

每次划分过程中，若主元已为既定项，显然不会有新的既定项产生；否则，我们采用如下策略，使得经过最多两次未定项与未定项的比较（下称未-未比较），主元就会变成既定项，从而该次划分中不再有新的既定项产生。第一次未-未比较中，我们随便选择一个未定项变成既定项，另一个变成“主元候补”（pivot candidate）。以后的一次未-未比较，让主元候补变成既定项。

采用该种策略，我们可以保证主元在至多2次未-未比较中就能变成既定项。所以我们可以保证有每次划分都会有n - O(1)个元素大于主元，从而使划分不平衡造成快排退化。

为了防止排序算法运行在数据副本上而无法观察到新既定项的产生，我们要排序的不是元素，而是指针（当然，实现中我们用的是下标）。

原论文对于快速排序的实现给出了几个如下的限制条件：

一、快速排序是单线程的

二、选择主元使用O(1)次比较，其他所有比较都用于划分

三、划分过程中比较是相邻的（原文contiguous）且总有主元参与的

四、数据操作仅包含比较和复制

五、比较仅涉及输入数据以及其副本

最重要的结论：OI中不会出现卡随机化快排的情况（除非出题人SXBK到出一道专卡快排的交互题）

C代码由原论文给出，下给出一个Pascal代码（惭愧，吾不怎么会C/C++）。

(********************************
    val:    原数组, 在排序完成后才会构造完成
    ptr:    指向原数组元素下标的指针, 排序的对象
    csol:   既定项(solid item)的个数
    cand:   主元候补的下标. 堆栈中至多有一个qsort过程在使用它, 故其为全局变量
    ccmp:   快速排序中比较次数
    cmp:    比较函数, 返回负数表示val[i] < val[j], 零与正数类似
    aqsort: 快速排序, 同时构造使快排退化的数据
    qsort： 普通的快排, 一种好用且优美的, (Pascal)最主流的实现
********************************)
{$INLINE ON}
program Quicksort_Adversary;

const maxn = 1000017;	

var val,ptr:array[0..maxn] of longint;
    n,csol,cand:longint;
    ccmp:int64;

function cmp(i,j:longint):longint; inline;
begin
    inc(ccmp);
    if (val[i]=n) and (val[j]=n) then
        if i=cand then begin
            inc(csol); val[i]:=csol;
        end else begin
            inc(csol); val[j]:=csol; 
        end;
    if val[i]=n then cand:=i
    else if val[j]=n then cand:=j;
    exit(val[i]-val[j]);
end;

procedure aqsort(l,r:longint);
var i,j,k,o:longint;
begin
    i:=l; j:=r; k:=ptr[l + random(r-l+1)];
    repeat
        while cmp(ptr[i],k) < 0 do inc(i);
        while cmp(ptr[j],k) > 0 do dec(j);
        if i <= j then begin
            o:=ptr[i]; ptr[i]:=ptr[j]; ptr[j]:=o;
            inc(i); dec(j);
        end;
    until i > j;
    if i < r then aqsort(i,r);
    if j > l then aqsort(l,j);
end;

procedure qsort(l,r:longint);
var i,j,k,o:longint;
begin
    i:=l; j:=r; k:=ptr[l + random(r-l+1)];
    repeat
        while val[ptr[i]] < val[k] do inc(i);
        while val[ptr[j]] > val[k] do dec(j);
        if i <= j then begin
            o:=ptr[i]; ptr[i]:=ptr[j]; ptr[j]:=o;
            inc(i); dec(j);
        end;
    until i > j;
    if i < r then qsort(i,r);
    if j > l then qsort(l,j);
end;

procedure ainit;
var i:longint;
begin
    readln(n);
    for i:=1 to n do begin
        val[i]:=n; ptr[i]:=i;
    end; readln;
    ccmp:=0; csol:=0; cand:=0;
end;

procedure init;
var i:longint;
begin
    readln(n);
    for i:=1 to n do begin
        read(val[i]); ptr[i]:=i;
    end; readln;
end;

procedure answer;
var i:longint;
begin
    for i:=1 to n-1 do write(val[i],' '); writeln(val[n]);
    for i:=1 to n-1 do write(val[ptr[i]],' '); writeln(val[ptr[n]]);
    writeln(ccmp);
end;

begin
    assign(input,'sort.in'); reset(input);
    ainit;
    close(input);
    aqsort(1,n);
    assign(output,'sort.out'); rewrite(output);
    answer;
    close(output);
end.