本文对和 排序 有关的常见算法基础题思路进行分析和总结，并以 Java 为例，适当指出需要注意的编程细节

记号约定：按升序排，数组 A 大小记为 n

冒泡排序

思路：

  1. 依次交换相邻两个数，使大的在后，每趟在末尾确定一个最大值
  2. 外循环 n 趟依次确定最大值，次大值，….，确定排序

注意：

  • 内循环的相邻元素下标写法和内循环下标起始

计数排序

思路：

  1. 找到数组最大值 max 和最小值 min，以差值(max-min)作为桶数组的长度
  2. 遍历数组入桶计数
  3. 遍历桶，写回原数组

注意：

  • 入桶时，对应桶下标为 A[i]-min
  • 写回数组时下标依次递增， A[i++] = j + min;

堆排序

思路：

  1. 初始化成大根堆
  2. 将堆顶元素(即最大值)和末尾元素交换，并下沉该换上来的末尾元素
  3. 将堆的长度减1，重复第二步

注意：

  • 下标从 1 开始较方便，子节点下标就对应为 2*i 和 2*i+1
  • 初始化时从一半位置依次递减下标使用下沉操作
  • 下沉操作挑子节点中较大值与父节点交换，直至 满足父节点大于两个子节点
1
2
3
4
5
6
7
8
9
private static void sink(Comparable[] pq, int k, int N) {
    while (2 * k <= N) {
        int j = 2 * k;
        if (j < N && less(pq, j, j + 1)) j++;
        if (!less(pq, k, j)) break;
        exch(pq, k, j);
        k = j;
    }
}

插入排序

思路：

  1. 将数组前一部作为一个“有序数组”，该“有序数组”长度逐步扩大
  2. 每趟循环将当前元素依次和前一个元素比对，插入到“有序数组”中的相应位置

注意：

  • 注意下标起始，外循环 n-1 次，内循环下标递减
  • 插入效果可以使用两两相邻交换来实现

归并排序

这里使用非递归的 bottom-up 的实现方式

思路：

  1. 每次合并的单位长度为 size ， size 依次取 1，2，… ，直到 size>=n
  2. 对于每个 size，从前往后按照步长为 2*size 依次合并
  3. 归并的内部逻辑是，先从原数组拷贝一份到辅助数组，再按序填回原数组

注意：

  • 需要分配一个辅助数组用于合并
  • 每次合并需要传递五个参数：原数组，辅助数组以及合并的起止下标和中点下标
  • 归并的截止下标需要取小避免越界 Math.min(n, i + 2 * size);
  • 内循环的终止条件是 i + size < n，步长是 2*size

快速排序

思路：

  1. shuffle(可选):先把原数组随机打乱
  2. partition:随机选一个数作为参考值，比其小的放左边，大的放右边
  3. 递归地排序上述结果的左半部分和右半部分

注意：

  • 一般参考值就取第一个元素，对后面的元素进行划分
  • 划分时注意循环终止条件，大于小于带不带等号，都要注意

选择排序

思路：

  1. 每次遍历一趟挑取最小元素，将该元素与起始元素交换
  2. 起始元素下标依次为0，1，…，n-1

注意：

  • 比较的是值，记录的是下标

基数排序

以元素小于等于 2000 为例，位数为 4

思路：

  1. 准备一个 10*n 的桶数组(10 代表 0～9 的数字，n代表某个数字下最多容纳的个数，这里为原数组大小 n)
  2. 由低位到高位，将3，4步执行位数次循环
  3. 遍历数组，按照某一位的数字将元素入桶
  4. 从大数字到小数字，依次将桶内元素从后往前写回原数组

注意：

  • 需要两个辅助数组，一个用于存放元素，一个用于记录每个数字桶的元素个数
  • 入桶时一定要先低位，再高位，这样才能保证最高位影响最大
  • 取桶内元素返到数组时一定要倒着取，这样才能保证之前排序的顺序

希尔排序

思路：

  1. 对数组进行步长为1，4，13,…,（3*前一个步长+1）的插入排序，步长由大到小

注意：

  • 最外层先计算好最大步长，每次除以三
  • 插入排序的外层起始下标为 h，每次下标递增 1
  • 插入排序的内层递减步长为 h

合并两个有序数组

题目:Merge

思路：

  1. 从两个数组末端取值，每次取较大者，从后往前填空
  2. 当数组 B 的元素分配完时结束

判断数组中是否有重复值

题目见 Checker

时间最快 O(n)，遍历一遍使用哈希表即可。

若要保证额外空间复杂度为O(1)，则使用排序，再遍历，看相邻是否有重值

行列排序矩阵找值

题目见 lectures.sort.Finder

思路：由于行列分别有序（升序），从矩阵右上/左下开始找均可在 O(行数＋列数) 时间复杂度找到。以右上为例，当前数大于待找数，则同行往前找，否则同列往下找。

排序后相邻两数的最大差值

题目见 Gap

直接排序做最快是 O(n*log n)的时间复杂度，这里讨论的是 O(n) 的时间复杂度

思路：来源于桶排序

  1. 找到数组的最大值和最小值，准备 n+1 个桶（n为数组元素个数）
  2. 最大值放在第 n+1 个桶中，其它桶以 (max-min)/n 的间隔均匀分布（所以最小值一定落在第一个第一个桶中）
  3. 将数组中元素依次落入桶中，找出空桶前的桶内元素的最大值和空桶后的桶内元素的最小值，求差即可

注意：

  • n+1 个桶放 n 个元素，一定会有空桶，同一桶内元素的差值一定小于桶区间，所以来自不同桶之间的相邻元素差值更大。
  • 分别使用 hasNum[n+1], maxs[n+1], mins[n+1] 来表示桶是否为空以及桶内元素的最大最小值

计算需要排序的最短子数组的长度

题目见 Subsequence

思路：

  1. 从左到右遍历，记录元素值比该元素左边的最大值要小的最右下标 right
  2. 从右往左遍历，记录元素值比该元素右边的最小值要大的最左下标 left
  3. 如果 right > left，则需要排序的长度为 right-left +1

注意：

  • right 的初始值为 0，left 的初始值为 n-1
  • 遍历的每一步，要么满足递增（减），更新最大（小）值；要么更新下标

荷兰旗问题

题目见 ThreeColor

思路一：计数排序，先入桶再出桶即可。

思路二：类似三路快排，下标[0,lo]，(lo,mid]，(mid,n-1] 之间的元素各表示一个数值区间

注意：

  • lo, hi, mid 的起始值要注意
  • 交换时的增减顺序要注意，参考示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
int lo = -1;
int hi = n;
int mid = 0;
while (mid < hi) {
    if (A[mid] < 1) {
        swap(A, ++lo, mid++);
    } else if (A[mid] > 1) {
        swap(A, --hi, mid);
    } else {
        mid++;
    }

}