快速排序思路

1、选取基准值，并标明首、尾的标识low、high；

2、先从后往前判断，当high的值大于基准值时，high--，否则将low的值替换为high的值；

3、然后从前往后判断，当low的值小于基准值时，low++，否则将high的值替换为low的值；

4、将基准值赋值给low的值；

5、当low<high的时候，递归调用2~4步；

快速排序理解

每个人理解不同，有人说快排属于交换排序方式，有人说是归并排序方式，都有道理。我理解快排就是一边分堆，一边交换。以基准值为标届，大于基准值的放在右边，小于基准值的放在左边。每分一次堆就是一次排序，直到每个堆左右只剩下0个或1个值则排序结束。

快速排序的复杂度

快排的时间复杂度和基准值的选取有绝对的关系，当基准值正好是所有元素中间大小的那个值，他的排序就是很平均的，一分为二，然后两边再平均分，最终分的深度都一样，时间复杂度也就是O(nlogn)，不然的话会导致基准值两边深度及其不平衡，极端情况下就是一颗斜数，这种情况下时间复杂度就是O(n^2)。

快速排序的优化

既然上面说到，快速排序的效率和基准值的选取有绝对的关系，那么优化点自然要从如何选好基准值入手。

方法一：以首（或尾）部的值作为基准值。这种弊端显而易见，谁也不能说清选取的基准值到底是什么。

方法二：随机值选取。就是在所有元素中随便选取一个值作为基准值。这种方法比起第一种稍微保险一些，稍稍降低了取到醉倒或者最小值的概率，但是还是一种“瞎蒙”的存在。

方法三：三数取中值，即选取所有元素中的三个值，在这三个值中进行排序，选择中间的值作为基准值。这样做的好处就是能保证选取的基准值不会是最大或者最小的值。

方法四：多（大于三）数取中。同上。

快速排序的实际应用

很多人在实际的工作中应该都会用到Arrays.sort()方法进行排序，这里面其实就有实际用到快速排序。

排序.png

如上图，当需要排序的元素个数大于QUICKSORT_THRESHOLD（286）的值时，便会使用优化后的双轴快速排序方法。感兴趣的同学可以自行研究jdk源码。

至于小于QUICKSORT_THRESHOLD（286）值的时候用什么排序方式呢？答案是直接插入排序。

这其中当然包含各种排序方法适合场景的考虑，而为神马这个边界值时286呢？参考Stack Overflow的回答，那就是前任进行了多次试验，发现这个值就是算法性能的分界点。

快速排序JAVA实现代码

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 432, 2, 31, 5, 234, 12};
        quickSort(arr, 0, arr.length - 1);
        for (int a : arr) {
            System.out.println(a);
        }
    }

    /**
     * 快速排序思路：
     * 在一组元素中，选取一个基准值，把大于基准值的元素放到右侧，小于基准值的元素放到左侧，重复操作直到完成排序。
     * <p>
     * 使用方法：
     * 1、找基准值，并设置首、尾标识（low、high）
     * 2、从后半部分开始，当扫描值大于基准值时就让high-1，如果比基准值小，则把high位置的值赋值给low
     * 3、然后从前向后臊面，如果扫描至小于low则low+1，如果大于基准值则将low位置的值付给high位置
     * 4、递归操作
     *
     * @param arr
     * @param low
     * @param high
     */
    private static void quickSort(int[] arr, int low, int high) {
        // 指定递归退出条件
        if (low < high) {
            // 获取排序后基准值的位置
            int pivot = partition(arr, low, high);
            // 对小于基准值的元素再次进行排序
            quickSort(arr, low, pivot - 1);
            // 对大于基准值的元素再次进行排序
            quickSort(arr, pivot + 1, high);
        }
    }

    /**
     * 返回排序后基准值的位置
     *
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static int partition(int[] arr, int low, int high) {
        int pivotKey = arr[low];
        while (low < high) {
            // 当尾部元素大于基准值时high-1
            while (low < high & arr[high] >= pivotKey) {
                high--;
            }
            // 否则将尾部元素赋值给首部位置
            arr[low] = arr[high];
            // 当首部元素小于基准值时low+1
            while (low < high && arr[low] <= pivotKey) {
                low++;
            }
            // 否则将首部元素赋值给尾部位置
            arr[high] = arr[low];
        }
        // 将基准值插入到首部和尾部中间位置
        arr[low] = pivotKey;
        // 返回基准值的位置
        return low;
    }
}