🍗排序合集 【十大经典排序】

🚩传送门：牛客题目

题目

给定一个数组，请你编写一个函数，返回该数组排序后的形式。

示例 1:

输入: [5,2,3,1,4] 输出: [1,2,3,4,5]

示例 2:

输入: [5,1,6,2,5] 输出: [1,2,5,5,6]

备注：

数组的长度不大于100000，数组中每个数的绝对值不超过

解题思路：调用库函数 Arrays.sort

import java.util.Arrays;
public class Solution {
    public int[] MySort (int[] arr) {
        //调用库函数sort；
        Arrays.sort(arr);
        return arr;
    }
}

解题思路：冒泡排序 BubbleSort

• 将第一个元素和第二个元素比较，若前者大于后者，则交换两者的位置，再将第二个元素与第三个元素比较，若前者大于后者则交换两者位置，以此类推直到倒数第二个元素与最后一个元素比较，若前者大于后者，则交换两者位置。
• 这样一轮比较下来将会把序列中最大的元素移至序列末尾，这样就安排好了最大数的位置，接下来只需对剩下的（n-1）个元素，重复上述操作即可。

复杂度分析

时间复杂度：或者 ，其中 是数组的长度。

• 若原数组本身就是有序的（这是最好情况），仅需 n-1次比较就可完成，时间复杂度依然为；

• 若是倒序，比较次数为 ，交换次数和比较次数等值。为

  综上所述：冒泡排序总的平均时间复杂度为：，时间复杂度和数据状况无关。

空间复杂度： ，使用常数个辅助单元

稳定性：

  - 当两个相同大小的元素相邻，相等的时候是不会交换位置的。
  - 当两个相等元素相离较远，只是会把他们交换到相邻的位置。他们的位置前后关系不会发生变化。

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
冒泡					稳定

整理代码

public class Solution {
    public void BubbleSort(int[] arr){
        //1. 2个数比较1次,arr.length 个数比较 arr.length-1 次
        for(int i=0;i<arr.length-1;i++){ 
            //2. 从 0 比较到 arr.length-1-i 
            for(int j=0;j<arr.length-1-i;j++){
                //3. 相邻两个元素作比较，如果前面元素大于后面，进行交换
                if(arr[j]>arr[j+1]){ 
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}

解题思路：选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。

它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

复杂度分析

时间复杂度： ，其中 是数组的长度。

比较次数为 ，故而时间复杂度为

空间复杂度： ，使用常数个辅助单元

稳定性：

  - 当两个相同大小的元素相邻，相等的时候是会交换位置的。
  - 当两个相等元素相离较远，只是会把他们交换到相邻的位置。他们的位置前后关系会发生变化。

比如 A：80 B：80 C：70 这三个卷子从小到大排序 第1步：会把 C 和 A 做交换，变成 C B A 第2步和第3步不需要再做交换了。所以排序完是 C B A 但是稳定的排序应该是 C A B

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
选择					不稳定

整理代码

public class Solution {
    public void SelectionSort(int[] arr){
        //1. 依次从每个下标位置出发开始选择
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];        //假设下标为i的数为最小值
            int minindex=i;            //创建minindex变量确定min位置
            //2.通过for循环比较出最小值，minindex就是最小值坐标
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<min) {
                    min=arr[j];    //保存最小值
                    minindex=j;        //保存其下标
                }
            }
            //3.将最小值与arr[i]交换
            int temp=arr[i];
            arr[i]=arr[minindex];
            arr[minindex]=temp;
        }
    }
}

解题思路：插入排序（Insertion Sort）

插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小（例如量级小于千），那么插入排序还是一个不错的选择。

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

复杂度分析

时间复杂度： ，其中 是数组的长度。

比较次数为 ，故而时间复杂度为

空间复杂度： ，使用常数个辅助单元

稳定性：

  - 当两个相同大小的元素相邻，相等的时候是不会交换位置的。
  - 当两个相等元素相离较远，只是会把他们交换到相邻的位置。他们的位置前后关系不会发生变化。

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
冒泡					稳定

整理代码

public class Solution {
    public void InsertionSort(int[] arr){
        //1. 从下标1开始遍历
        for (int i = 1; i < arr.length; i++) {
            //2.记录当前需要插入的值
            int key = arr[i];
            int j = i-1;
            //3.从后往前寻找要插入的位置，其他元素往后稍一稍给腾个地方
            while (j >= 0 && arr[j] > key){
                arr[j+1] = arr[j];
                j--;
            }
            //4.插入
            arr[j+1] = key;
        }
    }
}

解题思路：希尔排序（Shell Sort）

插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小（例如量级小于千），那么插入排序还是一个不错的选择。

1959年Shell 发明，第一个突破 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为 。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为 时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

我们来看下希尔排序的基本步骤，在此我们选择增量 ，缩小增量继续以 的方式，这种增量选择我们可以用一个序列来表示，，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

复杂度分析

时间复杂度： ，其中 是数组的长度。

空间复杂度： ，使用常数个辅助单元

稳定性：

  - 当两个相同大小的元素相邻，相等的时候是会交换位置的。
  - 当两个相等元素相离较远，只是会把他们交换到相邻的位置。他们的位置前后关系会发生变化。

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
希尔					不稳定

整理代码

public class Solution {
    public void shellSort(int[] arr){
        //1. step:步长,依次除2求步长直至步长为0
        for (int step = arr.length / 2; step > 0; step /= 2) {
            //2. 从 [step,arr.length) 开始的数需要抽出来和前面数比较
            for (int i = step; i < arr.length; i++) {
                int value = arr[i];
                int j;    

                //3. 比 value 大的后移
                for (j=i - step; j >= 0 && arr[j] > value; j -= step) {
                    arr[j + step] = arr[j]; 
                }
                //4. 此时j<0或者arr[j]<=vaule,故vaule应放在 j+step 处
                arr[j + step] = value;  
            }
        }
    }
}

解题思路：归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2-路归并。

本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为 。

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

复杂度分析

时间复杂度： ，其中 是数组的长度。

每次合并操作的平均时间复杂度为 ，而完全二叉树的深为。总的平均时间复杂度为 。而且，归并排序的最好、最坏、平均时间复杂度均为 。

空间复杂度： ，使用常数个辅助单元

稳定性：

  - 当两个相同大小的元素相邻，相等的时候是不会交换位置的。
  - 当两个相等元素相离较远，只是会把他们交换到相邻的位置。他们的位置前后关系不会发生变化。

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
归并					稳定

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java 中 Arrays.sort() 采用了一种名为 TimSort 的排序算法，就是归并排序的优化版本。

整理代码

public class Solution {

    public static void MergeSort(int []arr){
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int []temp = new int[arr.length];
        sort(arr,0,arr.length-1,temp);
    }

    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);        //左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);     //右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp); //将两个有序子数组合并操作
        }
    }

    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;        //左序列指针
        int j = mid+1;        //右序列指针
        int t = 0;            //临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){                //将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){            //将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}

解题思路：快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比关键值小，另一部分均比关键值大，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

• 从数列中挑出一个元素，称为 "基准"（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

复杂度分析

时间复杂度： ，其中 是数组的长度。

  - 每次划分都是按照折半划分，那么其时间复杂度是 ![](https://cdn.nlark.com/yuque/__latex/32951b5fd8b07713711289c8aba258b6.svg#card=math&code=%5Csmall%20O%28n%5Ccdot%20%5Clog_2n%29&id=BrSE5) 
  - 极端情况就是我们平时说的有序的情况，如`1,2,3,4,5`，这样其实就退化成 ![](https://cdn.nlark.com/yuque/__latex/56520ff852bbdb26d3f8f6e0923fd03e.svg#card=math&code=%5Csmall%20O%28n%5E2%29&height=20&id=Ew2ro) 。

空间复杂度： ，使用常数个辅助单元

稳定性：

  - 当两个相同大小的元素相邻，相等的时候是会交换位置的。
  - 当两个相等元素相离较远，只是会把他们交换到相邻的位置。他们的位置前后关系会发生变化。

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
快排					不稳定

整理代码

public class Solution {

    //快速排序算法(从小到大)
    //arr:需要排序的数组，begin:需要排序的区间左边界，end:需要排序的区间的右边界 [begin,end]
    public static int partition(int arr[], int begin, int end) {
        int temp = arr[begin]; //将区间的第一个数作为基准数
        int i = begin;            //从左到右进行查找时的"指针"，指示当前左侧位置
        int j = end;             //从右到左进行查找时的"指针"，指示当前右侧位置
         //当i=j时候,就是基准的位置
        while (i < j)
          {
            //当右边的数大于基准数时，跳过，继续向左查找
            //不满足条件时跳出循环，此时的j对应的元素是小于基准元素的
            while (i<j && arr[j] > temp)
                j--;
            //将右边小于等于基准元素的数填入右边相应位置
            arr[i] = arr[j];
            //当左边的数小于等于基准数时，跳过，继续向右查找(重复的基准元素集合到左区间)
            //不满足条件时跳出循环，此时的i对应的元素是大于等于基准元素的
             while (i < j && arr[i] <= temp)
                i++;
               //将左边大于基准元素的数填入左边相应位置
               arr[j] = arr[i];
         }
         //将基准元素填入相应位置
         arr[i] = temp;
         //此时的i即为基准元素的位置
         return i;
    }

    public static void QuickSort(int arr[], int begin, int end)
    {
        //如果区间不只一个数
        if (begin < end)
         {     //获取基准的位置
            int i = partition(arr, begin, end);
            //对基准元素的左边子区间进行相似的快速排序
            QuickSort(arr, begin, i - 1);
            //对基准元素的右边子区间进行相似的快速排序
            QuickSort(arr, i + 1, end);
          }
          //如果区间只有一个数或者end>begein，则结束
    }
}

Split 写法

思想：
i 指向的的永远是小于基准的最右侧，所有当遇到大于基准的 j 时候并不需要关心那个数字，j++ 即可，当 j再次遇到小于基准的只需要把 i 后面的那个大于基准的和 j 遇到小于基准的数字互换即可，这样就仍能保持大于基准的和小于基准的分成两列。

void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}

//划分数组的函数
int split(int a[], int low, int high)
{
    int i = low;    //i指向比较元素的期望位置
    int x = a[i];    //将该数组第一个元素设置为比较元素
    //从数组的第二个元素起开始遍历，若找到的元素大于比较元素，则跳过
    for(int j = low+1;j<=high;j++)
        //若找到了小于比较元素的数，则将其与前面较大的数进行交换
        if (a[j] <= x)
        {
            i++;
            if(i!=j)
                swap(a[i], a[j]);
        }
    swap(a[low], a[i]);    //将比较元素交换到期望位置
    return i;
}

//快速排序
void quicksort(int a[], int low, int high)
{
    if (low < high)
    {
        int i = split(a, low, high);    //划分数组并获得比较元素位置
        quicksort(a, low, i - 1);    //对比较元素左边进行排序
        quicksort(a, i + 1, high);    //对比较元素右边进行排序
    }
}

解题思路：堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并满足堆的性质：

  - 每个结点的值都大于或等于其左右孩子结点的值，称为**大顶堆**；
  - 或者每个结点的值都小于或等于其左右孩子结点的值，称为**小顶堆**。

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：**arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] **
小顶堆：**arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] **

其中性质：
设当前元素在数组中以 R[i] 表示，那么，

1. 它的左孩子结点是：R[2*i+1];
2. 它的右孩子结点是： R[2*i+2];
3. 它的父结点是： R[(i-1)/2];

堆排序的基本思想是：

1. 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
2. 将其与末尾元素进行交换，此时末尾就为最大值。
3. 然后将剩余 **n-1** 个元素重新构造成一个堆，再与末尾交换。
4. 如此反复执行，便能得到一个有序序列了

步骤1: 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

1. 假设给定无序序列结构如下

1. 此时我们从最后一个非叶子结点开始，从左至右，从下至上进行调整。

   最后一个非叶子结点： arr.length/2-1

1. 找到第下一个非叶节点，重复上述步骤

   下一个非叶节点是4，由于[4,9,8]中 9 元素最大，4 和 9 交换。

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中 6 最大，交换 4 和 6 。

此时，我们就将一个无需序列构造成了一个大顶堆。
步骤2： 将堆顶元素与末尾元素进行交换，使末尾元素最大。

步骤3：然后继续调整堆，形成大顶堆，再将堆顶元素与末尾元素交换

1. 调整形成大顶堆

1. 将堆顶元素和末尾元素交换

   将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8

步骤4：如此反复进行交换、重建、交换。

复杂度分析

时间复杂度： ，其中 是数组的长度。

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为 ，在交换并重建堆的过程中，需交换 次，而重建堆，根据完全二叉树的性质，逐步递减，近似。所以堆排序时间复杂度一般认为就是级。

空间复杂度： ，使用常数个辅助单元

稳定性：

  - 当两个相同大小的元素相邻，相等的时候是会交换位置的。
  - 当两个相等元素相离较远，只是会把他们交换到相邻的位置。他们的位置前后关系会发生变化。

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
堆排序					不稳定

整理代码

public class Solution {
    public static void HeapAdjust(int[] array, int parent, int length) {
        int temp = array[parent];   // temp保存当前父节点
        int child = 2 * parent + 1; // 先获得左孩子

        while (child < length) {
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }

            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= array[child]) break;

            // 把孩子结点的值赋给父结点
            array[parent] = array[child];

            // 选取孩子结点的左孩子结点,继续向下筛选
            parent = child;
            child = 2 * child + 1;
        }

        array[parent] = temp;
    }

    public static void heapSort(int[] arr) {
        // 循环建立初始堆(起始值为最后一个非叶子节点,从右向左开始)
        for (int i = arr.length / 2; i >= 0; i--) {
            HeapAdjust(arr, i, arr.length);
        }

        // 进行n-1次循环，完成排序
        for (int i = arr.length - 1; i > 0; i--) {
            // 最后一个元素和第一元素进行交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;

            // 筛选 R[0] 结点，得到i-1个结点的堆
            HeapAdjust(arr, 0, i);
        }

    }
}

解题思路：计数排序（Counting Sort）

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为 （其中 是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当 的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是 , 如归并排序，堆排序）

算法描述：

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
• 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素 i 放在新数组的第 C(i) 项，每放一个元素就将 C(i) 减去 1 。

复杂度分析

时间复杂度：，其中 是数组的长度。

空间复杂度：

稳定性：

  - 当两个相同大小的元素相邻，相等的时候是不会交换位置的。
  - 当两个相等元素相离较远，只是会把他们交换到相邻的位置。他们的位置前后关系不会发生变化。

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
计数排序					稳定

1. 首先我们需要知道最大的球和最小的球分别对应的元素，这里最大的对应 ，最小的对应 。

1. 然后我们需要用 个计数器来分别统计 到 之间每种小球的个数（假设 到 之间的小球对应的元素均为整数），下图中我们用带有标记的桶来表示。

1. 我们遍历所有的小球，将每个值为 的小球放入到第 个桶中

1. 最后，我们从左往右依次将每个桶里的小球取出，每取出一个小球，对应桶的计数器减 ，直到计数器为 ，将所有桶内的小球都取出后，小球就是从小到大排列了。

整理代码

public class Solution {
    public static void CountSort(int[] arr) {
        // 1.找出数组A中的最大值
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            max = Math.max(max, num);
        }
        // 2.初始化计数数组count
        int[] count = new int[max+1];
        // 3.对计数数组各元素赋值
        for (int num : arr) {
            count[num]++;
        }
        // 4.创建结果数组的起始索引
        int index = 0;
        // 5.遍历计数数组，将计数数组的索引填充到结果数组中
        for (int i=0; i<count.length; i++) {
            while (count[i]>0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }
}

解题思路：桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

算法描述：

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

复杂度分析

时间复杂度：，其中 是数组的长度。

空间复杂度：

稳定性：

  - 当两个相同大小的元素相邻，相等的时候是不会交换位置的。
  - 当两个相等元素相离较远，只是会把他们交换到相邻的位置。他们的位置前后关系不会发生变化。

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
计数排序					稳定

整理代码

public class Solution {
    public static void BucketSort(int[] arr){
        // 1.计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        // 2.计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;    //#计算桶数量
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }

        // 3.将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);    //#确定所属桶序号
            bucketArr.get(num).add(arr[i]);
        }

        // 4.对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }

        // 5.将桶中的元素赋值到原序列
        int index = 0;
        for(int i = 0; i < bucketArr.size(); i++){
            for(int j = 0; j < bucketArr.get(i).size(); j++){
                arr[index++] = bucketArr.get(i).get(j);
            }
        }
    }
}

解题思路：基数排序（Radix Sort）

我们人在对数字进行排序的时候是按照本能对最高位先排，然后是次高位，最后…最低位置。

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述：

• 取得数组中的最大数，并取得位数；
• arr 为原始数组，从最低位开始取每个位组成 radix 数组；
• 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；

复杂度分析

时间复杂度： ，其中 是数组的长度。

空间复杂度：

稳定性：

其中 n 表示待排序列的规模，d 表示待排序列的最大位数，k 表示每一位数的范围

  - 当两个相同大小的元素相邻，相等的时候是不会交换位置的。
  - 当两个相等元素相离较远，只是会把他们交换到相邻的位置。他们的位置前后关系不会发生变化。

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
基数排序					稳定

整理代码

/**
 * 基数排序
 * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }


    //获取最高位
    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;
    }

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