面试官超级喜欢问的排序算法

脚本之家 2022-05-10

The following article is from 程序员巴士 Author 七十七

关注

“脚本之家

”，与百万开发者在一起

来源 | 程序员巴士（ID：tech-bus）
如若转载请联系原公众号

前言

阿巴阿巴刷了半年的算法，决定出去试试水，巧了，这次面试官让她谈谈对排序算法的理解。

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

阿巴阿巴： 了解一点，排序算法这一块主要有冒泡排序、插入排序、希尔排序、选择排序、快速排序、归并排序、堆排序、基数排序、桶排序。

面试官： 很不错，那你知道什么是稳定性吗，上述这些算法都是稳定的吗？他们的复杂度分别是多少呀？

阿巴阿巴： 稳定性就是说，如果有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="">= 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;
    }

}