概要

        快速排序由C. A. R. Hoare在1960年提出，是八大排序算法中最常用的经典排序算法之一。其广泛应用的主要原因是高效，核心算法思想是分而治之。

        快速排序经常会被作为面试题进行考察，通常的考察思路是快排思想、编码实践之手写快排以及进一步对快排的优化。

相关文章：
常见十大排序算法，动图演示（Python3实现）_Java Punk的博客-CSDN博客回顾所学发现见到最多的还是各种排序算法https://blog.csdn.net/weixin_44259720/article/details/103385439更多相关文章，请登录我的博客主页进行查看。

正文

        事实上，Java 标准库中 Arrays. sort() 方法的源码也正是使用了优化后的快速排序，这也是面试的一个考点，下面会带大家分析源码。可见，掌握快排算法对于数据结构与算法入门极为重要。

一、原理

        快速排序（Quick Sort）是从冒泡排序算法演变而来的，实际上是在冒泡排序基础上的递归和分治法，核心思想是分治，即：每一轮选择数组中某个数作为基数，通过一趟排序将要排序的数据分割成独立的两部分，其中比基数小的放一边，比基数大的放在另一边，循环递归，最终使整个数组变成有序。

        快速排序核心是选定一个基数进行划分排序，关于基数选择有很多方式，而基数选择直接关系到快排的效率。事实上，选取基准元素应该遵循平衡子问题的原则，即：使得划分后的两个子序列的长度尽量相同。

        本篇以最常见的使用数组首元素（P）作为基数进行快速排序原理说明。

二、方法描述

        先安排一个测试类，然后再展开来讲解排序方法：

    @Test
    void all_process_T(){
        int[] arr1 = {1,2,3,5,8,11,10,6,9,7,54,23,27,17,22,13};
        int[] arr2 = {1,2,3,5,8,11,10,6,9,7,54,23,27,17,22,13};

        this.quickSort_1(arr1, 0, arr1.length - 1);
        System.out.println("arr1 = " + JSON.toJSONString(arr1));
        this.quicksort_2(arr2, 0, arr2.length - 1);
        System.out.println("arr2 = " + JSON.toJSONString(arr2));
    }

• 写法一：分开的写法，原理更好理解；

    public void quickSort_1(int[] arr,int left,int right){
        if (left >= right)
            return;
        int mid = this.partition(arr, left, right);
        this.quickSort_1(arr, left, mid-1);
        this.quickSort_1(arr, mid+1, right);
    }

    private int partition(int[] arr, int left, int right) {
        // 划分参考数索引，默认为第一个数，可优化
        int base = arr[left];
        // 以左边为key，所以从右边开始找
        while (left < right) {
            // 右边找
            while (left < right && arr[right] >= base ) {
                right--;
            }
            // 找到以后，与左边元素交换
            if (left < right) {
                arr[left++] = arr[right];
            }
            // 左边找
            while (left < right && arr[left] <= base ) {
                left++;
            }
            // 找到以后，与右边元素交换
            if (left < right) {
                arr[right--] = arr[left];
            }
        }
        // 最后，将参考数字赋值给left，完成最终交换
        arr[left] = base;
        return left;
    }

• 写法二：合并在一起的写法；

    public static void quicksort_2(int[] arr, int left, int right) {
        //数组最左边小于最右边不合法,直接退出
        if (left > right) {
            return;
        }
        //定义变量i指向最左边
        int i = left;
        //定义变量j指向最右边
        int j = right;
        //定义左边为基准元素base
        int base = arr[left];
        //只要i和j没有指向同一个元素,就继续交换
        while (i != j) {
            //从右向左寻找第一个小于基准元素的数
            while (arr[j] >= base && i < j) {
                j--;
            }
            //从左向右寻找第一个大于基准元素的数
            while (arr[i] <= base && i < j) {
                i++;
            }
            //执行到这里证明找到了i和j指向的元素
            //交换i和j指向的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //将i和j共同指向的元素与基准元素交换
        arr[left] = arr[i];
        arr[i] = base;
        //对左边进行快速排序
        quicksort_2(arr, left, i - 1);
        //对右边进行快速排序
        quicksort_2(arr, i + 1, right);
    }

三、Arrays.sort源码解析

         Arrays 其实调用了 DualPivotQuicksort. sort() 方法进行排序：

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

        DualPivotQuicksort.sort() 方法在预处理部分，主要做了三件事：

1. 判断数组长度是否超过快排阈值：如果超过286，则进行进一步判断，否则直接调用快速排序的方法。而进入快速排序的方法中也会有长度判断，如果数组长度小于47，会使用插入排序（下面代码展示有说明）；
2. 创建运行记录空间（run）：主要用于记录数组的形状，是否大体呈有序状态。如果峰值过多，说明数组趋于乱序状态，依然使用快速排序方法；
3. 如若最后一轮迭代仅剩一个数自成一个子序列，那么则在 run 中添加一个哨兵，值为 right + 1；如若数组已然有序，则直接返回。

        因为涉及 sort() 排序代码比较多，所以我只节选了一部分进行展示，感兴趣的小伙伴可自行源码。

final class DualPivotQuicksort {

    // 合并排序中的最大运行长度。
    private static final int MAX_RUN_LENGTH = 33;

    // 合并排序中的最大运行次数。
    private static final int MAX_RUN_COUNT = 67;

    // 如果要排序的数组长度小于该常数，则插入排序优先于快速排序。
    private static final int INSERTION_SORT_THRESHOLD = 47;

    // 如果要排序的数组长度小于此常数，则优先使用快速排序合并排序。
    private static final int QUICKSORT_THRESHOLD = 286;

    /**
     * 如果可能合并，使用给定的工作区数组切片对数组的指定范围排序。
     */
    static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) {
        // 在小数组上使用快速排序, 常量 QUICKSORT_THRESHOLD = 286
        if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }

        // run[i] 表示第i轮外循环迭代的起始位置
        int[] run = new int[MAX_RUN_COUNT + 1];
        int count = 0; run[0] = left; // count 表示轮数-1, run[0] 初始值为 left 

        // 检查这个数组是否大体呈有序态
        for (int k = left; k < right; run[count] = k) {
            // 升序
            if (a[k] < a[k + 1]) { 
                while (++k <= right && a[k - 1] <= a[k]);
            } 
            // 降序
            else if (a[k] > a[k + 1]) {
                while (++k <= right && a[k - 1] >= a[k]);
                // 如果是降序，那么对降序序列进行交换，转换为升序序列
                for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                    int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                }
            } 
            // 相等
            else { 
            	// 统计相等元素【a[k]】的频数，如果超过MAX_RUN_LENGTH（默认33）则使用快速排序
                for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                    if (--m == 0) {
                        sort(a, left, right, true);
                        return;
                    }
                }
            }

            // 如果数组的结构化指标（即凹凸点个数）超过了阈值，其实就是乱序，那么还是选择快速排序
            if (++count == MAX_RUN_COUNT) {
                sort(a, left, right, true);
                return;
            }
        }

        // 检查特殊情况
        if (run[count] == right++) {
        	// 数组长度为1时，设置一个哨兵
            run[++count] = right;
        } 
        // 数组已呈有序状态
        else if (count == 1) { 
            return;
        }

        // 太长了，不写了，自己看源码吧 ...
    }

    /**
     * 通过双枢轴快速排序对数组的指定范围排序。
     */
    private static void sort(int[] a, int left, int right, boolean leftmost) {
        int length = right - left + 1;
        // 在微小数组上使用插入排序, 常量 INSERTION_SORT_THRESHOLD = 47
        if (length < INSERTION_SORT_THRESHOLD) {
            // ...
        }
        // 否则，使用快速排序，代码太多不展示了，直接看源码吧 ...
    }

}