JAVA数据结构--排序

排序算法详解：七大基于比较的排序与非比较排序

学习目标

目录

• 1. 排序的概念及运用
  • 1.1 排序的概念
  • 1.2 排序的运用
• 2. 常见排序算法
  • 2.1 插入排序
    • 2.1.1 直接插入排序
    • 2.1.2 希尔排序（缩小增量排序）
  • 2.2 选择排序
    • 2.2.1 直接选择排序
    • 2.2.2 堆排序
  • 2.3 交换排序
    • 2.3.1 冒泡排序
    • 2.3.2 快速排序
    • 2.3.3 快速排序的优化
    • 2.3.4 快速排序的非递归实现
    • 2.3.5 快速排序总结
  • 2.4 归并排序
    • 2.4.1 基本思想与实现
    • 2.4.2 归并排序总结
    • 2.4.3 海量数据的排序问题
• 3. 排序算法复杂度及稳定性分析
• 4. 其他非基于比较的排序
  • 4.1 计数排序
  • 4.2 基数排序
  • 4.3 桶排序
• 5. 全文总结

1. 排序的概念及运用

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减地排列起来的操作。通常讨论的是**非递减（升序）**排列；若待排序列中所有关键字互不相同，则排序结果是唯一的。

稳定性：假定在待排序的记录序列中，存在多个具有相同关键字的记录。若经过排序，这些记录的相对次序保持不变——即在原序列中 r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中 r[i] 仍然在 r[j] 之前——则称这种排序算法是稳定的；否则称为不稳定的。

稳定性为什么重要？考虑多关键字排序：先按"数学成绩"排好，再按"语文成绩"做一次稳定排序，则语文成绩相同的同学仍然保持数学成绩的相对顺序。如果第二次排序不稳定，第一次的结果就被破坏了。因此稳定性直接决定了排序算法能否用于多关键字场景。

内部排序：整个排序过程完全在内存中进行的排序（数据元素全部放在内存中）。本文讨论的七大排序都属于内部排序。

外部排序：数据元素太多、不能同时放在内存中，需要根据排序过程的要求不断在内外存之间移动数据的排序。例如对磁盘上的大文件排序（详见 2.4.3 节）。

1.2 排序的运用

排序在实际生活中无处不在，最典型的就是电商商品列表的多维度排序。以京东为例，商品列表页顶部提供了「综合、销量、评论数、新品、价格」等排序方式：

• 点击「价格」，后台就把该类目下的商品按照价格字段做升序或降序排列；
• 点击「销量」，则按照销量字段降序排列；
• 「综合」则是一个加权后的复合关键字排序。

除此之外，排序还广泛应用于：数据库的 ORDER BY 查询、操作系统的进程调度、搜索引擎的结果排名、文件系统的目录组织、以及作为二分查找等算法的前置条件（二分查找要求序列有序）。可以说，排序是程序设计中使用频率最高、也是最重要的基础操作之一。

2. 常见排序算法

排序算法主要分为基于比较的排序和非基于比较的排序两大类。基于比较的排序有七大类：插入排序（直接插入、希尔排序）、选择排序（直接选择、堆排序）、交换排序（冒泡、快速排序）、归并排序。本章逐一讲解。

2.1 插入排序

2.1.1 直接插入排序

基本思想：直接插入排序是一种最简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

生活中我们打扑克牌时抓牌、理牌的过程用的就是插入排序思想：手中牌始终是有序的，每次摸一张新牌，就把它插入到手中已排序序列的合适位置。

当插入第 i (i >= 1) 个元素时，前面的 array[0], array[1], …, array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1], array[i-2], … 的排序码顺序（从后往前）进行比较，找到插入位置后将 array[i] 插入，原来位置上的元素顺序后移。

// 直接插入排序：升序
public static void insertionSort(int[] array) {
// 把 array[i] 插入到 [0, i-1] 的有序区间中
for (int i = 1; i < array.length; i++) {
int tmp = array[i]; // 待插入元素，先取出"哨兵"防止被覆盖
int j = i – 1;
// 比 tmp 大的元素统一后移一位，为 tmp 腾位置
while (j >= 0 && array[j] > tmp) {
array[j + 1] = array[j];
j—;
}
// 循环结束，j+1 即为插入位置
array[j + 1] = tmp;
}
}

直接插入排序的特性总结：

2.1.2 希尔排序（缩小增量排序）

希尔排序法又称缩小增量法，是对直接插入排序的优化。

基本思想：先选定一个整数 gap，把待排序文件中所有记录分成 gap 个组，所有距离为 gap 的记录分在同一组内，并对每一组内的记录进行直接插入排序。然后取 gap = gap / 2（或 / 3），重复上述分组和排序的工作。当 gap = 1 时，所有记录被分在统一组内，此时数组已经接近有序，再走一遍插入排序即可快速完成。

// 希尔排序：升序
public static void shellSort(int[] array) {
int gap = array.length;
while (gap > 1) {
gap = gap / 3 + 1; // +1 保证最后一轮 gap 一定等于 1
// 分别对 gap 个分组做直接插入排序
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i – gap;
while (j >= 0 && array[j] > tmp) {
array[j + gap] = array[j];
j -= gap;
}
array[j + gap] = tmp;
}
}
}

希尔排序的特性总结：

希尔排序的时间复杂度估算：

• 外层循环：gap 每次缩小一半（或三分之一），从 N 缩到 1，因此外层循环次数为 O(log₂n) 或 O(log₃n)，即 O(log n)。

• 内层循环：假设一共有 n 个数据，分成 gap 组，则每组为 n/gap 个。在每组中插入移动的次数最坏情况下为 1 + 2 + 3 + … + (n/gap – 1)，一共 gap 组，因此总计最坏情况下的移动总数为：

  gap × [1 + 2 + 3 + … + (n/gap – 1)]

  以「除 3」为例，gap 的取值有：n/3, n/9, n/27, …, 2, 1：

  • 当 gap = n/3 时，移动总数为 (n/3) × (1 + 2) = n；
  • 当 gap = n/9 时，移动总数为 (n/9) × (1 + 2 + … + 8) = (n/9) × [8 × (1 + 8) / 2] = 4n；
  • 最后一趟 gap = 1，即直接插入排序，内层循环排序消耗为 n。

  由此可以画出一条曲线：希尔排序在最初和最后阶段的排序次数都为 n，中间阶段先逐渐上升到某个顶点后再逐渐下降回 n，而该顶点的值目前无法给出精确的闭式计算过程。

关于希尔排序复杂度的结论：希尔排序的时间复杂度不好精确计算，因为 gap 的取值方案有很多种，不同的增量序列会得到不同的复杂度，因此很多教材给出的复杂度都不统一：

• 《数据结构（C 语言版）》——严蔚敏：给出了与增量序列相关的界；
• 《数据结构——用面向对象方法与 C++ 描述》——殷人昆：O(n^1.25)（取特定增量序列时）。

工程上一般把希尔排序的平均复杂度记作 O(N^1.3) 量级（介于 O(N) 与 O(N²) 之间，优于直接插入排序）。

2.2 选择排序

2.2.1 直接选择排序

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

排序过程：

• 在元素集合 array[i] … array[n-1] 中选择关键码最大（小）的数据元素；
• 若它不是这组元素中的最后一个（第一个）元素，则将它与这组元素中的最后一个（第一个）元素交换；
• 在剩余的 array[i] … array[n-2]（或 array[i+1] … array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素。

// 直接选择排序：升序
public static void selectSort(int[] array) {
// 每一轮从 [i, length) 中选出最小值的下标，与 array[i] 交换
for (int i = 0; i < array.length – 1; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array, i, minIndex);
}
}

直接选择排序的特性总结：

2.2.2 堆排序

堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种——本质上是「通过堆来进行选择数据」，从而把「选最值」的代价从 O(N) 降到了 O(log N)。

关键易错点：排升序要建大堆，排降序要建小堆。 原因是堆排序的思路是「反复把堆顶（最值）与末尾元素交换、然后堆的规模缩小」。排升序时希望最大的元素最终落到末尾，所以堆顶必须是当前区间的最大值，因此建大堆。若排升序建小堆，交换后堆顶（最小值）被换到了末尾，反而破坏了有序性。

// 向下调整：以 root 为根的 [root, end] 区间维护为大顶堆
private static void adjustDown(int[] array, int root, int end) {
int parent = root;
int child = parent * 2 + 1; // 左孩子
while (child <= end) {
// 选出左右孩子中较大的那个
if (child + 1 <= end && array[child + 1] > array[child]) {
child++;
}
if (array[child] > array[parent]) {
swap(array, child, parent);
parent = child;
child = parent * 2 + 1;
} else {
break; // 已经满足堆的性质，无需继续向下调整
}
}
}

// 堆排序：升序
public static void heapSort(int[] array) {
// 1. 建大堆：从最后一个非叶子结点开始向下调整
for (int i = (array.length – 1 – 1) / 2; i >= 0; i—) {
adjustDown(array, i, array.length – 1);
}
// 2. 反复把堆顶（最大值）与无序区末尾交换，无序区缩小 1
int end = array.length – 1;
while (end > 0) {
swap(array, 0, end);
adjustDown(array, 0, end – 1);
end—;
}
}

堆排序的特性总结：

堆排序的隐藏优势：它不依赖数据的初始分布，不存在「有序数据反而退化成 O(N²)」的情况，因此在**需要求 Top-K（前 K 大 / 前 K 小）**以及内存受限的场景中非常常用。

2.3 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1 冒泡排序

// 冒泡排序：升序
public static void bubbleSort(int[] array) {
// 每趟把 [0, length-i-1] 中的最大值"冒泡"到右端
for (int i = 0; i < array.length – 1; i++) {
boolean swapped = false; // 优化：一趟没有发生交换说明已有序
for (int j = 0; j < array.length – 1 – i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
swapped = true;
}
}
if (!swapped) {
break;
}
}
}

冒泡排序的特性总结：

2.3.2 快速排序

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法。

基本思想：任取待排序元素序列中的某元素作为基准值（pivot），按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

递归主框架：

// 假设按照升序对 array 数组中 [left, right] 区间中的元素进行排序
public static void quickSort(int[] array, int left, int right) {
if (right – left < 1) {
return; // 区间只剩 0 或 1 个元素，天然有序
}

// 按照基准值对 [left, right] 区间中的元素进行划分
int div = partition(array, left, right);

// 划分成功后以 div 为边界形成了左右两部分 [left, div-1] 和 [div+1, right]
quickSort(array, left, div – 1); // 递归排左半部分
quickSort(array, div + 1, right); // 递归排右半部分
}

上述递归主框架与二叉树的前序遍历规则非常像：写递归框架时联想二叉树前序遍历即可快速写出，剩下的关键在于分析如何按照基准值对区间数据进行划分。

将区间按照基准值划分为左右两半部分的常见方式有三种：

方式一：Hoare 版（双指针从两端向中间扫描）

private static int partitionHoare(int[] array, int left, int right) {
int i = left;
int j = right;
int pivot = array[left]; // 取最左元素为基准
while (i < j) {
// 右：找比基准小的（升序时从右往左找第一个 < pivot）
while (i < j && array[j] >= pivot) {
j—;
}
// 左：找比基准大的（从左往右找第一个 > pivot）
while (i < j && array[i] <= pivot) {
i++;
}
swap(array, i, j);
}
// 相遇点放回基准值
swap(array, i, left);
return i;
}

注意：Hoare 版必须从 right 端先开始扫描，这样两个指针相遇位置的值一定 ≤ 基准值，最后把基准值放到相遇点才满足「左边都比它小、右边都比它大」。

方式二：挖坑法

private static int partitionHoare2(int[] array, int left, int right) {
int i = left;
int j = right;
int pivot = array[left]; // 先把基准值"挖"出来，left 处成为第一个坑
while (i < j) {
while (i < j && array[j] >= pivot) {
j—;
}
array[i] = array[j]; // 右坑元素填左坑，右边形成新坑
while (i < j && array[i] <= pivot) {
i++;
}
array[j] = array[i]; // 左坑元素填右坑，左边形成新坑
}
array[i] = pivot; // 基准值落坑
return i;
}

方式三：前后指针法

private static int partitionHoare3(int[] array, int left, int right) {
int prev = left; // prev 指向"小于基准区间"的最后一个元素
int cur = left + 1;
while (cur <= right) {
// cur 找到比基准小的元素，prev 前移后与 cur 交换
if (array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array, cur, prev);
}
cur++;
}
// 最后把基准值放到 prev 位置，左边都 ≤ 基准，右边都 ≥ 基准
swap(array, prev, left);
return prev;
}

快速排序最坏情况：当序列已经有序或逆序时，每次划分极不均衡（一个子区间 N-1 个、另一个 0 个），递归树退化成一条链，时间复杂度退化到 O(N²)，并且递归深度达到 O(N)，可能造成栈溢出。

2.3.3 快速排序的优化

针对上述最坏情况，工程上有两个经典优化：

2.3.4 快速排序的非递归实现

递归本质上是利用系统栈保存「待处理区间」。当数据量很大、又担心递归退化为深链导致栈溢出（StackOverflow）时，可以用一个显式的栈来模拟递归：每次把子区间的左右边界压栈，再弹栈处理。

public static void quickSortNonR(int[] a, int left, int right) {
Stack<Integer> st = new Stack<>();
st.push(right);
st.push(left); // 先把整个区间的左右边界入栈
while (!st.empty()) {
int l = st.pop(); // 注意出栈顺序与入栈顺序相反
int r = st.pop();
if (r – l < 1) {
continue; // 区间只有 0/1 个元素，跳过
}
int div = partitionHoare(a, l, r); // 一次划分，得到基准最终位置
// 把左右两部分 [l, div-1] 和 [div+1, r] 的边界压栈
st.push(div – 1);
st.push(l);
st.push(r);
st.push(div + 1);
}
}

2.3.5 快速排序总结

2.4 归并排序

2.4.1 基本思想与实现

归并排序（MERGE-SORT）是建立在归并操作上的一种有效排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

核心步骤（把区间不断二分到只剩 1 个元素 → 天然有序 → 自底向上两两归并）：

// 归并排序：升序（递归版）
public static void mergeSort(int[] array, int left, int right, int[] tmp) {
// [left, right] 闭区间，只剩一个元素时不用再归并
if (right – left < 1) {
return;
}
int mid = (left + right) / 2;
// 1. 拆：先让左右两个子区间分别有序
mergeSort(array, left, mid, tmp);
mergeSort(array, mid + 1, right, tmp);
// 2. 合：把两个有序区间归并成一个有序区间
merge(array, left, mid, right, tmp);
}

// 归并两个有序区间 [left, mid] 与 [mid+1, right]
private static void merge(int[] array, int left, int mid, int right, int[] tmp) {
int leftStart = left;
int rightStart = mid + 1;
int i = left;
while (left <= mid && rightStart <= right) {
// 取等时优先取左边，保证稳定性
tmp[i++] = (array[left] <= array[rightStart]) ? array[left++] : array[rightStart++];
}
// 把剩余未拷贝的部分补进临时数组
while (left <= mid) {
tmp[i++] = array[left++];
}
while (rightStart <= right) {
tmp[i++] = array[rightStart++];
}
// 把排好序的区间拷回原数组
System.arraycopy(tmp, leftStart, array, leftStart, right – leftStart + 1);
}

归并排序必须额外申请一个 tmp 辅助数组，并且递归的终止条件是「只剩一个元素」，这与快速排序「划分完即结束」不同：快排是"边递归边干活"，归并是"递归回来之后才干活"。

2.4.2 归并排序总结

2.4.3 海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序。

前提：内存只有 1G，而需要排序的数据有 100G。由于内存中无法把所有数据全部放下，所以必须使用外部排序，而归并排序是最常用的外部排序。

典型做法：

这正是归并排序「空间换稳定」特性的用武之地：归并操作只需要线性空间 + 顺序读写的磁盘访问模式，天生契合外存。

3. 排序算法复杂度及稳定性分析

几条必须记住的结论（也常作为考点）：

• 时间复杂度为 O(N²) 的：插入、希尔、选择、冒泡（前四种「慢」排序）；
• 时间复杂度为 O(NlogN) 的：堆排序、快速排序、归并排序；其中快速排序最坏会退化到 O(N²)；
• 不稳定的四种：希尔、选择、快排、堆排（口诀："些（选）谢（希尔）快堆"不稳定）；
• 空间复杂度为 O(N) 的：归并排序（唯一需要线性辅助空间的主流内部排序）；
• 基本有序时，直接插入排序最快（可降至 O(N)）；而快速排序在数据有序时划分极不均，反而退化成接近冒泡排序的 O(N²)。

记忆小贴士：想记稳定性，可以联想——「谁跨得远谁就不稳定」。希尔排序跨 gap 距离交换、选择排序跨区间选最值交换、快排跨越基准值划分、堆排序堆顶与末尾远距离交换，这四者都会越过相等元素、破坏相对次序；而插入、冒泡只在相邻/局部移动，归并取等优先取左侧，都保持了稳定性。

4. 其他非基于比较的排序

前面七大排序都靠「比较 + 移动」，其时间复杂度下界已被证明是 O(NlogN)。而非基于比较的排序突破了这一限制，可以做到线性时间 O(N)，代价是用空间换时间、且通常对数据分布有要求。

4.1 计数排序

思想：计数排序又称为鸽巢原理（抽屉原理），是对哈希直接定址法的变形应用。

操作步骤：

// 计数排序：适用于整数且数据范围集中
public static void countSort(int[] array) {
int min = array[0], max = array[0];
for (int num : array) { // 1. 找出范围，决定计数数组大小
if (num < min) min = num;
if (num > max) max = num;
}
int[] cnt = new int[max – min + 1];
for (int num : array) { // 2. 统计每个值出现次数
cnt[num – min]++; // 减去 min 做偏移，支持负数
}
int i = 0;
for (int j = 0; j < cnt.length; j++) { // 3. 按下标顺序回收
while (cnt[j]— > 0) {
array[i++] = j + min;
}
}
}

计数排序的特性总结：

经典应用：对 1 亿个整数排序，但每个数的取值范围只有 0～100（如年龄、分数），此时计数排序远快于快排。

4.2 基数排序

思想：基数排序（Radix Sort）是借助多关键字排序思想对单逻辑关键字进行排序的方法。它不比较关键字大小，而是按照关键字的每一位（个位 → 十位 → 百位……）进行「分配 + 收集」，重复若干轮。

以 LSD（低位优先）为例，对 [297, 35, 200, 9] 排序：

基数排序的特性总结：

4.3 桶排序

思想：桶排序（Bucket Sort）是计数排序的升级版。它的工作原理是把数组划分成有限个「桶」，将待排数据映射到这些桶中，再对每个桶单独排序（可用插入排序，也可递归使用桶排序），最后把所有桶里的数据按顺序拼接起来。

• 适用前提：数据在值域上近似均匀分布，这样每个桶里的元素才会足够少，单桶排序代价才低；
• 时间复杂度：数据均匀分布时平均可达 O(N)，最坏（全部挤进一个桶）退化为单桶内所用排序的复杂度；
• 空间复杂度：O(N + K)（K 为桶数）；
• 稳定性：取决于桶内所用的排序算法（用稳定的插入排序，则整体稳定）。

三者关系可以这样理解：计数排序是「桶 = 每一个取值」的极端桶排序；桶排序是「一个桶装一段范围」的泛化计数排序；基数排序则是「按位反复做稳定分桶」。

5. 全文总结

回到最初的学习目标，本篇围绕「七大基于比较的排序」完成了如下梳理：

排序是数据结构的"基本功"，看似简单，实则每个算法背后都对应着一种重要的算法思想：插入是「维持不变式」、希尔是「增量优化」、选择是「贪心选最值」、堆是「用结构加速选择」、快排是「分治 + 划分」、归并是「分治 + 合并」。理解这些思想，比单纯背下复杂度表更有价值。