排序算法

排序算法说明

排序的定义

对一序列对象根据某个关键字进行排序

术语说明

  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
  • 不稳定：如果a原本在b前面，而a=b，排序之后a可能会出现在b的后面
  • 内排序：所有排序操作都在内存中完成；
  • 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
  • 时间复杂度：一个算法执行所耗费的时间
  • 空间复杂度：运行完一个程序所需内存的大小

算法总结

排序算法
总结名词解释

  • n:数据规模
  • k:“桶”的个数
  • In-place:占用常数内存，不占用额外内存
  • Out-place:占用额外内存

比较与非比较的区别

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法。它重复地走访要排序的数列，一次比较两个元素，如果它们错误就把它们交换过来。走访数列的工作是重复的进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

  • 比较相邻的元素，如果第一个比第二个大，就交换它们两个；
  • 对每一对相邻元素作相同的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  • 针对所有的元素重复以上的步骤，除了最后一个；
  • 重复步骤1~3，直到排序完成

动画演示

冒泡排序

代码实现

可以对冒泡排序设置一个标记flag，从而优化冒泡排序时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] bubbleSort(int[] array) {
    if (array.length == 0){
        return array;
    }
    for (int i = 1;i < array.length; i++>) {
        // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
        boolean flag = true;
        for (int j = 0;j < array.length - i; j++>) {
            if (array[j + 1] < array[j]) {
                int temp = array [j];
                array[j] = array[j + 1];
                array[j + 1] = temp;

                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
    return array;
}

算法分析

最佳情况：T(n) = O(n)
最差情况：T(n) = O(n^2)
平均情况：T(n) = O(n^2)

空间复杂度：O(1)


选择排序(Selection Sort)

表现最稳定的排序算法之一，无论什么数据进去都是O(n^2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧
选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理：首先在末排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

  • 初始状态：无序区为R[1..n]，有序区为空
  • 第i趟排序排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第一个记录R交换，使R[1..i]和R[i+1..n]分别变成记录个数增加1个的新有序区和记录个数减少1个的新无序区。
  • n-1趟结束，数组有序化了。

动画演示

选择排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int[] selectionSort(int[] array) {
    if (array.length == 0){
        return array;
    }

    // 总共要经过N-1轮比较
    for (int i = 0;i < array.length - 1; i++) {
        int minIndex = i;
        
        // 每轮需要比较的次数为N-i
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                
                // 记录目前能找到的最小值元素的下标
                minIndex = j;
            }
        }

        // 将找到的最小值和i位置所在的值进行交换
        if (i != minIndex) {
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
    return array;
}

算法分析

最佳情况：T(n) = O(n^2)
最差情况：T(n) = O(n^2)
平均情况：T(n) = O(n^2)

空间复杂度：O(1)


插入排序(Insertion Sort)

插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已经排序元素逐步向后挪位，为最新元素提供插入空间。

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  • 从第一个元素开始，该元素可以认为已经被排序；
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  • 如果该元素(已排序)大于新元素，将该元素移到下一位置；
  • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  • 将新元素插入到该位置后；
  • 重复步骤2~5

动画演示

插入排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] insertionSort(int[] array) {
    if (array.length == 0) {
        return array;
    }
    // 从小标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
    for (int i = 1;i < array.length; i++) {
        // 记录要插入的数据
        int temp = array[i];
        // 从已经排序的序列最右边开始比较，找到比其小的数
        int j = i;
        while(j > 0 && temp < array[j - 1]) {
            array[j] = array[j - 1];
            j--;
        }
        // 存在比其小的数，插入
        if (j != i) {
            array[j] = temp;
        }
    }
    return array;
}

算法分析

最佳情况：T(n) = O(n)
最坏情况：T(n) = O(n^2)
平均情况：T(n) = O(n^2)

空间复杂度：O(1)


希尔排序(Shell Sort)

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2)的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

算法描述

我们来看下希尔排序的基本步骤，在此我们选择增量gap = length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…..1}，称为增量序列。希尔排序的增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实中国增量序列不是最优的。此处我们做示例使用希尔增量。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 选择一个增量序列t1，t2，…..，tk，其中ti>tj,tk = 1;
  • 按增量序列个数k，对序列进行k趟排序；
  • 每趟排序，根据对应的增量ti，将待排序序列分割成若干长度为m的子序列，分别对各个子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动画演示

希尔排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] shellSort(int[] array) {
    int len = array.length;
    int temp, gap = len / 2;
    while(gap > 0) {
        for (int i = gap; i < len; i++) {
            temp = array[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && array[preIndex] > temp) {
                array[preIndex + gap] = array[preIndex];
                preIndex -= gap;
            }
            array[preIndex + gap] = temp;
        }
        gap /= 2;
    }
    return array;
}

算法分析

最佳情况：T(n) = O(nlog2n)
最坏情况：T(n) = O(nlog2n)
平均情况：T(n) = O(nlog2n)

空间复杂度：O(1)


归并排序(Merge Sort)

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn)的时间复杂度，代价是需要额外的空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，就能得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2路归并。

算法描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列；
  • 对这两个子序列分别采用归并排序；
  • 将两个排序好的子序列合并成一个最终的排序序列

动画演示

归并排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int[] mergeSort(int[] array) {
    if (array.length < 2) {
        return array;
    }
    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array,0,mid);
    int[] right = Arrays.copyOfRange(array,mid,array.length);
    return merge(mergeSort(left),mergeSort(right));
}

public int[] merge(int[] left,int[] right) {
    int[] result = new int[left.length + right.length];
    for (int index = 0,i = 0,j = 0;index < result.length; index++){
        if (i >= left.length) {
            result[index] = right[j];
            j++;
        }else if (j >= right.length) {
            result[index] = left[i];
            i++;
        }else if (left[i] > right[j]) {
            result[index] = right[j];
            j++;
        }else {
            result[index] = left[i];
            i++;
        }
    }
    return result;
}

算法分析

最佳情况：T(n) = O(n)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)

空间复杂度：O(n)


快速排序(Quick Sort)

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

算法描述

快速排序使用分治法来把一个串(list)分成两个字串(sub-lists)。具体算法描述如下：

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

动画演示

快速排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int[] quickSort(int[] array,int left,int right) {
    if (left < right) {
        // 哨兵划分
        int pivot = partition(array, left, right);
        // 递归左子数组，右子数组
        quickSort(array, left, pivot - 1);
        quickSort(array, pivot + 1, right);
    }
    return array;
}

public int partition(int[] array, int left, int right) {
    // 以array[left]作为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && array[j] >= array[left]){
            // 从右向左找首个小于基准数的元素
            j--;
        }
        while (i < j && array[i] <= array[left]){
            // 从左向右找首个大于基准数的元素
            i++;
        }
        // 交换这两个元素
        swap(array,i,j);
    }
    // 将基准数交换至两子数组的分界线
    swap(array,i,left);
    // 返回基准数的索引
    return i;
}

public void swap(int[] array,int i,int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

算法分析

最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(n^2)
平均情况：T(n) = O(nlogn)

空间复杂度：O(logn)


堆排序(Heap Sort)

堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结果，并同时满足堆积的性质：即子结点的键值或索引总是小于(或大于)它的父节点。

算法描述

  • 将初始待排序关键字序列(R1,R2,…,Rn)构建成大顶堆，此堆为初始的无序区；
  • 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,…,Rn-1)和新的有序区(Rn)，且满足R[1，2…n-1] <= R[n];
  • 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,…,Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2,..Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

动画演示

堆排序1
堆排序2

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int len;

public int[] heapSort(int[] array) {
    len = array.length;
    if (len < 1) {
        return array;
    }
    // 构建一个最大堆
    bulidMaxHeap(array);
    // 循环将堆首位(最大值)与末位交换，然后重新调整最大堆
    while (len > 0) {
        swap(array, 0, len - 1);
        len--;
        adjustHeap(array, 0);
    }
    return array;
}

// 建立最大堆
public void buildMaxHeap(int[] array) {
    // 从最后一个非叶子节点开始向上构造最大堆
    for (int i = (len / 2 - 1); i >= 0; i--) {
        adjustHeap(array, i);
    }
}

// 调整使之成为最大堆
public void adjustHeap(int[] array, int i) {
    int maxIndex = i;
    //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
    if (i * 2 < len && array[i * 2] > array[maxIndex])
        maxIndex = i * 2;
    //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
    if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
        maxIndex = i * 2 + 1;
    //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
    if (maxIndex != i) {
        swap(array, maxIndex, i);
        adjustHeap(array, maxIndex);
    }
}

public void swap(int[] array,int i,int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

算法分析

最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)

空间复杂度：O(1)


计数排序(Counting Sort)

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序(Counting Sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

计数排序的特征
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。

算法描述

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

动画演示

计数排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int[] countingSort(int[] array){
    // 统计数组最大元素m
    int m = 0;
    for (int num : array) {
        m = Math.max(m,num);
    }
    // 统计各个数字的出现次数
    // counter[num] 代表num的出现次数
    int[] counter = new int[m + 1];
    for (int num : array) {
        counter[num]++;
    }
    // 求counter的前缀和，将“出现次数”转换成“尾索引”
    // 即counter[num] - 1是num在res中最后一次出现的索引
    for(int i = 0;i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 倒序遍历array，将各元素填入结果数组res
    // 初始化数组res用于记录结果
    int n = array.length;
    int[] res = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int num = array[i];
        // 将num放置到对应索引处
        res[counter[num] - 1] = num;
        // 令前缀和自减1，得到下次放置num的索引
        counter[num]--;
    }
    // 使用结果数组res覆盖原数组array；
    for (int i = 0;i < n; i++){
        array[i] = res[i];
    }
    return array;
}

算法分析

当输入的元素是n个0到k之间的整数时，它的运行时间是O(n+k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1)，这使得计数排序对应数据范围很大的数组，需要大量时间和内存。
最佳情况：T(n) = O(n+k)
最差情况：T(n) = O(n+k)
平均情况：T(n) = O(n+k)

空间复杂度：O(k)


桶排序(Bucket Sort)

桶排序(Bucket Sort)是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的缺点。
桶排序的工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)

算法描述

  • 人为设置一个BucketSize，作为每个桶所能放置多少个不同数值(例如当BucketSize==5时，该桶可以存放{1，2，3，4，5}这几种数字，但是容量不限，即可以存放100个3)；
  • 遍历输入数据，并且把数据一个个放到对应的桶里去；
  • 对每个不是空的桶进行排序，可以使用其他排序方法，也可以递归使用桶排序；
  • 从不是空的桶里把排好序的数据拼接起来。

    注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。

图片演示

元素分布在桶中：
桶排序1
然后，元素在每个桶中排序：
桶排序2

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public int[] sort(int[] sourceArray) {
    // 对 arr 进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    return bucketSort(arr, 5);
}

public int[] bucketSort(int[] arr, int bucketSize) {
    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 = sort(bucket);
        for (int value : bucket) {
            arr[arrIndex++] = value;
        }
    }

    return arr;
}

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

算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
最佳情况：T(n) = O(n+k)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n+k)

空间复杂度：O(n + k)

基数排序(Radix Sort)

基数排序(Radix Sort)也是非比较的排序算法，对每一位进行排序，从最低为开始排序，复杂度为O(kn)，n为数组长度，k为数组中的数的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依此类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法描述

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

动画演示

基数排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/* 获取元素 num 的第 k 位，其中 exp = 10^(k-1) */
public int digit(int num, int exp) {
    // 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
    return (num / exp) % 10;
}

/* 计数排序（根据 nums 第 k 位排序） */
public void countingSortDigit(int[] nums, int exp) {
    // 十进制的位范围为 0~9 ，因此需要长度为 10 的桶
    int[] counter = new int[10];
    int n = nums.length;
    // 统计 0~9 各数字的出现次数
    for (int i = 0; i < n; i++) {
        int d = digit(nums[i], exp); // 获取 nums[i] 第 k 位，记为 d
        counter[d]++;                // 统计数字 d 的出现次数
    }
    // 求前缀和，将“出现个数”转换为“数组索引”
    for (int i = 1; i < 10; i++) {
        counter[i] += counter[i - 1];
    }
    // 倒序遍历，根据桶内统计结果，将各元素填入 res
    int[] res = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int d = digit(nums[i], exp);
        int j = counter[d] - 1; // 获取 d 在数组中的索引 j
        res[j] = nums[i];       // 将当前元素填入索引 j
        counter[d]--;           // 将 d 的数量减 1
    }
    // 使用结果覆盖原数组 nums
    for (int i = 0; i < n; i++)
        nums[i] = res[i];
}

/* 基数排序 */
public int[] radixSort(int[] nums) {
    // 获取数组的最大元素，用于判断最大位数
    int m = Integer.MIN_VALUE;
    for (int num : nums)
        if (num > m)
            m = num;
    // 按照从低位到高位的顺序遍历
    for (int exp = 1; exp <= m; exp *= 10)
        // 对数组元素的第 k 位执行计数排序
        // k = 1 -> exp = 1
        // k = 2 -> exp = 10
        // 即 exp = 10^(k-1)
        countingSortDigit(nums, exp);
    return nums;
}

算法分析

最佳情况：T(n) = O(nk)
最差情况：T(n) = O(nk)
平均情况：T(n) = O(nk)

空间复杂度：O(n + k)

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶；
  • 计数排序：每个桶只存储单一键值；
  • 桶排序：每个桶存储一定范围的数值；