1 前言
吴军《Google 方法论》专栏「计算机算法，谈谈提高效率的本质」文章中提及算法的重要性，未来是人工智能，大数据时代。在计算机使用不同算法运行程序会出现成千上万倍的效率差。
文中提及常用算法 “归并排序” 与 “快速排序”，业余时间一直有翻阅相关文章，但没有自己总结深入了解。
快速排序核心思想：选取一个基准数字，比基准数字小的数字全部放在基准左边，比基准数字大的数字全部放在基准右边，基准依次递归。
2 快速排序原理与Java代码实现
快速排序 是图灵奖得主 C. R. A. Hoare 于 1960 年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)
分治法基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快速排序，利用分治法可以分为三步：
- 数据集中选择 一个元素作为 “基准”「pivot」
- 所有小于 “基准” 的元素，都移到基准左边；所有大于 “基准” 的元素，都移到基准的右边，这个操作称为分区操作，分区操作结束后，基准元素所处位置就是最终排序的位置。
- 对于 “基准” 左边与右边的两个子集，不断重复第一步与第二步，直到所有子集只剩下一个元素为止。
2.1 快速排序动态原理图
快速排序原理图
2.2 快速排序静态原理图
举例来说，现在有一个数据集{85, 24, 63, 45, 17, 31, 96, 50}，怎么对其排序呢？
第一步，选择中间的元素45作为"基准"。（基准值可以任意选择，但是选择中间的值比较容易理解。）
第二步，按照顺序，将每个元素与"基准"进行比较，形成两个子集，一个"小于45"，另一个"大于等于45"。
第三步，对两个子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
2.3 Java 伪代码实现
public class Quicksort {
private static final String TAG = "Quicksort";
private int[] numbers;
private int number;
public void sort(int[] values) {
// 检查数组是否为空
if (values == null || values.length == 0) {
return;
}
this.numbers = values;
number = values.length;
quicksort(0, number - 1);
}
private void quicksort(int low, int high) {
int i = low, j = high;
// 把数组中间的元素设置为基准数
int pivot = numbers[low + (high - low) / 2];
// 分开成两个数组
while (i <= j) {
//从左向右“探测”，如果左边的元素小于基准数，则去“探测”下一个元素
while (numbers[i] < pivot) {
i++;
}
//从右向左“探测”，如果左边的元素大于基准数，则去“探测”下一个元素
while (numbers[j] > pivot) {
j--;
}
// 如果左边探测结果大于基准数，右边探测结果小于基准数，那么交换这两个元素
// 然后继续探测
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
// 递归
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}
private void exchange(int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
