点击(此处)折叠或打开

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

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就比较过呢，这个可以用反证法推翻，具体就不详解了

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

    中文意思是：我们只需要记住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就是我们要找的的时间复杂度，由期望值的线性性质--和的期望等于期望的和

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

定理1.1：如果递增集合Zij 中第一个成为partition函数主元的元素不在两端（设为Zk,i<k<j)，则元素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）

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

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