算法：排序

Weekly Post

四月的第四周，来整理排序算法，本篇文章基于 CS-Notes 的《算法-排序》，那篇文章的代码写得非常通用，使用泛型并继承 Comparable 接口来进行，本篇只针对数字做排序，重点放在算法而不是兼容上。

算法写完这一篇就暂时不写了，每天细水长流做一做题，多积累一点算法底蕴再抽空回来写。

总结写在最前面，方便查看。本篇文章涉及七种排序算法（以及几种亚种），时间和空间复杂度的对比汇总如下：

算法 稳定性 时间复杂度 空间复杂度
选择排序 × N² 1
冒泡排序 √ N² 1
插入排序 √ N ~ N² 1
希尔排序 × N 的若干倍乘于递增序列的长度 1
归并排序 √ NlogN N
快速排序 × NlogN logN
堆排序 × NlogN 1

P.S. 稳定性的意思是，相同项排序前后不能调换位置，例如 1、[2]、(2)、3 排序后不能变成 1、(2)、[2]、3。

选择排序

遍历最小的交换

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] selectSort(int[] nums) {
    int n = nums.length;
    // 从第一个开始，执行到倒数第二个
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[minIndex] > nums[j]) {
                minIndex = j;
            }
        }
        swap(nums, i, minIndex);
    }
    return nums;
}

冒泡排序

相邻比较，最小的升到最前面

冒泡排序（这个 gif 是反过来的，最大的挪到最后）

1
2
3
4
5
6
7
8
9
10
11
12
public int[] bubbleSort(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        // 从倒数第一个开始，执行到第i+1个
        for (int j = n - 1; j > i; j--) {
            if (nums[j] < nums[j - 1]) {
                swap(nums, j, j - 1);
            }
        }
    }
    return nums;
}

插入排序

每个数字一路往前交换，等效为插入

插入排序

1
2
3
4
5
6
7
8
9
10
public int[] insertSort(int[] nums) {
    int n = nums.length;
    for (int i = 1; i < n; i++) {
        // 从第二个开始，每个数字一路往前交换，直到前面比它小为止
        for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
            swap(nums, j, j - 1);
        }
    }
    return nums;
}

希尔排序

改进的插入排序，设置了间隔

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] shellSort(int[] nums) {
    int n = nums.length;

    // 间隔数量，初始值为[1, 4, 13, 40……]数列中最接近n的那个
    int h = 1;
    while (h < n / 3) {
        h = 3 * h + 1;
    }

    while (h >= 1) {
        for (int i = h; i < n; i++) {
            // 从第h+1个开始，每个数字一路往前交换（间隔为h），直到前面比它小为止
            for (int j = i; j >= h && nums[j] < nums[j - h]; j--) {
                swap(nums, j, j - h);
            }
        }
        h /= 3;
    }

    return nums;
}

归并排序

将数组分成两个子数组，分别排序，再合并

归并排序

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
private int[] helpArray;

public int[] mergeSort(int[] nums) {
    helpArray = new int[nums.length];
    return doMergeSort(nums, 0, nums.length - 1);
}

private int[] doMergeSort(int[] nums, int l, int h) {
    if (l < h) {
        int mid = l + (h - l) / 2;
        doMergeSort(nums, l, mid);
        doMergeSort(nums, mid + 1, h);
        merge(nums, l, h, mid);
    }
    return nums;
}

private void merge(int[] nums, int l, int h, int mid) {
    // 技巧：用辅助数组
    System.arraycopy(nums, l, helpArray, l, h - l + 1);
    int i = l, j = mid + 1, curr = l;
    while (curr <= h) {
        if (i <= mid && j <= h) {
            if (helpArray[i] <= helpArray[j]) {
                nums[curr++] = helpArray[i++];
            } else {
                nums[curr++] = helpArray[j++];
            }
        } else if (i <= mid) {
            nums[curr++] = helpArray[i++];
        } else {
            nums[curr++] = helpArray[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 int[] quickSort(int[] nums) {
    doQuickSort(nums, 0, nums.length - 1);
    return nums;
}

private void doQuickSort(int[] nums, int l, int h) {
    if (l < h) {
        // mid左边都是小于等于它的数字，右边都是大于等于它的数字
        int mid = partition(nums, l, h);
        doQuickSort(nums, l, mid - 1);
        doQuickSort(nums, mid + 1, h);
    }
}

private int partition(int[] nums, int l, int h) {
    // 取第一个数作为比较基础
    int target = nums[l];
    int i = l, j = h + 1;
    while (i < j) {
        // 左 -> 右  找更大的数
        while (++i != h && nums[i] < target) ;
        // 左 <- 右  找更小的数
        while (--j != l && nums[j] > target) ;
        if (i < j) {
            swap(nums, i, j);
        }
    }
    // 此时 i>j 要跟坐标小的交换，并返回这个小坐标
    swap(nums, l, j);
    return j;
}

堆排序

数组中坐标 2k 和 2k+1 的数字，是 k 的叶子

堆排序

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[] heapSort(int[] nums) {
    int n = nums.length - 1;
    for (int i = n / 2; i >= 1; i--) {
        // 从倒数第二层预排一次，大顶堆
        sink(nums, i, n);
    }

    while (n > 1) {
        // 最大的数交换到数组尾，将交换来的数再大顶堆下沉
        swap(nums, 1, n--);
        sink(nums, 1, n);
    }
    return nums;
}

private void sink(int[] nums, int parent, int n) {
    while (parent * 2 <= n) {
        int son = parent * 2;
        if (son < n && nums[son] < nums[son + 1]) {
            son++;
        }
        // 父亲一定比孩子大，排到某层符合就不用排了
        if (nums[parent] >= nums[son]) {
            break;
        }
        swap(nums, parent, son);
        parent = son;
    }
}

整理完算法，顺便学习一下 Java 默认提供的一些排序 API。

Comparable & Comparator

Java 排序相关的内容，最常用到的就是 Comparable 和 Comparator，这两个都是接口类。

Java 对容器、数组进行排序时调用的 sort() 方法（例如 Collections.sort(list)、Arrays.sort(array)）时，要不然让容器内的元素实现 Comparable 接口，要不然自己重写 Comparator 接口说明排序逻辑。知乎文章《Java 中的排序》对此解释得清晰明了：

  • 如果一个类实现了 Comparable 接口，那么它“天生”就是可以借助 Collections、Arrays、SortedMap、SortedSet 等类来进行排序。

  • 但是，如果一个类没有实现 Comparable 接口，却也想利用 Collections、Arrays、SortedMap、SortedSet 等来进行排序，就可以通过指定一个自定义的 Comparator 来实现。

如果觉得两个接口容易记混，可以思忖一下名字，一个叫做 Comparable（可以比较），表明实现该接口的类是可以进行比较的，另一个叫做 Comparator（比较器），表明该接口是用来确定比较大小逻辑的。

具体使用逻辑懒得写了，看看之后有没有写的动力吧……