「算法」快速排序 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实现