前言

自学了一年 JAVA 阿巴阿巴终于约到了面试，然而这次面试官让她谈谈对排序算法的了解。

面试官： 你对算法这一块理解吗？排序这一块理解吗？

阿巴阿巴： 理解一点，排序算法这一块次要有冒泡排序、插入排序、希尔排序、抉择排序、疾速排序、归并排序、堆排序、基数排序、桶排序。

面试官： 很不错，那你晓得什么是稳定性吗，这些算法都是 稳固 的吗？他们的复杂度别离是多少呀？

阿巴阿巴： 稳定性就是说，如果有 2 个元素 a 和 b，且 a = b，且 a 排在 b 后面，如果通过排序算进行排序后，b 在 a 后面了，那么咱们就说这个算法是不稳固的，这就是稳定性。不稳固的算法有疾速排序、抉择排序、希尔排序、堆排序。俗称‘快选希堆’。

阿巴阿巴： 如下图（狗头），能够看到均匀性能为 O(nlogn)的有：疾速排序，归并排序，堆排序，这些排序算法工夫复杂度低，适宜大数据集排序，当然工夫复杂度高的排序算法也有本人的用武之地的。

面试官： 讲一下你晓得的算法的应用场景呗

阿巴阿巴：

冒泡排序适宜： 实用于数据量不大，且要求排序稳固，数据量自身根本有序的状况。

抉择排序适宜： 当数据量不大且对于稳定性没有要求的状况（绝对冒泡排序来说缩小了替换次数）。

插入排序适宜： 适宜于数据量不大，对算法稳定性有要求，部分有序或整体绝对有序的状况。

归并排序适宜： 数据比拟大，且对算法稳定性有要求的状况。

疾速排序适宜： 数据量大，且数据较为扩散，且对稳定性没啥要求的状况。

堆排序适宜： 数据量大，对稳定性没要求的状况。

希尔排序： 希尔排序是对间接插入排序的一种优化，能够用于大型的数组，希尔排序比插入排序和抉择排序要快的多，并且数组越大，劣势越大。

基数排序适宜： 适宜数据集中，没有特地大的数据，对算法要求稳固的场景。

桶排序适宜： 适宜数据比拟集中的，对算法要求稳固的场景。

面试官： 好的，看你是有备而来，那我问个冷门点的，能够给我具体介绍下基数排序和桶排序吗？

阿巴阿巴： 基数排序属于“调配式排序”，又称“桶子法”或 bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素调配至某些“桶”中，藉以达到排序的作用。比如说有一批数据[31,19,46,23,17], 那么先依照“个”位上的数值进行排序，放进上面的桶中。

阿巴阿巴： 放进桶中后失去下图所示。

阿巴阿巴： 而后持续对桶中元素进行排序，从第 0 个桶开始往第 9 个桶顺次拿出，持续排序，失去蓝色局部数据。

阿巴阿巴： 而后持续对桶中元素进行排序，从第 0 个桶开始往第 9 个桶顺次拿出，持续排序，失去蓝色局部数据，对蓝色局部数据持续排序，依照“十位”上的数字进行排序。

阿巴阿巴： 最初将这些数据进行顺次从第 0 个桶开始往第 9 个桶顺次拿出，这样就都有序了。

面试官： 不错不错，基数排序如果数字很大的话，看起来对排序很不利呢？

阿巴阿巴： 是的如果有个数字很大，那么基数排序会显得相当吃力，最好是数据集中数据都差不多大。

 /**
 * 基数排序
 */
public class RadixSort {

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {int maxValue = arr[0];
        for (int value : arr) {if (maxValue < value) {maxValue = value;}
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {if (num == 0) {return 1;}
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {lenght++;}
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {// 思考正数的状况，这里扩大一倍队列数，其中 [0-9]对应正数，[10-19]对应负数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {for (int value : bucket) {arr[pos++] = value;
                }
            }
        }

        return arr;
    }
    /**
     * 主动扩容，并保留数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

面试官： 好的，那么桶排序呢，能够讲讲吗？

阿巴阿巴： 齐全能够，桶排序 (Bucket sort) 或所谓的箱排序，是一个排序算法，工作的原理是将数组分到无限数量的桶子里。每个桶子再个别排序（有可能再应用别的排序算法或是以递归形式持续应用桶排序进行排序）。抉择数据范畴特地集中的数据集排序时应用，比方有一组数据如：[1,2,1,3,5,3,2,1,2,3,4,5,2,1]，因为这部分数据集中在 1 - 5 之间，所以须要创立出 5 个桶，而后把元素放进匹配的桶里即可：1 号元素放入 1 号桶，2 号元素放入 2 号桶 ….

阿巴阿巴： 将元素放入到匹配的桶中。

阿巴阿巴： 再顺次从桶中拿出这些元素即排好序了。

面试官： 不错，把桶排序讲的清晰明了，那这样看来桶排序适宜数据集中跨度不大的数据集的排序状况。

阿巴阿巴： 是的桶排序适宜于

针对高考学生单科问题进行排序，问题个别是 0 -100，这时候建设 100 个桶，而后对这些问题进行排序即可。

医院须要针对患者年龄进行排序，年龄个别 0 -150，这时候建设 150 个桶，而后针对患者年龄进行排序即可。

// 桶排序
 public class BucketSort {private int[] bucketSort(int[] arr, int bucketSize) throws Exception {if (arr.length == 0) {return arr;}

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {if (value < minValue) {minValue = value;} else if (value > maxValue) {maxValue = value;}
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据调配到各个桶中
        for (int i = 0; i < arr.length; i++) {int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {if (bucket.length <= 0) {continue;}
            // 对每个桶进行排序，这里应用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {arr[arrIndex++] = value;
            }
        }
        
        return arr;
    }

    /**
     * 主动扩容，并保留数据
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}

阿巴阿巴：

面试官： 没想到你这么相熟，那就再讲下快排呗

阿巴阿巴： 疾速排序算法通过屡次比拟和替换来实现排序，其排序流程如下
(1) 首先设定一个分界值，通过该分界值将数组分成左右两局部。
(2)将大于或等于分界值的数据集中到数组左边，小于分界值的数据集中到数组的右边。此时，右边局部中各元素都小于或等于分界值，而左边局部中各元素都大于或等于分界值。
(3)而后，右边和左边的数据能够独立排序。对于左侧的数组数据，又能够取一个分界值，将该局部数据分成左右两局部，同样在右边搁置较小值，左边搁置较大值。右侧的数组数据也能够做相似解决。
(4)反复上述过程，能够看出，这是一个递归定义。通过递归将左侧局部排好序后，再递归排好右侧局部的程序。当左、右两个局部各数据排序实现后，整个数组的排序也就实现了。

如有一组数据须要排序：[31,33,46,12,17]

阿巴阿巴： 先选取基准值，这里选的是 31

阿巴阿巴： 而后从基准值后第一个元素开始向右遍历找到一个大于基准值的数同时从最初一个元素开始向左遍历找到一个小于基准值的数。

阿巴阿巴： 将这俩个元素进行替换。

阿巴阿巴： 持续向右遍历找到一个大于基准值的数同时从最初一个元素开始向左遍历找到一个小于基准值的数。

阿巴阿巴： 持续依照规定进行替换

阿巴阿巴： 失去如下图所示

阿巴阿巴： 最初将标准值放到右侧”指针“最初运行的地位使得基准值右边的数都小于等于基准值，基准值左边的数都大于等于基准值

阿巴阿巴： 这样一轮就完结了，快排中会进行递归，所以每个元素最终都能找到属于本人的地位

阿巴阿巴： 上面代码就是装置这个逻辑来实现的。

public class QuickSort{public static void quickSort(int[] arr, int left, int right) {if (left >= right) return;;
        // 返回基准值的小标，而后递归基准值左侧和基准值右侧数组
        int j = handler(arr, left, right);
        // 递归基准值左侧数组
        quickSort(arr,0, j - 1);
        // 递归基准值右侧数组
        quickSort(arr,j + 1, right);
    }


    public static int handler(int[] arr, int start, int end) {
        // 定义右边和左边用来寻找左侧大于基准值的数和右侧小于基准值的数
        int left = start;
        int right = end;
        int bound = arr[start];

        while (left < right) {
            // 始终找直到找到或越界了
            while(left < right && arr[left] <= bound) left++;
            while(left <= right && arr[right] >= bound) right--;
            // 将左侧找到的值和右侧进行交互
            if (left < right) {int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        // 这一步很要害，用来定位基准值的地位
        int temp = arr[start];
        arr[start] = arr[right];
        arr[right] = temp;
        return  right;
    }

}

阿巴阿巴： 再走一遍整个流程。

面试官： 好的今天来下班😈

算法是面试中必不可少的一部分，而排序算法被问到的频率相对来说也很高，因而对于根本的排序算法都须要把握好。除此之外，leetcode 中有一些题也是带有排序算法的思维，上面是 leetcode 上有一些对于排序的算法题。

参考 https://www.runoob.com/

/ 感激反对 /

以上便是本次分享的全部内容，心愿对你有所帮忙 ^_^

喜爱的话别忘了 分享、点赞、珍藏 三连哦~

欢送关注公众号 程序员巴士，来自字节、虾皮、招银的三端兄弟，分享编程教训、技术干货与职业规划，助你少走弯路进大厂。