本文作为算法学习的一环，总结了十种基本的排序算法的特点.

配合算法练习工具 SortingPractice，手写算法加以练习效果更佳。

1. 比较排序

通过对元素之间两两比较确定先后顺序减少逆序对，从而使整体有序的排序算法。比较排序算法的性能下限为 Ω(nlogn).

1.1 选择排序

过程为将每轮遍历得到最小值置于待排序区间的首位，并缩小待排序区间。重复遍历直到待排序区间长度为 0。在该过程中有序的区间从左往右扩展，最终整体有序。对于长度为 n 的序列，必须遍历 n 次，因此渐进复杂度固定在 n2，是效率非常差的排序方式。

  • 时间复杂度：𝚹(n2)
  • 空间复杂度：O(1)

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void selectionSort(int[] nums) {
    int min, j;
    for(int i = 0; i < nums.length; i++) {
        min = i; // 每轮遍历设当前索引为本次遍历的最小值索引
        for(j = i + 1; j < nums.length; j++) {
            // 遍历后续元素时，如果发现更小值则记录下该索引值
            if(nums[j] < nums[min]) { // 相等的情况不用交换，否则会破坏排序稳定性
                min = j;
            }
        }
        if(min != i) { // 每次遍历结束后，当最小值索引与当前索引不同则进行交换
            swap(nums, i, min);
        }
    }
}

过程示例：下划线为本轮遍历交换的元素；圆括号为有序区间，余下部分为待排序区间

—|—|—
输入|[7, 5, 2, 3, 4, 5, 5, 7]|操作
第一次遍历结束|[(2), 5, 7, 3, 4, 5, 5, 7]|7与2交换
第二次遍历结束|[(2, 3), 7, 5, 4, 5, 5, 7]|5与3交换
第三次遍历结束|[(2, 3, 4), 5, 7, 5, 5, 7]|7与4交换
第四次遍历结束|[(2, 3, 4, 5), 7, 5, 5, 7]|没有进行交换
第五次遍历结束|[(2, 3, 4, 5, 5), 7, 5, 7]|7与5交换
第六次遍历结束|[(2, 3, 4, 5, 5, 5), 7, 7]|7与5交换
第七次遍历结束|[(2, 3, 4, 5, 5, 5, 7), 7]|没有进行交换
第八次遍历结束|[(2, 3, 4, 5, 5, 5, 7, 7)]|没有进行交换

按选择排序的一种思路，可以有不同的实现。如以上示例是由前向后、升序的方式。也可改为其他版本，如由后往前或降序的方式。

1.2 冒泡排序

在每一轮遍历中，前后元素相互比较，把较大值向后移。每当一轮遍历结束时，位于最后的元素即为遍历元素中的最大值。缩小待排序区间后重复遍历，直到待排序区间长度为0，即为整体有序。

排序的思路和过程都与选择排序相似，因此在优化前，运行效率与选择排序相同为 O(n2)。

优化的原理：由于冒泡排序的过程为相邻两元素之间的比较，为局部有序，因此当一轮遍历下来没有进行过元素交换时，即为整体有序，已无需后续的遍历。选择排序无法用该种方式优化的原因是比较的元素不一定是相邻的两个元素，无法保证局部的有序性。

  • 时间复杂度
    • 优化前：𝚹(n2)
    • 优化后
      • 最优：O(n)，输入序列整体有序；
      • 最差：O(n2)，输入序列为完全倒序；
      • 平均：O(n2)；
  • 空间复杂度：O(1)

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void bubbleSort(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    boolean changed;
    int len = nums.length
    int i, j;
    do {
        // 初始化状态
        changed = false; // 如果没有逆序对则直接退出循环
        len--; // 收缩待排序区
        for(i = 0; i < len; i++) {
            // 前后两元素比较，较大值向后移
            j = i + 1;
            if(nums[i] > nums[j]) { // 只有前者比后者大才需要交换，否则会破坏算法稳定性
                swap(nums, i, j);
                changed = true;
            }
        }
    } while(changed); // 至少遍历一次
}

过程示例：以输入序列 S=[3, 5, 2, 6, 2, 5, 4, 3] 为例，结果中的圆括号为有序部分

遍历次数|交换前|交换的元素|结果
—|—|—
1|[3, 5, 2, 6, 2, 5, 4, 3]|5&2, 6&2, 6&5, 6&4, 6&3|[3, 2, 5, 2, 5, 4, 3, (6)]
2|[3, 2, 5, 2, 5, 4, 3, (6)]|3&2, 5&2, 5&4, 5&3|[2, 3, 2, 5, 4, 3, (5, 6)]
3|[2, 3, 2, 5, 4, 3, (5, 6)]|3&2, 5&4, 5&3|[2, 2, 3, 4, 3, (5, 5, 6)]|
4|[2, 2, 3, 4, 3, (5, 5, 6)]|4&3|[2, 2, 3, 3, (4, 5, 5, 6)]
5|[2, 2, 3, 3, (4, 5, 5, 6)]|无|[(2, 2, 3, 3, 4, 5, 5, 6)]

1.3 归并排序

采取分而治之（Divide and conquer）策略，将输入序列分割成两个子序列并进行排序。

算法的具体过程为

  1. 把输入递归地分割为长度相约的子序列，直到满足排序的条件，即子序列长度为1.
  2. 从分割的路线进行回溯，对相应的两个子序列进行二路归并操作。
  • 时间复杂度：𝚹(nlogn)
  • 空间复杂度：𝚹(n)

根据算法的特性，由于对序列持续进行二分，可见遍历的层数必然为 log2n，且每层需要完成 n 个元素的比较，因此该算法的时间复杂度无论最好、平均或最坏，均为 𝚹(nlogn)，所需的的空间复杂度也必然为 𝚹(n).

归并排序(mergesort)的构思朴实却亦深刻，作为一个算法既古老又仍不失生命力。在排序算法发展的历史上，归并排序具有特殊的地位，它是第一个可以在最坏情况下仍然保持 O(nlogn) 运行时间的确定性排序算法。
时至今日，在计算机早期发展过程中曾经出现的一些难题在更大尺度上再次呈现，归并排序因此重新焕发青春。比如，早期计算机的存储能力有限，以至于高速存储器不能容纳所有的数据，或者只能使用磁带机或卡片之类的顺序存储设备，这些既促进了归并排序的诞生，也为该算法提供了施展的舞台。信息化无处不在的今天，我们再次发现，人类所拥有信息之庞大，不仅迫使更多地将他们存放和组织于分布式平台之上，而且对海量信息的处理也必须首先考虑，如何在跨节点的环境中高效地协同计算。因此在许多新算法和技术的背后，都可以看到归并排序的影子。^1

实例代码: java

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
public void mergeSort(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    int[] tmp = new int[nums.length]; // 需要使用 O(n) 辅助空间
    mSort(nums, 0, nums.length - 1, tmp);
}

private void mSort(int[] nums, int left, int right, int[] tmp) {
    if(left >= right) {
        return;
    }
    int mid = left + (right - left) / 2; // 计算中点索引值，不用 mid=(right+left)/2 的方式以防止上溢
    mSort(nums, left, mid, tmp);
    mSort(nums, mid + 1, right, tmp);
    merge(nums, left, mid, right, tmp); // 二路归并
}

private void merge(int[] nums, int left, int mid, int right, int[] tmp) {
    // 此时实际把 nums 按索引值，从逻辑上分为两个子序列，分别为 s1=[left, mid] 和 s2=[mid+1, right]
    // 由于 s1 和 s2 分别由更小的区间归并得来，因此各自均已有序
    int i = left, j = mid + 1, t = 0;
    while(i <= mid && j <= right) {
        if(nums[i] <= nums[j]) { // 加上判等操作才能保持算法的稳定性
            tmp[t++] = nums[i++];
        } else {
            tmp[t++] = nums[j++];
        }
    }

    // 循环退出时必然已有一个子序列完成遍历，未完成遍历的序列把元素按顺序填入辅助空间即可
    while(i <= mid) {
        tmp[t++] = nums[i++];
    }
    while(j <= right) {
        tmp[t++] = nums[j++];
    }

    // 将辅助空间完成排序的部分回填至原序列
    t = 0;
    while(left <= right) {
        nums[left++] = tmp[t++];
    }
}

算法过程示例：设输入序列 S=[6, 3, 2, 7, 1, 5, 8, 4]

1
2
3
4
5
6
7
8
9
10
11
1. 递归分割子序列:
[6,   3,   2,   7,   1,   5,   8,   4]
[6,   3,   2,   7], [1,   5,   8,   4]
[6,   3], [2,   7], [1,   5], [8,   4]
[6], [3], [2], [7], [1], [5], [8], [4]

2. 相邻子序列进行两路归并, 花括号为本轮进行归并的两个序列
{[6],[3]},{[2],[7]},{[1],[5]},{[8],[4]}
{[3 , 6  , [2 , 7]},{[1 , 5] , [4 , 8]}
{[2 , 3  ,  6 , 7] , [1 , 4  ,  5 , 8]}
 [1 , 2  ,  3 , 4  ,  5 , 6  ,  7 , 8]

1.4 快速排序

快速排序采用分而治之（Divide and conquer）的策略，将序列分割成两个子序列后，递归地对子序列进行排序。根据不同的实现方式，快速排序有不同的空间复杂度，这里仅讨论原地排序版本，即除一些临时变量外，无需申请额外的辅助空间。值得注意的是，快速排序并不是稳定的排序算法，即拥有相同值的多个元素在排序前后，并不能保证相同的相对位置。

算法过程

  1. 定义轴点元素 pivot。
  2. 进行分割（partition）操作：遍历数组，以 pivot 为基准，将较小的元素置于 pivot 左边，较大的元素置于右边。分割操作完成后，将形成以 pivot 为轴点的左右两个子序列，且左子序列的元素均不大于右子序列的元素。
  3. 分别对 pivot 左边与右边两个子序列递归排序。
  4. 递归结束时，子序列长度等于 1 达到最小，原序列整体有序完成排序。

渐进复杂度

  • 时间复杂度
    • 平均：O(nlogn)
    • 最差：O(n2)
  • 空间复杂度
    • O(n)，只需要在每层遍历中申请 𝚹(1) 个临时变量，最好 logn 层，最差 n 层。

示例代码

例1. 随机法，要点：

  1. 随机选取轴点
  2. 分割操作结束时，指针 i 与 j 交汇于轴点处，因此 i == j 时即可结束内部循环
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
public void quickSort(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    qSortA(nums, 0, nums.length - 1);
}

private void qSortA(int[] nums, int left, int right) {
    if(left >= right) {
        return;
    }
    
    Random rand = new Random();
    int bound = right - left + 1; // 包含 right
    int index = left + rand.nextInt(bound); // 随机索引
    swap(nums, left, index);

    // 首元素与随机位置的元素交换，并取出首元素作为轴点，即为随机轴点
    // 轴点会在最后回填，因此此刻可将 nums[i] 视作空位置
    int pivot = nums[left];
    int i = left, j = right;
    while(i < j) { // 该实现的目标是使 i == j，因此循环的条件为 i < j
        // 内循环开始时，先从右往左扫描，遇到小于轴点的元素即停下，并将该元素填入左侧 nums[i] 的空位置
        while(i < j && nums[j] >= pivot) { // 必须加上判等，否则当 pivot、nums[i]、nums[j] 均相等的情况会死循环，如[1,1]
            j--;
        }
        nums[i] = nums[j];

        // 此时 nums[j] 为空，从左往右扫描，遇到大于轴点的元素即停下，并将该元素填入右侧 nums[j] 的空位置
        while(i < j && nums[i] <= pivot) {
            i++;
        }
        nums[j] = nums[i];
    }
    // 内循环结束时，i == j == index(pivot), 原序列从逻辑上分割为 [left, i] 和 [i+1, right] 两个区间
    nums[i] = pivot; // 回填轴点元素
    qSortA(nums, left, i);
    qSortA(nums, i + 1, right);
}

例2. 中文维基版本，要点：

  1. 固定选取中间元素为轴点，并非随机轴点
  2. 分割操作结束时，指针 i 位于 j 右边，且 j + 1 = i, 故循环的结束条件为 i <= j
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
public void quickSort(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    qSortB(nums, 0, nums.length - 1);
}

private void qSortB(int[] nums, int left, int right) {
    if(left >= right) {
        return;
    }
    int pivot = nums[left + (right - left) / 2];
    int i = left, j = right;
    while(i <= j) { // 该实现的目标是使 i 移动到 j 右侧，即 j = i + 1，因此循环的条件为 i <= j
        while(nums[i] < pivot) { // 不能使用等于号，因为无法处理重复元素，如[1,1]
            i++;
        }
        while(nums[j] > pivot) {
            j--;
        }
        if(i < j) {
            swap(nums, i++, j--);
        } else if(i == j) {
            i++;
        }
    }
    // 遍历结束时，S=[left, right] 会被分割为 s1=[left,j] 和 s2=[i,right] 两个子序列，且 s2 的元素均比 s1 的元素更大
    // 注意此实现方式，j 和 i 与 mid=index(pivot) 并不相同
    qSortB(nums, left, j);
    qSortB(nums, i, right);
}

退化的情况

当分割后的两个子序列中，其中一个长度只有 1 ，这种情况一直持续到算法结束，则整个算法的时间复杂度将达到退化为 n2，与选择排序的复杂度相当。

如序列 S=[6, 3, 1, 2, 4, 5]，使用例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
输入: [6, 3, 1, 2, 4, 5]
======
pivot: index=2, value=1
s1区间: [0, 0]
s2区间: [1, 5]
排序后: [1, 3, 6, 2, 4, 5]
======
pivot: index=3, value=2
s1区间: [1, 1]
s2区间: [2, 5]
排序后: [1, 2, 6, 3, 4, 5]
======
pivot: index=3, value=3
s1区间: [2, 2]
s2区间: [3, 5]
排序后: [1, 2, 3, 6, 4, 5]
======
pivot: index=4, value=4
s1区间: [3, 3]
s2区间: [4, 5]
排序后: [1, 2, 3, 4, 6, 5]
======
pivot: index=4, value=6
s1区间: [4, 4]
s2区间: [5, 5]
排序后: [1, 2, 3, 4, 5, 6]
======
输出: [1, 2, 3, 4, 5, 6]

与归并排序比较

由于都应用了分治策略，快速排序与归并排序有许多相似的地方，即都是通过将序列分割成更小的子序列，使每次遍历时问题规模减少，从而减少外层遍历次数。但它们之间也有显著的区别，即归并排序是先分割区间，后比较；而快速排序则是先比较，后分割区间。

对于归并排序而言，由于分割区间的操作与元素无关，所以时间复杂度必然是 𝚹(nlogn)，不存在退化（最差）的情况。

对于快速排序而言，区间的分割依赖作为轴点的元素，存在不确定性，因此存在退化的情况。

总结

最坏情况下 O(n2) 的结论不免令人沮丧。但更为细致的分析与实验统计都一致地显示，在大多数情况下，快速排序算法的平均效率依然可以达到 O(nlogn)；而且较之其他排序算法，其时间复杂度中的常系数更小。
以采用随机法确定轴点的平均效率，经估算为 O(1.386·log2n)
因其良好的平均性能，加上其形象直观和易于实现的特点，快速排序算法自诞生起就一直受到人们的青睐，被集成到 Linux 和 STL 等环境中。^2

1.5 插入排序

简单直观的排序算法，把整个序列分为已排序和待排序两部分，待排序的元素在有序的部分中从后往前扫描，并置于合适的位置。重复该过程，直到有序区间的长度等于原序列的长度（即没有待排序元素），算法结束。整个过程可参考扑克牌的排序过程。该算法为稳定算法。

  • 时间复杂度
    • 最好：O(n), 即输入序列已经有序
    • 平均&最差：O(n2)
  • 空间复杂度：O(1), 无需额外的辅助空间

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void insertionSort(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    int k, j;
    for(int i = 0; i < nums.length; i++) {
        k = nums[i];
        j = i - 1;
        // 为了在合适的位置插入当前元素 k, 位于 k 后面的有序元素都要逐一往后挪
        while(j >= 0 && k < nums[j]) { // 只有小于的情况需要移动，否则会破坏算法稳定性
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = k;
    }
}

1.6 希尔排序

将长度为 n 的输入序列 A 按一定的宽度 w 分割为二维数组，对多维数组的每一列分别进行排序后，缩小宽度 w 再将 A 重新分割为新的二维数组并排序，重复该过程直到 w = 1，此时的二维数组宽度为 1，高度为 n，因此对该列进行排序等同对 A 的全局排序。

宽度 w 又被称为增量（increment），由上述过程可见，排序的过程就是逐渐减少增量进行遍历，因此希尔排序又被称为递减增量排序。

希尔排序为非稳定排序算法。

算法过程：

  1. 取一个增量序列： H=[w1=1, w2, …, wk-1, wk]。其中增量 w 必须合法，故最大增量 wk 不能大于数组长度 n.
  2. 选择增量 wi，i 从 k 递减到 1。
  3. 按增量 w 将输入序列等效划分为相应宽度的二维数组，并对每一列分别排序

第三点中，对每一列排序的算法一般为插入排序，因为随着增量的减小，序列整体越来越趋近于有序，而插入排序对于有序输入的效率比较理想。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void shellSort(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    int incr = nums.length / 2;
    int i, j, k;
    while(incr >= 1) { // H=[1, 2, 4, ..., n/2]
        for(i = 0; i < nums.length; i++) {
            k = nums[i];
            j = i - incr;
            while(j >= 0 && k < nums[j]) {
                nums[j + incr] = nums[j];
                j -= incr;
            }
            nums[j + incr] = k;
        }
        incr /= 2;
    }
}

影响希尔排序性能的关键在于增量序列的设计。示例中的增长序列 H=[1,2,…,n/2] 由算法设计者 Donald Shell 提出，但由于除了最终的增量 1 以外，其他增量元素均为 2 的倍数，即在按增量排序的过程中，原序列的元素按原来的秩分成了偶数和奇数两个子序列各自排序，只有在增量为 1 时，这两个子序列的元素才有机会进行交互，因此在最坏情况下退化为普通的插入排序的效率，即 O(n2).

不同增长序列的效率对比：

序列名称 增长序列 最坏复杂度
Shell n/2i O(n2)
PS 2k-1 O(n3/2)
Sedgewick 2i3j O(nlog2n)

1.7 堆排序

利用完全二叉堆的堆序性，即父节点不小于子节点（最大堆），对输入序列进行排序的算法。

算法过程分两步：

  1. 建堆：从最后一个元素的父节点开始，调整节点使之满足堆序性，直到根节点为止，完成建堆操作。
  2. 排序：交换并进行最大堆调整
    • 原序列分为两部分：完全二叉堆（待排序）和已排序部分
    • 将堆的首元素移至已排序部分的顶部，并对堆进行调整，以维持堆序性

复杂度：

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(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
35
36
37
38
39
40
41
42
43
44
public void heapSort(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    
    int last = nums.length - 1; // 堆中最后一个元素
    int begin = (last - 1) / 2; // 最后一个元素的父节点

    // 建堆
    for(int i = begin; i >= 0; i--) {
        maxHeapify(nums, i, last);
    }
    
    // 堆的首元素，即数组索引为0的元素，即当前堆的最大值，反复移至有序区间的首位，并维持堆序性
    for(int i = last; i > 0; i--) {
        swap(nums, 0, i);
        maxHeapify(nums, 0, i - 1);
    }
    
}

/**
 * @param nums 目标数组
 * @param i 堆顶的索引值
 * @param last 堆中最后一个节点的索引值
 */
private void maxHeapify(int[] nums, int i, int last) {
    int left, right, max;
    boolean next;
    do {
        next = false;
        left = 2 * i + 1; // 根据当前节点索引，计算左子节点的索引
        if(left > last) return; // 左子节点索引值非法，即可返回
        
        right = left + 1;
        max = left;
        if(right <= last && nums[right] > nums[left]) max = right; // 右子节点索引合法且值大于左节点，则与右子节点交换
        if(nums[i] < nums[max]) { // 堆序性验证
            swap(nums, i, max);
            i = max;
            next = true;
        }
    } while(next);
}

2. 非比较排序

非比较排序均可视为桶排序的某一特例，也即散列表的实际应用。通过散列表对元素的出现次数进行统计，并由此得知元素对应原序列的相对位置。非比较排序的实质是用空间（散列表）换取效率，由于无需进行元素之间的比较，因此可突破比较排序的性能下限 Ω(nlogn)，当输入序列的长度 n 远大于散列表的规模 M 时，最优复杂度达到 O(n).

非比较排序均为稳定排序。

2.1 桶排序

将原序列的最小值、最大值横跨的总区间，按同等宽度划分为一定数量的小区间，这些小区间即为桶（bucket）。遍历序列将元素逐一归入其所属的桶。对每个桶内的元素分别进行排序，如递归使用桶排序或其他排序算法。当所有桶均完成排序时，即可完成排序。

影响桶排序性能的主要因素为桶的区间间隔和每个桶内部的排序算法。当只有一个桶的时候，算法整体退化为普通的排序；对整数排序时，如果每个桶的区间为 1，即为计数排序，复杂度为 O(n), 同时消耗大量空间。桶排序的效率是一个空间与效率之间权衡问题。

最差时间复杂度：O(n2)
平均时间复杂度：O(n + n2/k + k)，k 为桶的个数。分别为找出元素范围和初始化桶、每个桶各自排序的时间、最后遍历的时间。可见当桶数 k 分别为 1 或 n 时对应最差与最好的情况，其代价是空间复杂度的增加。

示例代码：桶内部使用计数排序

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
public void bucketSort(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    int max = nums[0], min = max, i = 1;
    for(; i < nums.length; i++) {
        if(nums[i] < min) {
            min = nums[i];
        }
        if(nums[i] > max) {
            max = nums[i];
        }
    }
    
    int bucketSpan = 10; // 设每个桶的大小为10
    int range = max - min; // 待排序元素的区间
    if(range <= bucketSpan) {
        // 待排序的范围较小、不足一个桶时有多种选择：插入排序或计数排序
        // insertionSort(nums);
        countingSort(nums);
        return;
    }
    
    int bucketCount = range / bucketSpan + 1; // 必须加一，如[0,11]
    List<List<Integer>> bucketList = new ArrayList<>(bucketCount);
    for(i = 0; i < bucketCount; i++) {
        bucketList.add(new ArrayList<>());
    }
    List<Integer> bucket;
    int index, n;
    for(i = 0; i < nums.length; i++) {
        n = nums[i];
        index = (n - min) / bucketSpan;
        bucket = bucketList.get(index);
        bucket.add(Integer.valueOf(n));
    }
    index = 0;
    for(i = 0; i < bucketCount; i++) {
        bucket = bucketList.get(i);
        if(bucket.isEmpty()) {
            continue;
        }
        insertionSort(bucket);
        for(Integer n : bucket) {
            nums[index++] = n.intValue();
        }
    }
}

2.2 计数排序

统计每个元素出现的次数，再从小到大地遍历一次即可完成排序。

示例代码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
35
36
37
38
39
public void countingSortA(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    
    // 遍历数组，找出最小、最大值，确认统计数组 count 的区间
    int max = nums[0], min = max, i = 1;
    for(int n : nums) {
        if(n > max) {
            max = n;
        }
        if(n < min) {
            min = n;
        }
    }
    int[] count = new int[max - min + 1];

    // 再次遍历数组，统计各个元素的出现次数
    for(i = 0; i < nums.length; i++) {
        count[nums[i] - min]++;
    }

    // 对各元素出现的次数求积分
    for(i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    int[] tmp = new int[nums.length]; // 此实现方式需要一个长度为n的临时数组
    int index;
    for(i = nums.length - 1; i >= 0; i--) { // 从原数组的最后一个元素开始，反向填入临时数组
        index = --count[nums[i] - min];
        tmp[index] = nums[i];
    }

    // 回填至原数组
    for(i = 0; i < nums.length; i++) {
        nums[i] = tmp[i];
    }
}

示例代码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
public void countingSortB(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    
    // 遍历数组，找出最小、最大值，确认统计数组 count 的区间
    int max = nums[0], min = max, i = 1;
    for(int n : nums) {
        if(n > max) {
            max = n;
        }
        if(n < min) {
            min = n;
        }
    }
    int[] count = new int[max - min + 1];

    // 再次遍历数组，统计各个元素的出现次数
    for(i = 0; i < nums.length; i++) {
        count[nums[i] - min]++;
    }
    
    // 数组 count 的实质是"原序列中的每个元素的值（i + min）出现的次数（count[i]）
    int tmp, index = 0;
    for(i = 0; i < count.length; i++) {
        if((tmp = count[i]) == 0) continue;
        while(tmp-- > 0) {
            nums[index++] = i + min;
        }
    }
}

2.3 基数排序

将整数按数位切分并对各数位分别排序。排序方式按排序的方向分为 LSD（Least significant digit）, 即从右到左（由低位到高位），以及 MSD(Most significant digit), 即从左到右（由高位到低位）。

  • 时间复杂度：O(n·k), n为输入序列的规模，k为序列最大值的位数
  • 空间复杂度：O(n)
  • 稳定的排序算法

示例代码：LSD

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
public void radixSort(int[] nums) {
    if(nums == null || nums.length <= 1) {
        return;
    }
    
    // 获取序列最大值的位数
    int max = nums[0];
    for(int n : nums) {
        if(n > max) {
            max = n;
        }
    }
    int digit = 1;
    while(max >= 10) { // 注意必须判等
        digit++;
        max /= 10;
    }

    int[] count = new int[10]; // 待排序的对象为十进制
    int[] tmp = new int[nums.length]; // 辅助空间
    int i, k;
    int radix = 1;
    for(int j = 0; j < digit; j++) {
        // 清空统计表
        for(i = 0; i < count.length; i++) {
            count[i] = 0;
        }

        // 统计目标位数的数量
        for(i = 0; i < nums.length; i++) {
            k = (nums[i] / radix) % 10;
            count[k]++;
        }
        for(i = 1; i < count.length; i++) {
            count[i] += count[i - 1]; // 计算积分
        }

        // 反向填充以保持稳定性
        for(i = nums.length - 1; i >= 0; i--) {
            k = (nums[i] / radix) % 10;
            tmp[--count[k]] = nums[i];
        }
        for(i = 0; i < nums.length; i++) {
            nums[i] = tmp[i]; // 回填至原数组
        }
        radix *= 10; // 基数指针向高位移动
    }
}

3. 引用