排序算法 - 面试中的排序算法总结

Bertha 。 2022-06-01 01:59 220阅读 0赞

## 排序算法总结 ##

查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。

一般在面试中最常考的是**快速排序**和**归并排序**，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。面试官对于这些排序可能会要求比较各自的优劣、各种**算法的思想**及其**使用场景**，分析算法的**时间和空间复杂度**。

--------------------

## 排序算法分类、性能比较及使用场景 ##

#### 一、排序算法种类 ####

我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

排序算法大体可分为两种：

*  **比较排序**：时间复杂度最少可达到O(nlogn)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
 *  **非比较排序**：时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

#### 二、性能比较 ####

下表给出了常见比较排序算法的**性能**：  
![排序算法性能比较][SouthEast]

**排序算法稳定性**  
1） **稳定的**：如果存在多个具有相同排序码的记录，经过排序后，这些记录的相对次序仍然保持不变，则这种排序算法称为稳定的。  
插入排序、冒泡排序、归并排序、非比较排序（基数、计数、桶式）都是稳定的排序算法。  
2）**不稳定的**：直接选择排序、堆排序、希尔排序、快速排序。

#### 三、使用场景 ####

*  若n较小(如n≤50)，可采用直接**插入**或直接**选择**排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
 *  若文件初始状态**基本有序**(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜；
 *  若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。  
    
    
     *  **快速排序**是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
     *  **堆排序**所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
     *  若要求**排序稳定**，则可选用**归并排序**。通常可以将它和直接插入排序结合在一起使用:先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定 的，所以改进后的归并排序仍是稳定的。

--------------------

首先定义了一个Swap类，并且实现静态方法swap用于交换数组指定位置上的元素值。

/**
    * 交换数组指定位置上两个数的值
    * @param arr 数组
    * @param i 第一个数字在数组的下标
    * @param j 第二个数字在数组的下标
    */
    public static void swap(int[] arr, int i, int j) {
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
    }

--------------------

***下面是各个排序算法的具体思想和实现***

## 简单排序算法 ##

#### 冒泡排序 ####

冒泡排序是最简单的排序之一了，其**大体思想**就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。

举个例子，对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6,3。这样一次冒泡就完了，把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。

冒泡排序的时间复杂度为：O(n2)。

算法实现如下（Java）：

public static void main(String[] args) {
        int[] arr = {
       5, 3, 4, 8, 6};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 冒泡排序：稳定。属于交换排序算法的一种，另外一种是快速排序。
     * 时间复杂度：最好为 O(n^2)，最差为 O(n^2)，平均为 O(n^2)。空间复杂度：O(1)
     * @param arr 数组
     */
    public static void bubbleSort(int[] arr){
        if (arr == null || arr.length == 0) { // 数组为null或者没有元素
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) { 
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    Swap.swap(arr, j, j - 1);
                }
            }
        }
    }

--------------------

#### 选择排序 ####

思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。

举个例子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4。对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。

选择排序的时间复杂度为：O(n2)。

算法实现如下（Java）：

public static void main(String[] args) {
        int[] arr = {
       5, 3, 4, 8, 6};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 选择排序：不稳定。另外一种是堆排序。
     * 时间复杂度：最好为 O(n^2)，最差为 O(n^2)，平均为 O(n^2)。空间复杂度：O(1)
     * @param arr
     */
    public static void selectSort(int[] arr){
        if (arr == null || arr.length == 0) {
            return;
        }
        int minIndex = 0; // 记录每次循环最小值得数组下标，在循环外创建节省空间
        for (int i = 0; i < arr.length - 1; i++) { // 只需要比较n-1次
            minIndex = i; // 每次初始化为当前位置
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // 保证minIndex对应的元素为这次循环中的最小元素
                }
            }
            if (minIndex != i) { // 如果minIndex不为i，说明找到了更小的值，交换之
                Swap.swap(arr, i, minIndex);
            }
        }
    }

--------------------

#### 插入排序 ####

不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？ 就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。

举个例子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理。然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。

简单插入排序的时间复杂度为：O(n2)。

算法实现如下（Java）：

public static void main(String[] args) {
        int[] arr = {
       5, 3, 4, 8, 6};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 插入排序：稳定。另外一种是希尔排序。
     * 时间复杂度：最好为 O(n^2)，最差为 O(n^2)，平均为 O(n^2)。空间复杂度：O(1)
     * @param arr 数组
     */
    public static void insertSort(int[] arr){
        if (arr == null || arr.length == 0) {
            return;
        }
        for (int i = 1; i < arr.length; i++) { // 假设第一个数位置是正确的
            int j = i;
            int target = arr[j]; // 待插入的值
            // 将大于target的元素往后移动，直到小于target的元素
            while (j > 0 && arr[j - 1] > target) {
                arr[j] = arr[j - 1];
                j--;
            }
            if (j != i) {
                arr[j] = target; // 插入target数字到数组中
            }
        }
    }

--------------------

## 复杂排序算法 ##

#### 快速排序 ####

通过一趟排序将待排记录分割成独立的两部分，其中一部记录的关键均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序。快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是**表现最好**的排序算法。

快速排序虽然高端，但其实其**思想是来自冒泡排序**，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而**快速排序是比较和交换小数和大数**，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。

举个例子：对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。5,3,8,6,4 用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。5,3,8,6,4 首先设置i,j两个指针分别指向两端，j指针先扫描（思考一下为什么？）4比5小停止。然后i扫描，8比5大停止。交换i,j位置。5,3,4,6,8 然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。4,3,5,6,8 一次划分后达到了左边比5小，右边比5大的目的。之后对左右子序列递归排序，最终得到有序序列。

上面留下来了一个问题为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。

快速排序是**不稳定**的，其时间平均时间复杂度是：O(nlgn)。

总结快速排序的思想：**冒泡 + 二分 + 递归分治**，慢慢体会。

public static void main(String[] args) {
       int[] arr = {
       5, 3, 4, 8, 2};
    //        sort(arr);
       quickSortNonRec(arr);
       System.out.println(Arrays.toString(arr));
    }
    
    /**
    * 快速排序：不稳定。冒泡 + 二分 + 递归分治。
    * 时间复杂度：最好为 O(nlogn)，最差为 O(n^2)，平均为 O(nlogn)。空间复杂度：O(logn)
    * @param arr 数组
    */
    public static void sort(int[] arr) {
       if (arr == null || arr.length == 0) {
           return;
       }
       quickSort(arr, 0, arr.length - 1);
    }
    
    /**
    * 快速排序
    * @param arr 数组
    * @param left 左指针
    * @param right 右指针
    */
    public static void quickSort(int[] arr, int left, int right) {
       if (left > right) {
           return;
       }
       int pos = partition(arr, left, right); // 每次得到基准值的位置
       quickSort(arr, left, pos - 1); // 分别对数组的左右子数组重复快排调用
       quickSort(arr, pos + 1, right);
    }
    
    /**
    * 每次得到基准值下标，并进行一次排序
    * @param arr 数组
    * @param left 左指针
    * @param right 右指针
    * @return 基准值下标
    */
    public static int partition(int[] arr, int left, int right) {
       int temp = arr[left]; // 保存基准值
       while (left < right) {
           while (left < right && arr[right] > temp) { // 从右向左开始循环遍历
               right--;
           }
           arr[left] = arr[right]; // 左边的值都比基准值小
           while (left < right && arr[left] < temp) { // 从左向右开始循环遍历
               left++;
           }
           arr[right] = arr[left]; // 右边的值都比基准值大
       }
       arr[left] = temp;
       return left;
    }
    
    /**
    * 非递归实现
    * @param arr 数组
    */
    public static void quickSortNonRec(int[] arr) {
       if (arr == null || arr.length == 0) {
           return;
       }
       Stack<Integer> stack = new Stack<>(); // 用一个栈保存每次循环的子数组范围
       stack.add(0);
       stack.add(arr.length - 1);
       while (!stack.isEmpty()) {
           int right = stack.pop();
           int left = stack.pop();
           int pos = partition(arr, left, right);
           if (pos - 1 > left) {
               stack.add(left);
               stack.add(pos - 1);
           }
           if (pos + 1 < right) {
               stack.add(pos + 1);
               stack.add(right);
           }
       }
    }

--------------------

#### 归并排序 ####

归并排序是另一种不同的排序方法，因为归并排序使用了**递归分治**的思想，所以理解起来比较容易。

**基本思想**：先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列。倒着来看，其实就是先两两合并，然后四四合并，最终形成有序序列。

空间复杂度为：O(n)，时间复杂度为：O(nlogn)。

public static void main(String[] args) {
        int[] arr = {
       5, 3, 4, 8, 2};
    //        mergeSort(arr);
        mergeSortNonRec(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 归并排序：稳定。递归分治的实现。
     * 时间复杂度：最好为 O(nlogn)，最差为 O(nlogn)，平均为 O(nlogn)。空间复杂度：O(n)
     * @param arr 数组
     */
    public static void mergeSort(int[] arr){
        if (arr == null || arr.length == 0) {
            return;
        }
        mSort(arr, 0, arr.length - 1); // 归并排序
    }
    
    /**
     * 归并排序：递归分治
     * @param arr 数组
     * @param left 归并起始下标
     * @param right 归并结束下标
     */
    public static void mSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2; // 中间位置
        mSort(arr, left, mid); // 左半边排序 【left, mid】
        mSort(arr, mid + 1, right); // 右半边排序 【mid + 1, right】
        merge(arr, left, mid, right); // 合并左右两边的排序结果
    }
    
    /**
     * 合并一趟归并后的数组
     * @param arr 数组
     * @param left 左下标
     * @param mid 中间下标
     * @param right 右下标
     */
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; // 临时数组，保存合并后的两个数组
        int k = 0;
        int i = left; // 左半边数组起始位置
        int j = mid + 1; // 右半边数组起始位置
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) { // 每次保存比较小的那个数
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 如果前半个数组没有遍历完
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        // 如果后半个数组没有遍历完
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 因为arr的数组是从left开始到right的，所以更新对应的位置上的元素值
        for (int l = 0; l < temp.length; l++) {
            arr[l + left] = temp[l];
        }
    }
    
    /**
     * 归并排序非递归算法：
     * 设置每次归并长度为2的指数式增长
     * 每个归并长度内对整个数组进行归并
     * @param arr 数组
     */
    public static void mergeSortNonRec(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int len = 1; // 每次归并的长度
        while (len < arr.length) {
            for (int i = 0; i < arr.length; i += 2 * len) { // 将len归并规模的数组进行一次归并
                mergeSortNonRec(arr, i, len); // 每两两数组进行归并排序
            }
            len *= 2; // 将每组归并元素的规模扩大，1->2->4->8...
        }
    }
    
    /**
     * 归并排序，对数组元素进行归并排序
     * @param arr 数组
     * @param i 归并两个子数组的起始位置
     * @param length 归并两个子数组每个子数组的长度股
     */
    public static void mergeSortNonRec(int[] arr, int i, int length) {
        int start = i; // 保存起始位置由于恢复排序后的数组
        int arrLen1 = i + length; // 保存前面一个数组下标最大值
        int arrLen2 = i + 2 * length; // 保存后面一个数组下标最大值
        int j = i + length;
        int[] temp = new int[2 * length]; // 归并后的数组
        int k = 0;
        while (i < arrLen1 && j < arrLen2 && i < arr.length && j < arr.length) { // 注意i和j可能超出数组长度，因此需要考虑边界问题
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i < arrLen1 && i < arr.length) {  // 剩余数组元素直接拷贝，注意下标越界
            temp[k++] = arr[i++];
        }
        while (j < arrLen2 && j < arr.length) { // 剩余数组元素直接拷贝，注意下标越界
            temp[k++] = arr[j++];
        }
        k = 0;
        while (start < arr.length && k < 2 * length) { // 更新原数组相应位置元素的值为归并排序后的值
            arr[start++] = temp[k++];
        }
    }

--------------------

#### 堆排序 ####

堆排序是借助堆来实现的**选择排序**，思想同简单的选择排序，以下以**大顶堆**为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。

首先，实现堆排序需要解决两个问题：  
1. **建堆**：如何由一个无序序列键成一个堆？  
2. **调整堆**：如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

第一个问题，可以直接使用**线性数组**来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。  
第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为**筛选**。从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2取底个元素，由此筛选即可。

举个例子，49,38,65,97,76,13,27,49 序列的堆排序建初始堆和调整的过程如下：  
![堆排序1][1]  
![堆排序2][2]

堆排序算法的实现，以大顶堆为例。

public static void main(String[] args) {
        int[] arr = {
       5, 3, 4, 8, 2};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 堆排序：不稳定。选择排序的变种。
     * 时间复杂度：最好为 O(nlogn)，最差为 O(nlogn)，平均为 O(nlogn)。空间复杂度：O(1)
     * @param arr 数组
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        // 初始化建立大顶堆
        for (int i = arr.length / 2; i >= 0; i--) {
            heapAdjust(arr, i, arr.length - 1);
        }
        // 每次进行调整，得到排序的数组
        for (int i = arr.length - 1; i >= 0; i--) {
            Swap.swap(arr, 0, i);
            heapAdjust(arr, 0, i - 1);
        }
    }
    
    /**
     * 堆筛选，除了start之外，start-end均满足大顶堆的定义。
     * 调整之后start-end称为一个大顶堆
     * @param arr 待调整数组
     * @param start 起始指针
     * @param end 结束指针
     */
    public static void heapAdjust(int[] arr, int start, int end) {
        int temp = arr[start];
        for (int i = 2 * start + 1; i <= end; i *= 2) {
            // 左右孩子的节点分别为2*i+1, 2*i+2
            if (i < end && arr[i] < arr[i + 1]) {
                i++;
            }
            if (temp >= arr[i]) {
                break; // 已经为大顶堆，=保持稳定性
            }
            arr[start] = arr[i]; // 将子节点的值上移
            start = i; // 下一轮筛选
        }
        arr[start] = temp; // 插入到正确的位置
    }

--------------------

#### 希尔排序 ####

希尔排序是**插入排序**的一种高效率的实现，也叫**缩小增量排序**。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是**基本有序**的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。

**基本思想**：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。  
从上述排序过程可见，希尔排序的**特点**是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录组成一个子序列。

![希尔排序][SouthEast 1]

如上面的例子，第一趟排序时的增量为5，第二趟排序的增量为3。  
由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序， 只要作记录的少量比较和移动即可。  
因此希尔排序的效率要比直接插入排序高。

希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n1.3)。

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = {
       5, 3, 4, 8, 2};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 希尔排序：不稳定。插入排序的变种。
     * 时间复杂度：最好为 O(nlogn)，最差为 O(nlogn)，平均为 O(nlogn)。空间复杂度：O(1)
     * @param arr 数组
     */
    public static void shellSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int d = arr.length - 1; // 增量
        while (d >= 1) { // 增量大于等于1
            shellInsert(arr, d);
            d /= 2; // 每次增量除以2
        }
    }
    
    /**
     * 希尔排序的一趟排序
     * @param arr 待排数组
     * @param d 增量
     */
    public static void shellInsert(int[] arr, int d){
        for (int i = d; i < arr.length; i++) {
            int j = i;
            int target = arr[i]; // 带插入的元素
            while (j > 0 && arr[j - d] > target) { // 前面的数大于target，需要往后移动
                arr[j] = arr[j - d];
                j -= d;
            }
            if (j != i) {
                arr[j] = target; // 插入target数字到数组中
            }
        }
    }

--------------------

## 高级排序算法 ##

#### 计数排序 ####

如果在面试中有面试官要求你写一个**O(n)时间复杂度**的排序算法，你千万不要立刻说：这不可能！虽然前面基于比较的排序的下限是O(nlogn)。

但是确实也有线性时间复杂度的排序，只不过有**前提条件**，就是**待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间**。

其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。

public static void main(String[] args) {
        int[] arr = {
       5, 3, 4, 8, 2};
        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 计数排序：稳定。计数数组的下标为元素的值，计数数组的元素为原数组下标对应元素的出现次数。
     * 时间复杂度：最好为 O(n+k)，最差为 O(n+k)，平均为 O(n+k)。空间复杂度：O(n+k)
     * @param arr 数组
     */
    public static void countSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int max = max(arr);
        int[] countArr = new int[max + 1]; // 计数数组，长度为max+1，这样countArr[max]可以被赋值
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }
        int k = 0; // arr新数组的下标
        for (int i = 0; i < countArr.length; i++) {
            for (int j = 0; j < countArr[i]; j++) {
                arr[k++] = i; // 数组的下标i对应着元素，countArr[i]对应着元素出现的个数
            }
        }
    }
    
    /**
     * 得到数组元素的最大值
     * @param arr 数组
     * @return 最大值
     */
    public static int max(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

--------------------

#### 基数排序 ####

基数排序又是一种和前面排序方式不同的排序方式，基数排序不需要进行记录关键字之间的比较。

基数排序是一种借助**多关键字排序**思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有**多个优先级不同的关键字**。

比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面。如果对数字进行排序，那么**个位、十位、百位**就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。

基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。

public static void main(String[] args) {
        int[] arr = {
       5, 3, 4, 8, 2};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 基数排序：稳定。
     * 时间复杂度：最好为 O(d(n+r))，最差为 O(d(n+r))，平均为 O(d(n+r))。空间复杂度：O(r)
     * d为位数，r为基数（较复杂）
     * @param arr 数组
     */
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int maxBit = getMaxBit(arr);
        for (int i = 1; i <= maxBit; i++) {
            List<List<Integer>> buf = distribute(arr, i); // 分配
            collecte(arr, buf); // 收集
        }
    }
    
    /**
     * 分配
     * @param arr 待分配数组
     * @param iBit 要分配第几位
     * @return
     */
    public static List<List<Integer>> distribute(int[] arr, int iBit) {
        List<List<Integer>> buf = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            buf.add(new LinkedList<>());
        }
        for (int i = 0; i < arr.length; i++) {
            buf.get(getNBit(arr[i], iBit)).add(arr[i]);
        }
        return buf;
    }
    
    /**
     * 收集
     * @param arr 把分配的数据收集到arr中
     * @param buf
     */
    public static void collecte(int[] arr, List<List<Integer>> buf) {
        int k = 0;
        for (List<Integer> bucket : buf) {
            for (int ele : bucket) {
                arr[k++] = ele;
            }
        }
    }
    
    /**
     * 获取最大位数
     * @param arr
     * @return
     */
    public static int getMaxBit(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int ele : arr) {
            int len = (ele + "").length();
            if (len > max) {
                max = len;
            }
        }
        return max;
    }
    
    /**
     * 获取x的第n位，如果没有则为0
     * @param x
     * @param n
     * @return
     */
    public static int getNBit(int x, int n){
        String sx = x + "";
        if (sx.length() < n) {
            return 0;
        } else {
            return sx.charAt(sx.length() - n) - '0';
        }
    }

--------------------

#### 桶排序 ####

桶排序算是计数排序的一种改进和推广，但是网上有许多资料把计数排序和桶排序混为一谈。其实桶排序要比计数排序复杂许多。  
对桶排序的分析和解释借鉴这位兄弟的文章（有改动）：[http://hxraid.iteye.com/blog/647759][http_hxraid.iteye.com_blog_647759]。  
桶排序的平均时间复杂度为线性的O(N+C)，其中C=N\*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。

public static void main(String[] args) {
        int[] arr = {
       5, 3, 4, 8, 2};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 桶排序：稳定。将数组用桶来存储，关键在于映射函数，对每个桶可以使用快速排序，
     * 然后每个桶的元素比下一个桶的最小元素小。
     *
     * 时间复杂度：最好为 O(n)，最差为 O(nlogn)，平均为 O(n+c)。空间复杂度：O(n+m)
     * n为数的个数，m为桶的个数，c=n*(logn-logm)。桶越多，效率越高，n=m 达到 O(n)，但是占用很大的
     * 空间，桶内可用快排等
     * @param arr 数组
     */
    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        //      int bucketNums = 10; // 这里默认为10，规定待排数[0,100]
        List<List<Integer>> lists = new ArrayList<>(); // 桶保存数据
        for (int i = 0; i < 10; i++) {
            lists.add(new LinkedList<>()); // 链表结构
        }
        // 将数组中的数据添加到桶中
        for (int i = 0; i < arr.length; i++) {
            lists.get(f(arr[i])).add(arr[i]);
        }
        // 将每个桶的元素进行排序
        for (int i = 0; i < lists.size(); i++) {
            Collections.sort(lists.get(i));
        }
        // 得到排序后的数组
        int k = 0;
        for (int i = 0; i < lists.size(); i++) {
            for (int val: lists.get(i)) {
                arr[k++] = val;
            }
        }
    }
    
    /**
     * hash函数，桶的散列函数
     * @param x 输入一个整数
     * @return 散列函数值
     */
    public static int f(int x) {
        return x / 10;
    }

[SouthEast]: /images/20220601/c8ac4fe3f948473b9bbfd00e72ab9e2b.png
[1]: /images/20220601/52d4a5265b8c4b1c8ca88adc929af068.png
[2]: /images/20220601/5e58976bf8ca486fa16f89d3973054b4.png
[SouthEast 1]: /images/20220601/002b7b4ef1a842179dafd779dd6472b4.png
[http_hxraid.iteye.com_blog_647759]: http://hxraid.iteye.com/blog/647759