排序算法总结

一、概念回顾

稳定性

排序算法的稳定性是指：同样大小的元素在排序之后不会改变原始的相对次序。

  • 稳定性对基础类型对象来说毫无意义
  • 稳定性对非基础类型对象有意义，可以保留之前的相对次序

1. 比较排序（基于元素两两比较，时间复杂度下界 O(n log n)）

1. 冒泡排序

  • 核心思想：重复遍历数组，依次比较相邻元素，若顺序错误则交换。每一轮把当前未排序部分的最大值”冒泡”到末尾。
  • 稳定性：稳定

2. 选择排序

  • 核心思想：将数组分为已排序和未排序两部分。每一轮从未排序部分中选出最小元素，与未排序部分的首元素交换位置。
  • 稳定性：不稳定

3. 插入排序

  • 核心思想：将数组分为已排序和未排序两部分。每一轮将未排序部分的第一个元素，插入到已排序部分的正确位置。
  • 稳定性：稳定

4. 希尔排序

  • 核心思想：插入排序的改进版。先将数组按间隔（gap）分组，对每组分别进行插入排序；逐步缩小间隔，最终间隔为 1 时完成全局插入排序。
  • 稳定性：不稳定

5. 归并排序

  • 核心思想：分治思想。将数组递归地对半拆分，直到每个子数组只有一个元素；再将两个有序子数组合并成一个更大的有序数组。
  • 稳定性：稳定

6. 快速排序

  • 核心思想：分治思想。选取一个基准（pivot）元素，将数组划分为小于基准、等于基准、大于基准三部分；对左右两部分递归执行相同操作。
  • 稳定性：不稳定

7. 堆排序

  • 核心思想：利用完全二叉堆结构。先将数组构建成最大堆，然后不断将堆顶（最大值）与末尾元素交换，缩小堆的范围并重新调整为最大堆。
  • 稳定性：不稳定

2. 非比较排序（不做两两比较，时间复杂度可突破 O(n log n)）

1. 计数排序

  • 核心思想：遍历数组统计每个元素出现的次数，利用数组下标（天然有序性）直接算出每个元素在结果数组中的位置。
  • 适用前提：元素是整数且取值范围在可接受范围内
  • 稳定性：稳定

2. 桶排序

  • 核心思想：将数组元素按值的范围分配到若干个”桶”中；对每个桶内部分别排序（可使用任意排序算法）；最后依次将各桶的元素取出拼接。
  • 稳定性：取决于桶内排序算法，通常稳定

3. 基数排序

  • 核心思想：多轮按”位”排序。从低位到高位（或高位到低位），每一轮基于当前位的值将元素分配到 0~9 的桶中，再依次取出形成新序列；重复直至所有位处理完毕。
  • 稳定性：稳定（要求每一轮使用稳定的桶内分配方式）

3. 常见排序算法对比总结

排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(1) 稳定
选择排序 O(n²) O(n²) O(1) 不稳定
插入排序 O(n²) O(n²) O(1) 稳定
希尔排序 O(n^1.3) O(n²) O(1) 不稳定
归并排序 O(n log n) O(n log n) O(n) 稳定
快速排序 O(n log n) O(n²) O(log n) 不稳定
堆排序 O(n log n) O(n log n) O(1) 不稳定
计数排序 O(n + k) O(n + k) O(n + k) 稳定
桶排序 O(n + k) O(n²) O(n + k) 视情况
基数排序 O(d × (n + k)) O(d × (n + k)) O(n + k) 稳定

注：n 为元素数量，k 为取值范围大小，d 为最大位数

4. Java 中常见集合的排序方式

默认排序方向

  • 所有内置排序方法默认都是升序（从小到大）
  • 降序可通过 Comparator.reverseOrder() 或自定义比较器实现
  • 基本类型数组没有直接降序方法，需转为包装类型数组或手动反转

数组排序 Arrays.sort()

  • 基本类型数组（int[]、long[] 等）：底层使用 DualPivotQuicksort（双轴快速排序），不稳定，默认升序
  • 对象数组（Integer[]、String[] 等）：底层使用 TimSort（归并排序 + 插入排序的混合算法），稳定，默认升序
  • 可传入 Comparator 自定义排序规则

List 排序 Collections.sort() / list.sort()

  • Collections.sort(list)：本质调用 list.sort(null)，默认升序
  • list.sort(comparator)（Java 8+）：底层将 List 转为数组后调用 Arrays.sort()，即 TimSort，稳定
  • 可传入 Comparator 自定义排序规则

Stream 排序 stream.sorted()（Java 8+）

  • stream.sorted()：按元素自然顺序（升序）排序（元素需实现 Comparable）
  • stream.sorted(comparator)：传入 Comparator 自定义排序规则
  • 底层仍是 TimSort，稳定
  • 排序后需通过 collect() 收集为新集合，不影响原集合

自动有序集合

集合类 底层结构 默认排序方向 排序方式
TreeSet 红黑树 升序 元素实现 Comparable 或构造时传入 Comparator
TreeMap 红黑树 升序 Key 实现 Comparable 或构造时传入 Comparator
PriorityQueue 二叉堆 升序（小顶堆） 默认自然顺序，可传入 Comparator
  • 插入元素时自动维护有序性，无需额外调用排序方法

Comparable vs Comparator

对比项 Comparable Comparator
所属包 java.lang java.util
方法 compareTo(T o) compare(T o1, T o2)
使用方式 元素内部实现（自然排序） 外部传入（定制排序）
排序调用 Collections.sort(list) / list.sort(null) list.sort(comparator)
能否多种排序 只能有一种（类内部定义） 可以有多种（外部灵活传入）

Comparator 构造方式

以下以 Person(name, age) 类为例，按年龄升序排序：

方式一：匿名内部类（Java 7 及以前）

1
2
3
4
5
6
list.sort(new Comparator<Person>() {
    @Override
    public int compare(Person o1, Person o2) {
        return o1.age - o2.age;
    }
});

方式二：Lambda 表达式（Java 8+）

1
list.sort((o1, o2) -> o1.age - o2.age);

方式三：方法引用（Java 8+，需类有对应方法）

1
list.sort(Person::compareByAge);

方式四：Comparator 静态工厂方法（Java 8+，推荐）

1
2
3
4
list.sort(Comparator.comparingInt(p -> p.age));           // 按 age 升序
list.sort(Comparator.comparingInt((Person p) -> p.age).reversed()); // 按 age 降序
list.sort(Comparator.comparing((Person p) -> p.name)      // 先按 name 升序
                     .thenComparingInt(p -> p.age));      // 再按 age 升序

降序排序的三种写法

1
2
3
list.sort(Comparator.reverseOrder());          // 方式一：reverseOrder()
list.sort(Comparator.naturalOrder().reversed()); // 方式二：naturalOrder().reversed()
list.sort((o1, o2) -> o2.age - o1.age);        // 方式三：交换 o1 o2 位置

关键设计总结

场景 使用算法 稳定性 默认方向
Arrays.sort(基本类型[]) DualPivotQuicksort 不稳定 升序
Arrays.sort(对象[]) / List.sort() TimSort 稳定 升序
Stream.sorted() TimSort 稳定 升序

为什么基本类型和对象类型用不同算法？
基本类型不需要稳定性（值相等无意义），双轴快排平均性能更优、空间复杂度 O(1)。
对象类型需要稳定性（保留相等元素的相对顺序），且 TimSort 在部分有序场景下性能更优。

5. 算法题中何时使用集合排序？

一句话原则

当排序能让问题的约束条件变得简单时，先排序！ 排序是算法题中性价比最高的预处理手段之一，一次 O(n log n) 的排序，可能换来后续 O(n) 就能解决核心问题。

✅ 应该使用排序的典型场景

1. 去重问题

排序后相同元素相邻，通过 nums[i] != nums[i-1] 即可跳过重复，避免了 Set 的额外空间开销。

典型题：LeetCode 31.下一个排列、LeetCode 217.存在重复元素

2. 双指针 / 滑动窗口前提

双指针法的核心前提就是数组有序，否则指针移动没有方向依据。排序 + 双指针是解决”找两数/三数组合”类问题的黄金组合。

典型题：LeetCode 15.三数之和、LeetCode 11.盛最多水的容器、LeetCode 16.最接近的三数之和

3. 区间问题

按左端点或右端点排序后，区间关系变得有规律，只需一次遍历即可完成合并、插入或判断重叠。

典型题：LeetCode 56.合并区间、LeetCode 57.插入区间、LeetCode 435.无重叠区间

4. 分组 / 聚合处理

排序后相同或相似的元素聚集在一起，可以一边遍历一边统计或处理，不需要额外的 HashMap。

典型题：LeetCode 49.字母异位词分组、LeetCode 128.最长连续序列

5. 找中位数

排序后直接通过下标访问即可。但如果只需要 Top-K 不需要全排序，优先用堆（O(n log k)）更优。

典型题：LeetCode 4.寻找两个正序数组的中位数

6. 贪心策略前置

很多贪心算法需要先排序才能确定”贪心顺序”——按什么顺序处理局部最优。

典型题：LeetCode 455.分发饼干、LeetCode 435.无重叠区间、LeetCode 1005.K次取反后最大化的数组和

❌ 不应该全排序的场景

场景 原因 更优方案
只需要 Top-K 而不需要全排序 全排序 O(n log n) 做了无用功 堆（优先队列），O(n log k)
要求 O(n) 线性时间 排序下界 O(n log n) 不满足 计数排序、桶排序、快速选择
流式数据（数据量极大） 无法一次性全部加载到内存 外部排序 / 堆维护 Top-K
两数之和（返回下标） 排序会打乱原始下标 HashMap 空间换时间，O(n)

Java 算法题实战技巧

int[] 降序排序

基本类型数组没有直接降序方法，常见做法：

1
2
3
4
5
6
7
8
9
// 方式一：转为 Integer[]（会装箱，大数据量有性能损耗）
Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
Arrays.sort(arr, Collections.reverseOrder());

// 方式二：升序排完手动反转（推荐，原地修改）
Arrays.sort(nums);
for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
    int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
}

对 List 排序

1
2
3
Collections.sort(list);                           // 升序
Collections.sort(list, Collections.reverseOrder()); // 降序
list.sort(Comparator.reverseOrder());              // Java 8+ 写法

自定义对象排序

1
2
// 按身高升序，身高相同按体重降序（LeetCode 406.根据身高重建队列）
people.sort((a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

Comparator 中避免整数溢出

直接用 a - b 比较可能导致 int 溢出（如 Integer.MAX_VALUE - (-1)），推荐：

1
2
3
4
5
// 安全写法一：用 Integer.compare
list.sort((a, b) -> Integer.compare(a.age, b.age));

// 安全写法二：用 Comparator 静态工厂（推荐）
list.sort(Comparator.comparingInt(p -> p.age));