分析快速排序
快速排序是基于分治思想(Divide-and-conquer)的一种原地排序(In place)，其效率依赖于输入数据的排序状况。
快速排序中的分治法思想
-
分解问题：原数组基于Pivot X分成两部分，数组在X左侧的数据都小于X，在X右侧的数据都大于X
- 递归的对两部分数组进行处理
最关键的就是第一步：分化（Partition）的步骤，这是该算法处理问题的核心
partition(A, p, q)
x <- A[p]
i <- p
for j = p+1 to q
do if A[j] <= x
then i <- i+1
exch A[i] <-> A[j]
excha A[p] <-> A[i]
return i
quicksort(A, p ,r)
if(p < r)
then q <- partition(A, p ,r)
quicksort(A, p, q-1)
quicksort(A, q+1, r)
最坏情况（完全反序）
T(n) = T(n-1) + Θ(n) = Θ(n2)
最优情况（每次分划的时候正好将数组划分成了两个相等的子数组）
T(n) = 2T(n/2) + Θ(n) = Θ(nlgn)
随机化快排算法
若输入本身已被排序，那么对于快排来说就糟了。
如何避免这样的情况？
一种方法是随机排列序列中的元素
另一种方法时随机地选择pivot，这便是随机化快速排序的思想
这种快排的好处是：其运行时间不依赖于输入序列的顺序。最不幸运的情况有可能会发生，但是也是因为随机数产生器的原因，不是因为输入序列的原因。
随机化快排的算法效率是Θ(nlgn) 【证明需要一些数学期望的知识】
