排序算法笔记

排序算法是最基础的算法, 在算法学科中有着很高的地位
排序算法的目的是将一系列可比较元素按照某种规则进行排序. 其中需要重点关注的是不同算法的时间复杂度和空间复杂度, 以及使用场景

公共API

程序中将有以下公共 API

方法签名 注释
boolean less(Comparable v, Comparable w) 当且仅当 v 小于 w 时, 返回 true
void exchange(Comparable<?>[] a, int i, int j) 交换 a 数组中索引为 i 和 j 位置的元素

Comparable 接口的全类名为 java.lang.Comparable

算法实现

下文中的 N 无特殊说明时代表输入数组的长度

选择排序

将数组划分为有序区和无序区, 重复按序遍历无序区元素, 每次将最小的元素放在有序区末尾, 直到无序区没有元素

分析

选择排序算法需要经过 N * (N - 1) / 2 (~ N^2 / 2) 次元素比较, 与 N 次元素交换, 时间复杂度为 O(N^2), 空间复杂度为 O(1)
选择排序算法主要有以下特点:

  • 运行时间和输入无关
  • 与其他算法相比, 元素交换最少
  • 不稳定的排序算法

实现

1
2
3
4
5
6
7
8
9
void selection(Comparable<?>[] a) {
    for (var i = 0; i < a.length; i++) {
        var minIndex = i;
        for (var j = i + 1; j < a.length; j++)
            if (less(a[j], a[minIndex])) minIndex = j;

        exchange(a, i , minIndex);
    }
}

示例

输入 : 
1
[10, 5, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
排序过程 : 
1
2
3
4
5
6
7
8
9
10
11
12
[0, 5, 11, 4, 6, 7, 2, 3, 1, 10, 8, 9]
[0, 1, 11, 4, 6, 7, 2, 3, 5, 10, 8, 9]
[0, 1, 2, 4, 6, 7, 11, 3, 5, 10, 8, 9]
[0, 1, 2, 3, 6, 7, 11, 4, 5, 10, 8, 9]
[0, 1, 2, 3, 4, 7, 11, 6, 5, 10, 8, 9]
[0, 1, 2, 3, 4, 5, 11, 6, 7, 10, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 11, 7, 10, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 11, 10, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
输出 : 
1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

插入排序

将数组划分为有序区和无序区, 重复按序选择无序区元素, 将每次选择的元素放在有序区的合适位置, 直到无序区没有元素

分析

在最好情况下, 插入排序算法需要经过 N - 1 次元素比较, 与 0 次元素交换;
在最坏情况下, 插入排序算法需要经过 ~ N^2 / 2 次元素比较, 与 ~ N^2 / 2 次元素交换;
平均情况下, 插入排序算法需要经过 ~ N^2 / 4 次元素比较, 与 ~ N^2 / 4 次元素交换.
插入排序算法时间复杂度为 O(N^2), 空间复杂度为 O(1).
插入排序算法主要有以下特点:

  • 对已有序的数组效率非常高
  • 稳定的排序算法

实现

1
2
3
4
5
void insertion(Comparable<?>[] a) {
    for (var i = 0; i < a.length; i++)
        for (var j = i; j > 0 && less(a[j], a[j - 1]); j--)
            exchange(a, j , j - 1);
}

插入排序哨兵
可以先将一个最小的元素放在有序区最前面, 这样可以避免边界判断

示例

输入 : 
1
[10, 5, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
排序过程 : 
1
2
3
4
5
6
7
8
9
10
11
12
[10, 5, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
[5, 10, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
[5, 10, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
[4, 5, 10, 11, 6, 7, 2, 3, 1, 0, 8, 9]
[4, 5, 6, 10, 11, 7, 2, 3, 1, 0, 8, 9]
[4, 5, 6, 7, 10, 11, 2, 3, 1, 0, 8, 9]
[2, 4, 5, 6, 7, 10, 11, 3, 1, 0, 8, 9]
[2, 3, 4, 5, 6, 7, 10, 11, 1, 0, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 10, 11, 0, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
输出 : 
1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

希尔排序

希尔排序是基于插入排序的一种排序算法
希尔排序将数组按一定间隔 h 将原数组划分为若干子序列, 每个子序列中索引相同的元素归同一个子数组, 如数组 a, b, c, d, e, f, g, h, i, j, k, l, 当 h = 4 时, 子序列有 a, b, c, d, e, f, g, h, i, j, k, l, 子数组为a, e, i, b, f, j, c, g, k 和 d, h, l. 排序时, 先把每个子数组利用插入排序化为有序数组, 之后减小 h 的值重复操作, 直到 h 的值为 1

分析

希尔排序在插入排序的基础上还权衡了子数组的规模和有序性, 其算法的性能与 h 的选取有很大关系. 在面对大数组时, 希尔排序比选择排序和插入排序优势较大, 但对规模非常大的输入排序不是最优选择. 希尔排序的时间复杂度为 O(N^1.5), 空间复杂度为 O(1)
插入排序算法主要有以下特点:

  • 不稳定的排序算法

实现

1
2
3
4
5
6
7
8
9
10
11
void shell(Comparable<?>[] a) {
    var h = 1;
    while (h < a.length / 3) // 计算初始 h 值
        h = 3 * h + 1;
    while (h >= 1) {
        for (var i = 0; i < a.length; i++)
            for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
                exchange(a, j, j - h);
        h /= 3;
    }
}

示例

输入 : 
1
[10, 5, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
排序过程 : 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
h = 4 [10, 5, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
h = 4 [10, 5, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
h = 4 [10, 5, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
h = 4 [10, 5, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
h = 4 [6, 5, 11, 4, 10, 7, 2, 3, 1, 0, 8, 9]
h = 4 [6, 5, 11, 4, 10, 7, 2, 3, 1, 0, 8, 9]
h = 4 [6, 5, 2, 4, 10, 7, 11, 3, 1, 0, 8, 9]
h = 4 [6, 5, 2, 3, 10, 7, 11, 4, 1, 0, 8, 9]
h = 4 [1, 5, 2, 3, 6, 7, 11, 4, 10, 0, 8, 9]
h = 4 [1, 0, 2, 3, 6, 5, 11, 4, 10, 7, 8, 9]
h = 4 [1, 0, 2, 3, 6, 5, 8, 4, 10, 7, 11, 9]
h = 4 [1, 0, 2, 3, 6, 5, 8, 4, 10, 7, 11, 9]
h = 1 [1, 0, 2, 3, 6, 5, 8, 4, 10, 7, 11, 9]
h = 1 [0, 1, 2, 3, 6, 5, 8, 4, 10, 7, 11, 9]
h = 1 [0, 1, 2, 3, 6, 5, 8, 4, 10, 7, 11, 9]
h = 1 [0, 1, 2, 3, 6, 5, 8, 4, 10, 7, 11, 9]
h = 1 [0, 1, 2, 3, 6, 5, 8, 4, 10, 7, 11, 9]
h = 1 [0, 1, 2, 3, 5, 6, 8, 4, 10, 7, 11, 9]
h = 1 [0, 1, 2, 3, 5, 6, 8, 4, 10, 7, 11, 9]
h = 1 [0, 1, 2, 3, 4, 5, 6, 8, 10, 7, 11, 9]
h = 1 [0, 1, 2, 3, 4, 5, 6, 8, 10, 7, 11, 9]
h = 1 [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 9]
h = 1 [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 9]
h = 1 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
输出 : 
1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

归并排序

归并排序的核心是 “组合”, 将数组划分为子数组, 使子数组有序后再把子数组进行合并. 子数组也用同样的方法进行排序, 当子数组中只有一个元素时它本身就是有序的

分析

归并排序发时间复杂度是 O(N * lb N), 空间复杂度是 O(N), 是一种稳定的排序方法
TimSort 排序是归并排序的优化版本, 对归并排序排在已经反向排好序的输入时做了特别优化, 最好情况的时间复杂度为 O(N)
在面对较小输入, 归并排序的大量方法调用可能会使程序效率不如插入排序
对于较大输入可以考虑将归并排序和插入排序结合使用, 当子数组较小时, 使用插入排序将其排序, 再进行归并排序

公共 API

归并排序有不同的实现, 其中将两个有序子数组组合成一个有序数组的方法是共有的, 将这部分抽象为公共 API

方法签名 注释
void merge(Comparable<?>[] a, int low, int mid, int high) 将 a 的子序列 a[low … mid] 和 a[mid + 1 … high] 归并
void mergeSort(Comparable<?>[] a, int type) 归并排序的公共接口, type 为指定使用具体实现
查看 merge 方法的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void merge(Comparable<?>[] a, int low, int mid, int high) {
    var auxLength = mid - low + 1;
    var aux = new Comparable<?>[auxLength];
    System.arraycopy(a, low, aux, 0, auxLength);

    var auxIndex = 0;
    var aIndex = mid + 1;
    for (var k = low; k <= high; k++)
        if (auxIndex >= aux.length) {
            return;
        }
        else if (aIndex > high) {
            System.arraycopy(aux, auxIndex, a, k, aux.length - auxIndex);
            return;
        }
        else if (less(a[aIndex], aux[auxIndex])) {
            a[k] = a[aIndex++];
        }
        else {
            a[k] = aux[auxIndex++];
        }
    
}
查看经过优化的 merge 方法的实现
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
void merge(Comparable<?>[] a, int low, int mid, int high) {
    if (!less(a[mid + 1], a[mid])) return;

    var auxLength = mid - low + 1;
    var aux = new Comparable<?>[auxLength];
    System.arraycopy(a, low, aux, 0, auxLength);


    if (!less(a[low], a[high])) {
        var tempAux = new Comparable<?>[high - mid];
        System.arraycopy(a, mid + 1, tempAux, 0, tempAux.length);

        System.arraycopy(tempAux, 0, a, low, tempAux.length);
        System.arraycopy(aux, 0, a, low + tempAux.length, aux.length);
        return;
    }

    var auxIndex = 0;
    var aIndex = mid + 1;
    for (var k = low; k <= high; k++)
        if (auxIndex >= aux.length) {
            return;
        }
        else if (aIndex > high) {
            System.arraycopy(aux, auxIndex, a, k, aux.length - auxIndex);
            return;
        }
        else if (less(a[aIndex], aux[auxIndex])) {
            a[k] = a[aIndex++];
        }
        else {
            a[k] = aux[auxIndex++];
        }
}
查看 mergeSort 方法的实现
1
2
3
4
5
6
void mergeSort(Comparable<?>[] a, int type) {
    switch (type) {
        case 0 -> upToDownMerge(a, 0, a.length);
        default -> throw new IllegalArgumentException("unknown type");
    }
}

实现

自顶向下归并排序

自顶向下归并排序使用了分治思想

分析

自顶向下归并排序至少需要 0.5 * N * lb N 次比较, 至多 N * lb N 次比较和 6 * N * lb N 次数组访问

实现
1
2
3
4
5
6
7
8
9
10
void upToDownMerge(Comparable<?>[] a, int low, int high) { // type = 0
    if (high < low) return;

    var mid = low + (high - low) / 2;

    upToDownMerge(a, low, mid);
    upToDownMerge(a, mid + 1, high);

    merge(a, low, mid, high);
}
示例
输入 : 
1
[10, 5, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
排序过程 (原始 merge 方法) : 
1
2
3
4
5
6
7
8
9
10
11
12
[5, 10, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
[5, 10, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
[5, 10, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
[5, 10, 11, 4, 6, 7, 2, 3, 1, 0, 8, 9]
[4, 5, 6, 7, 10, 11, 2, 3, 1, 0, 8, 9]
[4, 5, 6, 7, 10, 11, 2, 3, 1, 0, 8, 9]
[4, 5, 6, 7, 10, 11, 1, 2, 3, 0, 8, 9]
[4, 5, 6, 7, 10, 11, 1, 2, 3, 0, 8, 9]
[4, 5, 6, 7, 10, 11, 1, 2, 3, 0, 8, 9]
[4, 5, 6, 7, 10, 11, 0, 1, 2, 3, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
输出 : 
1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
自底向上的归并排序