那年初识快速排序

快速排序Quicksort又称划分交换排序partition-exchange sort，简称快排，一种排序算法。最早由东尼·霍尔(C. A. R. Hoare)教授在1960年左右提出，在平均状况下，排序n个项目要O(nlogn)次比较。
在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。

快速排序的核心思想

在计算机科学中，分治法(Divide&Conquer)是建基于多项分支递归的一种很重要的算法范式，快速排序是分治思想在排序问题上的典型应用。

所谓分治思想D&C就是把一个较大规模的问题拆分为若干小规模且相似的问题。再对小规模问题进行求解，最终合并所有小问题的解，从而形成原来大规模问题的解。

字面上的解释是"分而治之"，这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序）、傅立叶变换（快速傅立叶变换）。

分治法中最重要的部分是循环递归的过程，每一层递归有三个具体步骤：

• 分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
• 解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
• 合并：将各子问题的解合并为原问题的解。

快速排序的发明者

查尔斯·安东尼·理查德·霍尔爵士(Sir Charles Antony Richard Hoare缩写为C. A. R. Hoare，1934年1月11日－），昵称为东尼·霍尔(Tony Hoare)，生于大英帝国锡兰可伦坡（今斯里兰卡），英国计算机科学家，图灵奖得主。

他设计了快速排序算法、霍尔逻辑、交谈循序程式。在操作系统中，他提出哲学家就餐问题，并发明用来作为同步程序的监视器（Monitors）以解决这个问题。他同时证明了监视器与信号标（Semaphore）在逻辑上是等价的。

1980年获颁图灵奖、1982年成为英国皇家学会院士、2000年因为他在计算机科学与教育方面的杰出贡献，获得英国王室颁赠爵士头衔、2011年获颁约翰·冯诺依曼奖，现为牛津大学荣誉教授，并在剑桥微软研究院担任研究员。

快速排序的基本过程

快速排序使用分治法来把一个序列分为小于基准值和大于基准值的两个子序列。

递归地排序两个子序列，直至最小的子序列长度为0或者1，整个递归过程结束，详细步骤为：

• 挑选基准值: 从数列中挑出一个元素称为基准pivot，选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。
• 基准值分割: 重新排序数列，所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面，与基准值相等的数可以到任何一边,在这个分割结束之后，对基准值的排序就已经完成。
• 递归子序列: 递归地将小于基准值元素的子序列和大于基准值元素的子序列排序，步骤同上两步骤,递归终止条件是序列大小是0或1，因为此时该数列显然已经有序。

快速排序的递归实现

• 版本一 C实现