快速排序与概率论

看过快排（特指算法导论中的就地分区版快排）多少会有下面几个疑问，本文为你逐一解答

1. 主元为什么要挑最后一个元素（或者可以这么问，partition函数中i的值为什么要从一个不存在的下标开始）
2. 在证明快排期望运行时间时，定义集合Z为原始集合排序后的集合有什么目的（Zi being ths ith smallest element ）
3. 在证明快排期望运行时间时，Xij明显不是独立随机变量（假设Xij=1,即第i个跟第j个发生比较了，那就说明两者有一个是主元，进而以后任何一个数都没法与其发生比较，也就是说Xi*或者Xj*恒为0），为什么还能把他们相加，最后用调和级数公式导出了nlogn的时间复杂度

就地分区版快排

private static int partition(int[] arr, int start, int end){
    int pivot=arr[end];
    int i=start-1;//i不在start..end这个区域内
    int j;
    for(j=start;j<end;j++){//-------------a
      if(arr[j]<pivot){//------------------b
        int tmp=arr[j];
        arr[j]=arr[++i];
        arr[i]=tmp;
      }
    }
    arr[end]=arr[++i];
    arr[i]=pivot;
    return i;
  }

  private static void quicksort(int[] arr, int start, int end){
    int i;
    if(start<end){
      i=partition(arr,start,end);
      quicksort(arr,start,i-1);
      quicksort(arr,i+1,end);
    }
  }

要快速消化上面这段代码只需要明确下面三点即可：

1. [start,i]这个闭区间内的数是下半区（区间内的数都小于主元，如果此区间为空，则说明还没分离出小于主元的元素，比如说初始化状态）
2. 当a行代码的j++执行完后，(i,j)这个开区间是上半区（区间内的数都大于主元，如果此区间为空，则说明还没分离出大于主元的元素，比如说初始化状态）
3. 如果把for循环过程比作经典游戏贪食蛇，则上半区就是那条前进的蛇：b行代码为false代表蛇吞了一个格子，长度加一,为true代表蛇前进一格：通过将蛇的最后一个格子调到前面来，而整体长度未增加

如果你能明白上面三点第一个问题就有解了：i必须从不存在的地址开始（start-1），否则初始化时下半区就有值了，关于为什么挑最后一个元素作为主元，如果你能看懂那个贪食蛇的demo就懂了——谁愿意蛇被截成两段啊-_-,你也可以挑第一个元素作为主元，但算导作者并没有这么做，其中的缘由我还真猜不出来

随机变量指示器求解快排时间复杂度

    求时间复杂度一般都是看for循环会循环多少次，但是快排是个例外，它是看for循环里执行的某行逻辑会发生多少次——j跟主元比较。

    我们可以很明显的看到快排中任何一对元素(假设a,b)最多只能比较一次，因为此轮比较后其中的一元素个会作为主元(假设a)被夹在中间，无缘下一轮partition，进而再也没法与任何元素（当然也包括b），有的人可能会问万一前面的几轮partition过程中a跟b就比较过呢，这个可以用反证法推翻，具体就不详解了

    算法导论中有这么一段原话：

where we are considering whether the comparison takes place at any time during the execution of the algorithm, not just during one iteration or one call of PARTITION

    中文意思是：我们只需要记住a跟b最多只会比较一次即可，至于谁是主元以及a还会不会跟c进行比较不用管，我们考虑的是整个算法的执行过程

    既然a跟b比较这个事件只会有两种结果:不发生or发生且仅有一次，设发生比较为事件X，对其建立随机变量指示器（indicator random variable）：令a是原始集合中第i小的元素（即Zi ），b是Zj，定义Zij 为子集{Zi ,Zi+1....Zj-1,Zj}（即大小介于a，b之间的数集合），那么

Xij =I{i跟j发生比较}=

1:i跟j发生比较

0：i跟j未比较

于是整个算法总的比较次数就是上述指示器的和

X=??Xij.......（第一个西格玛是i=1到n-1,第二个是j=i+1到n）

这个X就是我们要找的的时间复杂度，由期望值的线性性质--和的期望等于期望的和

E(X)=E(??Xij)=??E(Xij)=??(1*Pr(i跟j发生比较)+0*Pr(i跟j未比较))=??Pr(i跟j发生比较).........T1.1

不失一般性，我们已经令i是第i小的元素，j是第j小的元素，

定理1.1：如果递增集合Zij 中第一个成为partition函数主元的元素不在两端（设为Zk,i，则元素Zi跟Zj无法比较,即Xij=0

证明：用反证法即可证明，假设Zi和Zj还能比较，那么两者这这一轮partition过后一定被分到同一个区，假设在上半区，根据快排定义有：Zk<Zi且Zk<Zj，而集合Zij的递增的性质决定了Zk>Zi,与假设矛盾，故定理1.1成立

    由定理1.1我们可以很轻易的计算出事件“i跟j发生比较”的概率是多少，那就是Zi或者Zj必须是在整个算法的过程优先于集合Zij 其他任何一个元素选作主元，这样i跟j才不会被分到两个分区里面进而失去比较的可能，而集合Zij中任何一个元素被优先选为主元都是等可能的，故有

Pr(i跟j发生比较)=2*(1/j-i+1)

同时也回答了文初的问题2,集合Z递增有什么目的，就是为了讨论Zi跟Zj在一次partition过后的情况而特意设的

E(X)=??2*(1/j-i+1)

令k=j-i

E(X)=??2*(1/k+1)......(第一个西格玛是i=1到n-1,第二个是k=1到n-i）

E(X)<??2*(1/k)......(第一个西格玛是i=1到n-1,第二个是k=1到n）

由调和级数的公式可以消掉第二个西格玛

E(X)=?(lnn+O(1))=nlnn=O(nlgn)

对于文初的问题3，不独立的变量为何还能相加，会不会导致计算结果不准确，对此有两点是可以看到的

• a跟b比较了，则a跟c等于0的概率会增加，我们并没有强制将它设为0,导致总期望下降的因素被减去了，最终导致求出的总期望偏高，而我们要求的正好是一个上限
• 期望线性的性质并不要求相加的两个随机变量是独立的，推导T1.1恒成立