Sort
堆排序
快速排序
算法性质
快速排序是一种基于比较的、不稳定的原地排序算法。其最坏时间复杂度为$\Theta (n^2)$，最好时间复杂度为$O(nlogn)$，平均时间复杂度(指均匀随机分布情况下)为$\Theta (n^2)$
伪代码
本部分的PARTITION代码较为高效，其核心思想是用两个变量分别记录当前小于等于划分元的边界以及当前扫描过的元素的边界，从而避免了边界条件的重复检查(只需要一遍扫描)。其他的实现方法还有指针从两端向中间移动并交换元素等做法，但都需要边界检查。
时间复杂度分析
结论:快速排序算法的最坏时间复杂度为$\Theta(n^2)$(也即$O(n^2)$)；最好划分对应时间复杂度$\Theta (nlgn)$，并且系数较小；平均时间复杂度$\Theta (nlgn)$
最坏时间复杂度
快排的最坏时间复杂度为$\Theta (n^2)$，即PARTITION划分”不均匀”时，会造成快速排序算法和插入排序(平均或最坏)渐近一样慢。
实例：例如数组已经有序，那么快排的时间复杂度为$\Theta (n^2)$，而插入排序此时时间复杂度为$O(n)$
注意：“划分不均匀”指的是划分为长度为0和n-1的两部分，如果划分按照一定比例，即使不是对半划分，仍然认为是均衡划分（因为和对半划分同量级）
证明
PARTITION算法的时间复杂度为$\Theta (n)$
首先，可以找到一种情况，使得时间复杂度为$n^2$量级，即每一次划分均为0和n-1长度时，此时$T(n)$满足：$T(n) = T(0)+T(n-1)+\Theta (n)$
解得$T(n) =\Theta (n^2)$，即至少存在一种情况，使得最坏情况时间复杂度为$T(n) = \Omega (n^2)$（下界确定）
然后，假设在q划分导致运行时间最长，即$T(n) = \underset {0\leq q \leq n-1}{max}(T(q)+T(n-q-1))+C_1n$
猜测$T(n) \leq Cn^2$，利用代入法验证，上式变为:
$T(n) \leq \underset {0\leq q \leq n-1}{max}(Cq^2+C(n-q-1)^2)+C_1n \leq C(n-1)^2+C_1n$
当$C\ge C_1$时，$T(n)\leq Cn^2$对$n\geq 1$成立
综合上述分析，快排的最差时间复杂度为$\Theta (n^2)$
最好时间复杂度
如果每次划分都将数组对半划分，即子数组的长度分别为$\lfloor \frac{n}{2} \rfloor$和$\lceil \frac{n}{2} \rceil-1$，那么忽略取上下界和加减1的细节，递归方程为：
$T(n) = 2T(\frac{n}{2})+\Theta (n)$，解为$\Theta (nlgn)$
固定比例划分
对于快速排序“均衡”划分的理解实际上并不是直观感受上两子数组长度相近，实际上只要按照一定比例为界进行划分即可。
通过递归树即可很容易的证明：行和为$O(n)$(因为最后若干行并没有达到$Cn$)，总行数为$\Theta (lgn)$，因此固定比例划分情况下的时间复杂度仍为$O(nlgn)$
平均时间复杂度
平均时间复杂度的平均指的是划分位置在各位置的概率相等，实际上也是在说输入序列所有排列是等概率的
分析方法1
设$T_k(n)$为在数组下标k位置进行划分的运行时间，那么满足:
$T_k(n) = T(k)+T(n-1-k)+cn$
而对于$T(n)$，在每个位置划分的概率是相等的，因此$T(n)$满足：
$T(n) = \frac{1}{n}\sum_{k=0}^{n-1}T_k(n) = \frac{2}{n}\sum_{k=0}^{n-1}T(k)+cn$，可得
$2T(n) = 2\sum_{k=0}^{n-1}T(k)+cn^2$
$2T(n-1) = 2\sum_{k=0}^{n-2}T(k)+c(n-1)^2$
上面两式错位相减得到$\frac{T(n)}{n+1} = \frac{T(n-1)}{n}+\frac{c(2n-1)}{n(n+1)} = \frac{T(n-1)}{n}+\frac{2c}{n+1}-c(\frac{1}{n}-\frac{1}{n+1})$
设$G(n) = \frac{T(n)}{n+1}$，展开上式得到:
因此$T(n) = (n+1)G(n) = \Theta (nlgn)$
分析方法2
对于快排算法(或随机快排算法)，其运行时间必然为$O(n+X)$，其中$X$指的是总比较的次数。这一事实实际上是在说：算法调用n次$PARTITION$，每次调用必然会先进行$O(1)$的操作然后进入循环，用pivot对当前数组内所有元素进行比较，因此需要得到$X$的量级。
设$x_{ij}$为事件{$z[i]$和$z[j]$发生比较}的指示变量(其中z是排序后的A)，那么$X = \sum_{i=1}^n \sum_{j=i+1}^n x_{ij}$。
对于$z[i]$和$z[j]$，如果他们发生比较，那么必然其中一个元素被选为主元，并且必然是$z[i…j]$中第一个被选为主元的，否则接下来$z[i]$和$z[j]$必然会被分开，分开后他们不可能发生比较。由于两元素发生比较意味着某元素被选为主元，因此两元素发生比较最多发生一次。
由上述事实可以知道，$z[i]$和$z[j]$在$z[i…j]$中第一个被选为主元的概率是$z[i]$在$z[i…j]$中第一个被选为主元的概率的两倍，即$\frac{2}{j-i+1}$，因此可知$X$的期望为：
证明$E(X) = O(nlgn)$:
\[\begin{aligned} E(X)&= \sum_{i=1}^n \sum_{k=1}^{n-i} \frac{2}{k+1} \\ & \leq \sum_{i=1}^n \sum_{k=1}^{n} \frac{2}{k+1} \\ & \leq \sum_{i=1}^n O(lgn) \\ = O(nlgn) \end{aligned}\]证明$E(X) = \Theta (nlgn)$(注意这里用到的$\frac{1}{n+1} \geq \frac{1}{n+n}$)):
\[\begin{aligned} E(X)&= \sum_{i=1}^n \sum_{k=1}^{n-i} \frac{1}{k+1} \\ & \geq \sum_{i=1}^n \sum_{k=1}^{n-i} \frac{2}{k+k} \\ & \geq \sum_{i=1}^n ln(n-i+1)\\ & = ln(n!) \\ & = \Theta (nlgn) \end{aligned}\]综上，可以知道快排以及随机快排的平均性能为$\Theta (nlgn)$
随机化快速排序
随机化快速排序的思想和快速排序类似，其不同之处在于使用随机采样(random sampling)获得每一轮的划分元
算法实现
$RANDOMIZED-PARTITION$算法将$A[r]$和随机选取的元素交换，然后调用$PARTITION$作为子过程即可。排序算法调用划分。
算法分析
结论:随机快排的平均性能为$\Theta (nlgn)$
证明已在快速排序的平均时间复杂度部分给出。要注意的是快速排序平均性能的假设是：假设输入数据所有排列的可能性是相同的，但是实际情况并不一定是这样的，比如输入数据本身基本有序等（基本有序情况下划分会变得不均衡）；随机化快排的意义就在于人为地引入随机性，让算法对于所有输入的排列情况都能有较好的期望性能。
基于比较排序的时间界
基于比较排序的算法最坏时间复杂度满足：$T(n) = \Omega (nlgn)$，即最坏情况的下界不会渐近小于$cnlgn$
决策树
决策树是严格二叉树，其节点为当前正在进行的比较，不同的孩子表示两种比较结果对应的下一步。
无论一个算法对其输入按照什么样的决策树进行比较，最终得到的叶节点对应给定的一个输入；规模为$n$的输入总共有$n!$种，因此决策树的叶节点数量满足$l\geq n!$
假设决策树高度为$h$，那么其叶节点最多为$2^h$个，因此有如下不等式:
$n! \leq l \leq 2^h$，解得$h \geq lg(n!)$，即$h = \Omega (nlgn)$，对应算法的最坏时间复杂度
堆排序和归并排序运行时间上界是$O(nlgn)$，因此它们是渐近最优的比较排序算法；而快速排序运行时间上界为$O(n^2)$，因此不是渐近最优的。