「算法」快速排序 Java 实现

1 前言

吴军《Google 方法论》专栏「计算机算法，谈谈提高效率的本质」文章中提及算法的重要性，未来是人工智能，大数据时代。在计算机使用不同算法运行程序会出现成千上万倍的效率差。

文中提及常用算法 “归并排序” 与 “快速排序”，业余时间一直有翻阅相关文章，但没有自己总结深入了解。

2 快速排序原理与Java代码实现

快速排序 是图灵奖得主 C. R. A. Hoare 于 1960 年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)

分治法基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序，利用分治法可以分为三步： 1. 数据集中选择 一个元素作为 “基准”「pivot」 2. 所有小于 “基准” 的元素，都移到基准左边；所有大于 “基准” 的元素，都移到基准的右边，这个操作称为分区操作，分区操作结束后，基准元素所处位置就是最终排序的位置。 3. 对于 “基准” 左边与右边的两个子集，不断重复第一步与第二步，直到所有子集只剩下一个元素为止。

2.1 快速排序动态原理图

2.2 快速排序静态原理图

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; } }

参考文章

---

快速排序思想及Java实现算法 3：最常用的排序——快速排序快速排序（Quicksort）的Javascript实现