Quick Sort 思想以及 Java 代码实现

封面是发明快速算法的大佬 —— C. A. R. Hoare

对于算法仅限于 Baidu+Google+CSDN 的我来说，记忆里最深刻还是大一的水仙花数。
但其实先理解并牢记思想，代码就不难写出来。并且代码写错也没关系，实在写不出还能解释一下快排原理。

快速排序概要

快排的三个步骤：

• 选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）。
• 分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大。
• 递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

其实快排实现的核心思想就是分治和递归，接下来用大白话解释下快排的原理，用词和说明可能不是那么正确，但是能够先听懂它的实现，我觉得这更重要。

我们假设这样杂乱无序不重复的数组 [21, 5, 44, 63, 3]，设定他的 基准pivot 为第一位 Array[0]，则 pivot 就是 21，当然不一定都是第一位，并且 low 指针指向最左边，high 指针指向最后边。

当 low 指针指向的值大于 pivot 就赋值给 high 指针，若当前指向的值不大于 pivot，则一直向右移动，直到两个指针重合或者找到比 pivot 大的值。

high 指针则反之，一直找寻比 pivot 小的值，找到则赋值给 low 指针，否则一直向左移动，直到两个指针重合或者找到比 pivot 小的值。

快排原理解释

high 指针先于 low 指针比较和移动，high 指针所指向的 value 是 3，比 pivot 小，则赋值给 low 指针所指向的 21，并且 high 指针不动。

这时，轮到 low 指针向右移动了。

此时 low 指针向右移动发现比 pivot 小，则继续向右移动。

这时候 lei 了，low 指针指向的 44 比 pivot 大，辣么就赋值给 high 指针指向的 3，并且 low 指针保持不动。

high 指针向左移动。

发现比 pivot 大，这继续向左移动。

传说当两指针重合的时候，夜晚将是血红之月 🌛，野性驱使的人类将会幻化成狼人嗥叫，暗黑之礁的邪恶鱼人也会登上瓜哇岛，残忍猎杀大量秃头程序猿。当然更重要的是当两指针重合的时候，此时指向的 44 将会被 基准 值改写。

这时候一轮分治就 OJBK 了。可以清楚地看到（好像这个例子不是很清楚的看到，果然是 size 太短了吗），在 基准 值的左边数组大小都是小于 基准 值的，而右边数组都是大于 基准 值。这个时候就体现了快排的分治思想，相当于从 基准 中切一刀，左边的数组单独去排序，右边的数组单独去排序。这时候就变成了 [3, 5] 和 [63, 44] 继续递归快速排序，所以说快排实现的核心思想就是分治和递归。

Java 代码实现

/**
 * @ClassName Qs
 * @Description TODO
 * @Author MatthewHan
 * @Date 2019/7/23 10:48
 * @Version 1.0
 **/
public class Qs {

    
    private static int[] arr = {21,5,44,63,3,63,23,456,6764,8,22,15,67,33,202,23333,234,565656565,22,7,22,4,3,43,3,566,34,345,2};
    private static int n = 0;

    public static void main(String[] args){
        
        Qs qs = new Qs();
        qs.func(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        System.out.println(n);
    }

    private void func(int[] arr,int i, int k){

        if(i>k){
            return;
        }
        int low = i;
        int high = k;
        // 每次选取基准都是和low指针一致
        int pivot = arr[i];
    
        while (i<k){
    
            while(arr[k]>pivot && i<k){
                k--;
            }
            if (arr[k]<=pivot && i<k){
                arr[i] = arr[k];
                i++;
            }
            while(arr[i]<pivot && i<k){
                i++;
            }
            if (arr[i]>=pivot && i<k){
                arr[k] = arr[i];
                k--;
            }
        }
        if(i==k){
            arr[i] = pivot;
            arr[k] = pivot;
        }
        n++;
        // 递归调用
        func(arr,low,k-1);
        func(arr,k+1,high);

    }
}

要注意每次要判断 i 和 k 的大小，因为数组 size 是多少就会有多少次基准数归位，会不断地拆分成两对数组，最后变成 2 位，1 位。

快排的一些知识点和算法复杂度

• 选取基准最怕的就是选到了最大值或者最小值，这样一轮就是只是把基准数移到了最边上。
• 从概率学上来说，基准数选不选择第一个，还是中间随机抽取一个对是否会选取到最大值或最小值都是没有任何影响的。但是存在数列完全逆序的情况，从中间选取基准数可以有效避免这种情况发生，若还是选择数列最左位当做基准数的话，就会变成最糟糕的情况，时间复杂度就会变成 O（n^2）。
• 所以快速排序的平均时间复杂度是 O（nlogn），最坏情况下的时间复杂度是 O（n^2）。