Java 数组排序一共分成两大类，一类是 JDK 内置现成排序方法，也就是 Arrays 工具类提供的 sort 方法，开发项目优先使用这个，另一类是手写经典排序算法，包含冒泡排序选择排序插入排序快速排序归并排序希尔排序堆排序，面试和学习阶段重点掌握手写实现，内置 sort 底层并不是单一算法，JDK 针对不同数据规模和数据类型，会自动切换优化后的排序算法，基本类型数组底层是双轴快速排序，对象数组底层是 TimSort 也就是归并排序优化版本，很多初学者以为 Java 数组排序只有 Arrays.sort 这一种，其实手写排序是理解排序原理的核心，不同排序算法时间复杂度空间复杂度稳定性差别很大，业务开发优先调用内置 API，笔试面试需要能独立写出冒泡选择插入快速归并这几种 Java 数组排序代码，同时能分析算法优缺点。之所以要学习多种 Java 数组排序方法，是因为没有万能最优排序，小规模数组有序数组近乎有序数组大规模乱序数组，适合的排序算法不一样，理解每种算法的执行逻辑，遇到特殊场景才可以做算法选型。
JDK 内置 Java 数组排序方法
| 方法 | 适用类型 | 底层算法 | 特点 |
|---|---|---|---|
| Arrays.sort() | 基本类型数组 int long double 等 | 双轴快速排序 | 升序，原地排序，速度快 |
| Arrays.sort() | 对象类型数组 Integer String 等 | TimSort | 稳定排序，基于归并优化 |
| Arrays.parallelSort() | 所有数组类型 | 并行排序 | 多核 CPU 并行处理，超大数组性能更好 |
使用要点，Arrays.sort 默认升序，如果想要降序，对象数组可以自定义 Comparator，基本类型数组不能直接传比较器，需要排序之后反转或者转成包装类数组。parallelSort 适合几十万以上超大数组，小数组开启多线程反而有线程开销，性能不如普通 sort。
手写经典 Java 数组排序算法
冒泡排序
核心逻辑，重复遍历数组，相邻两个元素两两比较，如果前面大于后面就交换，每一轮遍历都会把当前未排序区间最大元素像气泡一样上浮到末尾。
特点，稳定排序，时间复杂度最坏 O n 平方，最好 O n，空间复杂度 O 1，适合很小规模数组，缺点就是数据量大的时候非常慢。
执行步骤
1 外层循环控制轮次，一共需要数组长度减 1 轮
2 内层循环相邻元素比较交换，每一轮结束末尾已经排好的元素不再参与比较
3 可以增加标记位优化，如果一轮没有发生任何交换，代表数组已经有序，直接提前退出循环
选择排序
核心逻辑，每一轮遍历，在未排序区间找到最小值下标，一轮结束之后把最小值和未排序区间第一个位置交换。
特点，不稳定排序，时间复杂度永远 O n 平方，空间复杂度 O 1，交换次数比冒泡少，但是比较次数很多，大数据量性能差。
执行步骤
1 定义最小值索引
2 遍历未排序区域，更新最小值下标
3 一轮遍历完成，交换最小值和当前起始位置元素
4 起始位置向后移动一位，重复循环
插入排序
核心逻辑，把数组分成有序区和无序区，每次取出无序区第一个元素，向前插入到有序区合适位置，类似打扑克牌整理手牌。
特点，稳定排序，最好情况数组已经有序是 O n，最坏乱序 O n 平方，空间复杂度 O 1，近乎有序数组性能非常优秀，也是 TimSort 底层会使用的基础子算法。
执行步骤
1 从第二个元素开始作为待插入元素
2 待插入元素和前面有序元素依次对比，大于待插入元素就后移
3 找到空位之后把待插入元素放入
4 重复直到全部元素插入完成
快速排序
核心逻辑，选一个基准值 pivot，把数组分成两部分，小于基准放左边，大于基准放右边，也就是分区操作，之后递归对左右两个子数组继续分区排序。
特点，不稳定排序，平均时间复杂度 O nlogn，最坏情况数组已经有序，如果基准选的不好会退化到 O n 平方，空间复杂度是递归栈开销 O logn，是非常经典的分治算法，JDK 内置 sort 底层优化版本就是双轴快排。
执行步骤
1 选取基准值，常用首元素尾元素或者三数取中
2 双指针分区，把小于基准和大于基准元素分开
3 递归排序左子数组
4 递归排序右子数组
归并排序
核心逻辑，分治思想，不断把数组对半拆分，拆分到单个元素之后，再有序合并两个有序子数组，合并的时候对比两个子数组头部元素，依次取出较小值。
特点，稳定排序，时间复杂度固定 O nlogn，不受原始数据顺序影响，缺点是需要额外临时数组，空间复杂度 O n，对象数组 TimSort 就是归并排序优化版本。
执行步骤
1 递归拆分数组到最小单元
2 创建临时数组
3 双指针合并两个有序子段
4 把合并结果复制回原数组
希尔排序
核心逻辑，插入排序改进版本，先设置增量 gap，按照 gap 分组做分组插入排序，之后不断缩小 gap，直到 gap 等于 1，最后执行一次完整插入排序。
特点，不稳定排序，时间复杂度和增量序列相关，大约 O n 的 1.3 次方，空间复杂度 O 1，适合中等规模数组，面试考频低于快排和归并。
堆排序
核心逻辑，利用大顶堆或者小顶堆结构，先把数组构建成大顶堆，堆顶就是最大值，把堆顶和末尾元素交换，然后调整堆，重复这个过程完成排序。
特点，不稳定排序，时间复杂度固定 O nlogn，空间复杂度 O 1，原地排序，但是缓存友好性差，实际业务使用少于快排。
算法对比总表
| 排序算法 | 平均时间复杂度 | 最好 | 最坏 | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | O n² | O n | O n² | O 1 | 稳定 |
| 选择排序 | O n² | O n² | O n² | O 1 | 不稳定 |
| 插入排序 | O n² | O n | O n² | O 1 | 稳定 |
| 快速排序 | O nlogn | O nlogn | O n² | O logn | 不稳定 |
| 归并排序 | O nlogn | O nlogn | O nlogn | O n | 稳定 |
| 希尔排序 | O n^1.3 | O n | O n² | O 1 | 不稳定 |
| 堆排序 | O nlogn | O nlogn | O nlogn | O 1 | 不稳定 |
整体来说，Java 数组排序日常开发直接调用 Arrays.sort 或者 parallelSort，学习面试阶段重点手写冒泡选择插入快速归并，理解每种 Java 数组排序方法原理复杂度稳定性，根据数组规模原始有序情况选择合适算法，不要盲目认为快排永远最优，近乎有序小数组插入排序反而性能更好。
【常见问题】
问题 1 Java 数组排序 Arrays.sort 底层是什么算法
回答 1 Java 数组排序的 Arrays.sort 方法，基本类型数组底层使用双轴快速排序，对象类型数组底层使用 TimSort，TimSort 是归并排序的优化版本，这就是内置 Java 数组排序方法和普通手写快排的区别。
问题 2 Java 数组排序稳定排序有哪几种
回答 1 Java 数组排序里面稳定排序包含冒泡排序插入排序归并排序，稳定排序意思是相等元素排序之后原本相对顺序不会改变，Java 数组排序如果业务要求保留原有相对顺序，优先选择归并排序或者使用对象版 Arrays.sort。
问题 3 Java 数组排序可以直接实现降序吗
回答 3 Java 数组排序如果是基本类型 int 数组，Arrays.sort 默认只能升序，想要降序需要排序之后反转数组，如果是包装类数组 Integer，可以传入自定义 Comparator 实现降序，手写 Java 数组排序算法的时候只需要修改比较符号即可改成降序。
问题 4 Java 数组排序 parallelSort 适合所有场景吗
回答 4 Java 数组排序 parallelSort 并不适合所有场景，它是多核并行排序，超大数组性能优势明显，但是小数组会产生线程创建切换开销，小数组使用普通 sort 性能更好，选择 Java 数组排序方法要结合数组大小。
【免责申明】
本文 Java 数组排序算法讲解基于 JDK 标准实现，不同 JDK 版本底层排序实现可能存在微调，算法复杂度为理论分析，实际运行性能受 CPU 内存数据分布影响，本文仅作为学习面试参考，不代表所有场景下绝对最优方案。
