企业官网建设流程全解析

很多朋友问过我同一个问题：Java 排序算法到底该怎么学？面试前背了又忘、忘了又背，真到了手写代码的时候，要么边界条件写错，要么复杂度分析说不清楚。这篇东西我准备了很久，从“为什么要学排序”讲到“每个算法到底怎么想出来的”，再到“面试官真正想考你什么”，一次性把 Java 里最常考的排序算法聊透。这篇文章面向零基础读者，但已经工作几年的朋友翻一翻也能有收获——尤其是快排优化和堆排那块，很多人在工作中写了几年 CRUD，回头再看这些基础反而能读出新的味道。

先说明一点：这篇文章不追求“算法竞赛解法大全”，而是把面试和日常开发中最常出现的 8 个排序算法讲清楚：冒泡、选择、插入、希尔、归并、快排、堆排，外加计数排序和桶排序这类“非比较排序”。每个算法都会给出完整的 Java 代码实现、复杂度推导、稳定性分析，以及我这么多年看别人写代码和带队面试时踩过的坑、品出的门道。收藏当然欢迎，但我更希望你边读边把代码自己敲一遍——排序这个东西，看十遍不如手写一遍，写完跑通了你才算真正拿下了。

1. 排序算法学习地图：先看清全貌再动手

1.1 为什么排序算法是 Java 面试的“硬骨头”

先说个现实：Java 后端招聘中，排序算法几乎是笔试和一面手写代码环节的“必考题”。不是说面试官非要看你写出一个性能最优的快排，而是排序算法能非常高效地暴露一个候选人的基本功——你能不能把思路转化成代码、能不能处理好边界条件、能不能分析清楚时间复杂度和空间复杂度、能不能解释“这个算法为什么稳定/不稳定”。

再往深一层说，排序算法是理解数据结构的一把钥匙。比如堆排序用到了完全二叉树和数组下标的映射关系；归并排序是分治思想的典型代表；快速排序的 partition 过程被广泛用在“查找第 K 大元素”这类问题里。把这些算法吃透，你后面学二叉树、学堆、学 TopK 问题、学分治算法都会轻松很多。我见过不少候选人，HashMap 八股背得滚瓜烂熟，结果让他手写一个快排——循环里 i 和 j 的边界没想明白，空指针直接崩了。这就是地基没打牢。

从实用角度看，排序算法也是“程序性能优化”的基本功。虽然日常开发中大多数场景直接调用Arrays.sort()就够了，但当你处理海量数据、或者需要对特定数据结构排序时，只有理解了各算法的特点和瓶颈，才能做出正确的技术选型。比如你面对的数据几乎有序，插入排序的性能会远超快排；你需要在排序过程中保持相等元素的原始相对顺序，那就不能用选择排序。

1.2 排序算法全览与复杂度对照表

把常用的排序算法放在一起看，我们需要关注四个维度：时间复杂度（最好情况、最坏情况、平均情况）、空间复杂度、是否稳定（即关键字相同的元素在排序后能否保持原有相对顺序）、以及是否原地排序（是否占用额外内存）。

注意几个细节：冒泡排序在数组完全有序的情况下可以优化到 O(n)，只需要加一个“本轮是否发生过交换”的标记；快速排序的最坏情况发生在每次 partition 都极度不平衡时，比如对已经有序的数组选择第一个元素作为基准；堆排序和归并排序的时间复杂度无论数据分布如何都非常稳定，都是 O(n log n)，但归并排序需要额外 O(n) 的辅助空间，堆排序则是原地排序。

1.3 学习顺序建议：从“看得懂”到“写得对”

我建议零基础的朋友按以下顺序推进，不要一上来就啃快排和堆排。

• 第一阶段：搞懂冒泡排序、选择排序、插入排序。这三个是“暴力型”算法基线，代码量小、思路直观，能帮你建立“比较—交换”和“比较—插入”的思维模型。
• 第二阶段：学习希尔排序和归并排序。希尔排序是插入排序的升级版，归并排序带你进入分治世界。
• 第三阶段：攻克快速排序和堆排序。这两个是面试重点，也是理解递归和树结构的最佳入口。
• 第四阶段：了解计数排序、桶排序、基数排序。它们不再是“比较排序”，思维上要做一个切换。

每一层我建议都亲手实现一遍，并跑几个测试用例，比如空数组、单个元素、完全逆序、包含大量重复元素、完全有序这几种输入。我当年就是这么练的，跑着跑着你就发现了：原来“看似对的代码”在边界条件下有那么多 bug。

2. 三个基础排序：从暴力到小优化

2.1 冒泡排序：从“相邻交换”理解稳定性

冒泡排序的思路非常朴素：每一轮从头到尾依次比较相邻的两个元素，如果顺序不对就交换它们。一轮结束后，最大的元素就像气泡一样“浮”到了数组末尾。重复 n-1 轮，数组就排好了。

public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int n = arr.length; for (int i = 0; i < n - 1; i++) { boolean swapped = false; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); swapped = true; } } if (!swapped) { break; } } } private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }

这里我引入了swapped标记：如果某一轮循环中没有任何交换，说明数组已经有序，直接退出。这是冒泡排序最常见的优化。时间复杂度方面，最坏情况是数组完全逆序，需要执行 n(n-1)/2 次比较和交换，所以是 O(n²)；最好情况是数组已经有序，加上优化后只需一轮扫描，复杂度降为 O(n)。

关于稳定性：冒泡排序是稳定的。当两个相邻元素相等时，我们只做“大于”判断才交换，所以相等元素的相对顺序不会改变。这个特性在有些业务场景中很重要，比如你按价格排序后，价格相同的商品仍要保留原来的上架时间顺序。

面试常考变体：双向冒泡排序，也就是“鸡尾酒排序”。它不同于普通冒泡只从一端往另一端扫，而是先从左到右把最大值移到末尾，再从右到左把最小值移到开头，交替进行。对“大部分元素已经有序”的数组，鸡尾酒排序可以减少轮数。

2.2 选择排序：不稳定性的经典示例

选择排序的思路更直观：每一轮从未排序区间中找出最小的元素，把它放到已排序区间的末尾。具体来说，第 i 轮在[i, n-1]范围内找最小值，找到后与第 i 个位置的元素交换。

public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int n = arr.length; for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex != i) { swap(arr, i, minIndex); } } }

选择排序的时间复杂度无论是最好、最坏还是平均都是 O(n²)，因为它总是要遍历未排序区间来找最小值，数据“好像有序”并不能帮它省事。空间复杂度 O(1)，属于原地排序。

为什么说选择排序不稳定？我用一个经典例子说明：数组[5, 8, 5, 2, 9]。第一轮找到的最小值是 2，下标为 3，于是把arr[0]的 5 和arr[3]的 2 交换。交换后，原来在下标 0 的 5 跑到了下标 3，原来在下标 2 的 5 还在原地。两个 5 的相对位置被打破了——第一个 5 现在跑到了第二个 5 的后面。这就是不稳定。

稍微想深一点：稳定性在业务中的价值在于“多关键字排序”。比如我们想先按销量从高到低排序，销量相同的再按价格从低到高排序。如果使用不稳定排序，第一轮按价格排序后，第二轮按销量排序时可能会把价格顺序打乱。稳定排序则可以安全地“从次要关键字到主要关键字”逐轮排序。

2.3 插入排序：打扑克牌的学习方法

插入排序的思路最贴近生活：就像打扑克牌时，你一张一张地摸牌，把新摸到的牌插到手里已经有序的牌中的合适位置。在数组中，我们把待排序元素往前比较，找到合适的位置插入。

public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int n = arr.length; for (int i = 1; i < n; i++) { int cur = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > cur) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = cur; } }

插排的实现细节值得玩味：我们不是“交换”元素，而是“平移”元素。先把当前元素cur存下来，然后从后往前把比cur大的元素依次往后移一位，最后把cur放到空出来的位置。这个“平移”比“交换”少了很多次赋值操作，性能上更有优势。

插入排序的最好情况是数组已经有序，此时内层 while 循环一次都不执行，时间复杂度 O(n)；最坏情况是逆序，时间复杂度 O(n²)。插入排序是稳定的，因为arr[j] > cur时我们才平移，相等的元素不会越过彼此。

插入排序的杀手级应用场景：当数据规模比较小（比如少于 50 个元素）或者数据“几乎有序”时，插入排序的性能往往优于复杂度更优的快排。原因是快排有递归调用、partition 的常数项比较大，而插入排序在近乎有序的数据上几乎退化成 O(n)。这也是 Java 标准库在底层排序时对小规模数组使用插入排序的原因，后面我会详细讲。

3. 分治思想：归并与快速排序

3.1 归并排序：分治法的标准模板

归并排序利用的是分治思想：先把数组从中间分成两半，分别排序，然后再把两个有序的子数组合并成一个有序数组。拆分的递归出口是“只有一个元素”的子数组，它天然有序。

public static void mergeSort(int[] arr, int left, int right) { if (left >= right) { return; } int mid = left + ((right - left) >> 1); mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } private static void merge(int[] arr, int left, int mid, int right) { int[] tmp = new int[right - left + 1]; int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; } } while (i <= mid) { tmp[k++] = arr[i++]; } while (j <= right) { tmp[k++] = arr[j++]; } System.arraycopy(tmp, 0, arr, left, tmp.length); }

合并过程是归并排序的核心：两个子数组已经有序，我们分别用两个指针 i 和 j 指向两个子数组的起点，每次比较arr[i]和arr[j]，把较小的那个放入临时数组，然后移动对应指针。某一边先用完后，直接把另一边的剩余元素全部拷贝进临时数组。注意mid的写法是left + ((right - left) >> 1)而不是(left + right) / 2，因为后者在 left 和 right 都很大时可能溢出——这是面试中一个值得说的优化点。

归并排序的时间复杂度非常稳定：每次划分把问题规模减半，递归深度 O(log n)，每一层合并的总代价是 O(n)，所以总复杂度 O(n log n)。空间复杂度是 O(n)，因为每层递归都要申请临时数组。当然像我上面这样写，每次 merge 都 new 一个数组，频繁创建对象会有额外开销；工程上更优的写法是申请一个全局的临时数组，每次 merge 复用它。

归并排序的稳定性来自合并时的判断条件arr[i] <= arr[j]：左边子数组的相等元素会先被放入结果，不会跑到右边相等元素的后面，所以是稳定的。归并排序还天然适合外部排序——比如要对海量数据排序，内存装不下，可以把大文件拆成多个小文件分别排序，再通过归并合并。

3.2 快速排序：应用最广泛的排序算法

快速排序也是分治思想，但它的思路比归并排序更“反直觉”：归并是“先递归排序子数组再合并”，快排是“先分区，再递归排序分区后的子数组”。所谓分区，就是选一个基准值，把比基准值小的元素放在左边，比基准值大的元素放在右边，然后返回基准值的最终下标。

public static void quickSort(int[] arr, int left, int right) { if (left >= right) { return; } int pivotIndex = partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); } private static int partition(int[] arr, int left, int right) { int pivot = arr[left]; int i = left; int j = right; while (i < j) { while (i < j && arr[j] >= pivot) { j--; } while (i < j && arr[i] <= pivot) { i++; } if (i < j) { swap(arr, i, j); } } swap(arr, left, i); return i; }

这是经典的“挖坑法”或叫“左右指针法”：先取最左边的元素作为 pivot，然后从右边找第一个比 pivot 小的元素，从左边找第一个比 pivot 大的元素，找到后交换。两个指针相遇的位置，就是 pivot 的最终位置，最后把arr[left]和arr[i]交换。这里有个关键点：必须是先从右往左找，再从左往右找。如果你先从左往右，最后交换 pivot 时可能会把“比 pivot 大”的元素换到最左边，导致分区错误。这个坑我见过无数次了。

快排的平均时间复杂度是 O(n log n)，但它有一个致命的弱点：如果每次 partition 选择到的 pivot 都恰好是当前区间的最小值或最大值，那两边极不平衡，递归退化成“每次只排好一个元素”，复杂度变成 O(n²)。典型场景就是对已经有序的数组做快排，如果你固定取第一个元素作为 pivot，那么每次分区都只分出一个元素，性能惨不忍睹。这也是为什么工程上不能简单取第一个元素当 pivot。

3.3 快速排序的优化策略与三路快排

既然快排的性能瓶颈在于 pivot 的选择和重复元素的处理，业界总结了几个非常有效的优化手段。

第一，“三数取中”：不是取第一个元素当 pivot，而是取左端点、右端点、中点三个元素中的中位数作为 pivot。这能极大地避免有序数组下“最坏情况”的出现。实现上，可以先做一次比较，把中位数交换到left位置，再走常规的 partition 流程。

private static void medianOfThree(int[] arr, int left, int right) { int mid = left + ((right - left) >> 1); if (arr[mid] < arr[left]) { swap(arr, mid, left); } if (arr[right] < arr[left]) { swap(arr, right, left); } if (arr[right] < arr[mid]) { swap(arr, right, mid); } swap(arr, mid, left); }

第二，小区间使用插入排序。快排在数据规模很小的时候，递归调用带来的开销反而比插入排序的常数更大。所以当right - left小于某个阈值（比如 16）时，直接调用插入排序，省去递归。

第三，三路快排（3-way partition）。当数组中有大量重复元素时（比如 100 万个元素全是 0 到 9 的随机数），标准快排依然会对重复元素做大量无谓的 partition。三路快排的思路是把数组分成三块：小于 pivot、等于 pivot、大于 pivot。partition 之后，等于 pivot 的区间直接不需要再递归处理了。对于含大量重复元素的场景，三路快排的速度可以是标准快排的几倍。

public static void quickSort3Ways(int[] arr, int left, int right) { if (left >= right) { return; } int pivot = arr[left]; int lt = left; int i = left + 1; int gt = right; while (i <= gt) { if (arr[i] < pivot) { swap(arr, lt++, i++); } else if (arr[i] > pivot) { swap(arr, i, gt--); } else { i++; } } quickSort3Ways(arr, left, lt - 1); quickSort3Ways(arr, gt + 1, right); }

三路快排的思路在 Java 的Arrays.sort()底层也有体现，不过它针对的是基本类型数组。JDK 中的DualPivotQuicksort（双基准快排）使用了两个 pivot 把数组分成三块，本质上也是为了让更多元素更快归位。

3.4 归并与快排怎么选

面试中经常被问：既然快排平均性能好，为什么还需要归并？答案可以从三个维度看。

• 稳定性：归并稳定，快排不稳定。如果业务要求保持相等元素的相对顺序，归并更合适。
• 空间占用：归并需要 O(n) 额外空间，快排是原地排序（递归栈不算额外数据空间），只需要 O(log n) 的递归栈空间。内存受限时快排更优。
• 数据分布：快排对数据分布敏感，有序数组不优化会退化；归并无论数据怎么分布，复杂度都是稳定的 O(n log n)。

所以 Java 标准库做了一个非常聪明的决策：Collections.sort()（对象数组排序）使用稳定的归并排序变体 TimSort；Arrays.sort()对基本类型数组使用双基准快排，因为基本类型不需要考虑稳定性。这个设计取舍本身就是一道很好的面试题。

4. 堆排序：借助二叉堆的力量

4.1 完全二叉树与大小顶堆

堆是一种特殊的完全二叉树，它满足两个性质：结构性——树是满的，除了最后一层，其他层节点必须填满，最后一层从左到右连续填充；堆序性——每个节点的值都大于等于（大顶堆）或小于等于（小顶堆）其子节点的值。

堆之所以高效，是因为它可以直接用数组表示：下标为 i 的节点，其左子节点下标为2*i + 1，右子节点下标为2*i + 2，父节点下标为(i - 1) / 2。这种“数组就是树”的表达方式，省去了指针的存储开销，也方便在数组上直接排序。

堆排序的基本思路分两步：第一步把无序数组构建成一个大顶堆；第二步反复把堆顶元素（最大值）与数组末尾元素交换，堆的规模缩小一个，然后对新的堆顶执行“下沉”操作，恢复堆序性。这样循环 n-1 次，数组就从小到大排好了。

4.2 堆排序的完整实现与下沉操作

先说“下沉”（sift down）操作：让一个节点不断与它较大的子节点比较，如果小于较大的子节点就交换，直到它比所有子节点都大，或者没有子节点。堆排序的核心就是这个操作。

public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int n = arr.length; // 1. 建堆：从最后一个非叶子节点开始下沉 for (int i = n / 2 - 1; i >= 0; i--) { siftDown(arr, i, n); } // 2. 排序：堆顶与末尾交换，缩小堆范围，再下沉 for (int i = n - 1; i > 0; i--) { swap(arr, 0, i); siftDown(arr, 0, i); } } private static void siftDown(int[] arr, int i, int heapSize) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < heapSize && arr[left] > arr[largest]) { largest = left; } if (right < heapSize && arr[right] > arr[largest]) { largest = right; } if (largest != i) { swap(arr, i, largest); siftDown(arr, largest, heapSize); } }

为什么要从n/2 - 1开始建堆？因为最后一个非叶子节点的下标是n/2 - 1，从这个节点开始往前逐个下沉，可以保证“当处理某个节点时，它的左右子树已经是合法的堆”。这比从根节点开始下沉高效得多，时间复杂度是 O(n) 而不是 O(n log n)，具体推导可以在“堆优化建堆”的资料里找到。

堆排序的时间复杂度非常稳定，最好、最坏、平均都是 O(n log n)，空间复杂度 O(1)。但它的缺点也很明显：不稳定。比如数组[5, 5, 3]构建大顶堆后，堆顶的 5 会被换到数组末尾，另一个 5 留在前面，两个 5 的相对顺序就变了。另外，堆排序在实际运行中往往比快排慢，因为它在排序过程中对内存的访问是“跳跃式”的（父节点与子节点的下标相差较大），这不利于 CPU 缓存命中。

虽然堆排序在纯排序场景下不如快排常用，但“堆”这种数据结构本身非常值钱。优先队列、TopK 问题（比如找海量数据中最大的 100 个）、定时任务调度、Dijkstra 算法，底层全是堆的身影。面试时如果时间有限，我建议你重点把建堆和下沉两个操作练熟，很多题都能复用这套模板。

4.3 面试延伸：用堆解决 TopK 问题

一个很常见的面试场景是：有 100 亿个数，内存只能装下一部分，如何找出最大的 100 个数？如果用排序，内存根本装不下；用一个大小为 100 的小顶堆，每次新来一个数就和堆顶比较，如果比堆顶大，就poll掉堆顶，把这个数放进去。最终堆里剩下的就是最大的 100 个数。这个思路就是典型的“堆”而不是“排序”的应用，能把上一小节学到的东西直接迁移到实战问题中。

5. 非比较排序：跳出“比大小”的框架

5.1 计数排序：用数组下标代替比较

计数排序的基本思想非常“暴力”：既然数据都是整数，而且范围已知，那我可以创建一个足够大的计数数组，遍历原始数据，统计每个数出现的次数；然后再按顺序把每个数依次放回原数组中。

public static void countingSort(int[] arr, int maxValue) { int[] count = new int[maxValue + 1]; for (int num : arr) { count[num]++; } int index = 0; for (int i = 0; i <= maxValue; i++) { while (count[i] > 0) { arr[index++] = i; count[i]--; } } }

这个最简单的版本是“不稳定”的，因为我们在回填时没有保持同值元素原有的先后顺序。要实现稳定版，需要借助前缀和：先计算每个值的累计出现次数，然后从原数组从后往前遍历，根据累计次数把元素放到结果数组的正确位置，每放一个就把计数减一。这样一来，相等元素会按照原数组中的相对顺序依次落到结果数组里。

计数排序的时间复杂度是 O(n + k)，其中 k 是数据范围。当k远小于n时，效率极高，比如给 100 万个 0 到 100 之间的整数排序，计数排序秒杀任何比较排序。但如果数据范围很大——比如对 100 万个分布在[0, 10^9]的整数排序，计数数组就要开到 10 亿，空间直接爆炸。工程上使用时，务必先确认数据分布是否适合。

5.2 桶排序与基数排序的适用边界

桶排序是计数排序的一般化版本：把数据按照某种映射函数分到若干个桶里，每个桶内再用其他排序算法（比如插入排序或快排）排序，最后把所有桶的结果依次合并。桶排序效率高低完全取决于映射函数的选择——如果数据分布均匀，每个桶里的元素数量差不多，复杂度接近 O(n)；如果数据都挤到一个桶里，退化成普通排序的 O(n²)。

基数排序很有意思，它不直接比较数字大小，而是按位数逐个排序。比如对非负整数，先按个位排序，再按十位排序，最后按百位排序，每一轮都用稳定的计数排序。因为计数排序是稳定的，所以每一轮排序后，低位的顺序不会被高位的顺序打乱。基数排序的时间复杂度是 O(d × (n + k))，d 是最大数字的位数。它适合位数不多、但数值范围很大的整数排序。

这三种非比较排序的共同点是“用空间换时间”，而且它们对数据类型有严格要求：计数排序要求整数且范围可控，桶排序要求数据能均匀映射到桶，基数排序要求数据能按位拆解。在面试中，非比较排序通常不会让你手写代码，而是考察你是否知道它们的存在、能否分析出优劣和适用场景。能说出“Java 的Arrays.sort()用快排处理基本类型、用 TimSort 处理对象类型，但不会用计数排序”，这已经能体现你的知识深度了。

6. 面试实战与避坑指南

6.1 深入 Java 内置排序：Arrays.sort 的底层秘密

我建议你在搞懂手写排序之后，再花点时间看看 Java 标准库里的排序实现，因为这里面的工程智慧比任何算法书都值钱。

Arrays.sort(int[])在 JDK 8 以后使用DualPivotQuicksort（双基准快排）。名字里的 “DualPivot” 说明它不是选一个 pivot，而是选两个 pivot，把数组分成三段：小于 pivot1、pivot1 到 pivot2 之间、大于 pivot2。这样 partition 一次可以让更多元素归位，常数项更低。当数组规模小于 47 时，它直接改用插入排序——因为小规模数据上递归开销太大了；当数组基本有序时，它会去检查数组是否“近乎排序”，如果是，就走归并排序的逻辑，避免快排退化。这些自适应策略，就是工程代码和教科书代码的区别。

Collections.sort()/Arrays.sort(Object[])则使用 TimSort，一种稳定的归并排序优化版本。TimSort 会先找到数组中“天然有序”的片段（称为 run），再用归并的方式把这些 run 合并起来。如果数据本身就是几段有序序列拼接起来的，TimSort 能直接受益，几乎达到 O(n) 的时间复杂度。这是它在处理对象排序时被选中的关键原因——对象排序默认要求稳定。

我在面试候选人时，特别喜欢问一句：“为什么 Java 要给基本类型数组和对象数组用两套完全不同的排序算法？” 这个问题能同时考察你对稳定性、时间复杂度、空间复杂度、工程权衡的综合理解。如果你能答出“基本类型不需要稳定，所以用更快的双基准快排；对象类型需要稳定，所以用 TimSort”，说明你是真的理解了排序的本质，而不只是背了八股。

6.2 手写排序最常见的 8 个错误

我在带团队和辅导新人时，归纳了手写排序时最容易出错的几个点，你写代码的时候一定要警惕。

• 边界条件没写：left > right或者left >= right的递归出口漏了，无限递归直接栈溢出。
• 快排中 i 和 j 相遇的判断写错：while (i < j)写成了while (i <= j)，导致数组越界。
• 快排先从左扫描而不是从右扫描：如果 pivot 选在最左边，必须先移动右指针，再移动左指针，否则最后交换 pivot 时会出问题。
• 归并排序的临时数组拷回主数组时，System.arraycopy写错位置：要拷回arr[left]开始的位置，而不是arr[0]。
• 插入排序忘记把cur放到j + 1位置：很多人平移完arr[j]之后，忘了最后一步赋值，导致元素丢失。
• 堆排序建堆时从n/2开始而不是n/2 - 1：最后一个非叶子节点下标算错，建出的堆不合法。
• 下沉操作忘了判断heapSize的收缩：交换堆顶和末尾元素后，新的堆范围应当是i，如果不收缩，排好的元素会被再次调整。
• 用(left + right) / 2计算中点：当 left 和 right 都接近 Integer.MAX_VALUE 时会溢出成负数，正确写法是left + (right - left) / 2。

还有一个“散装问题”：很多人能写对主逻辑，但swap方法里没有用临时变量，或者用异或交换导致两个相同变量交换后变成 0。面试时可以顺手用小技巧a ^= b; b ^= a; a ^= b;，但日常代码中还是老老实实写临时变量，可读性优先。

6.3 面试回答策略：先问需求再选算法

很多候选人在手写算法前，连问题都没听清就开写。我建议你遵循这套思路来组织答案，不仅显得专业，还能避免踩进陷阱。

第一步，确认排序的对象和规模：是整数数组还是对象数组？数据量级是多少？能否一次性载入内存？这决定了是用比较排序还是非比较排序，也决定了空间复杂度能不能接受。第二步，确认稳定性要求：相等元素的相对顺序重要吗？如果需要稳定，选归并或插入；如果不需要，可以选快排。第三步，确认数据分布：数据是否基本有序？是否有大量重复元素？如果是，建议在快排的基础上做三数取中、三路快排等优化。第四步，说出时间复杂度和空间复杂度，并解释为什么这个选择最适合当前场景。

我举一个实际例子：面试官让你对一个“长度很大的、值域很小的整数数组”排序。如果你直接写快排，当然也不算错，但如果你能想到这里可以用计数排序，把复杂度做到 O(n)，并且写出稳定版本的代码，那印象分是明显不一样的。排序算法面试不是背模板，而是考察“你把问题和算法匹配起来”的能力。

6.4 学习资源与实践建议

如果你想把排序算法练到“肌肉记忆”的程度，我给你三个建议。

一是刻意练习输入类型。不要只测随机数组，多测边界用例：空数组、单元素、两个元素、完全有序、完全逆序、全部相同元素、含大量重复元素。每次跑测试时，可以写一个校验函数，判断排序结果是否正确，以及是否稳定（可以给元素带原始下标来验证）。

二是可视化学习。看动画演示排序过程很有帮助，尤其是快排的分区、归并的合并、堆的建堆和下沉。我当年就是靠“先看动画理解过程，再手写代码”的方式，把那些抽象的递归过程在脑子里“跑”出来的。

三是做变体题。排序算法很少单独考，更多是和其他知识点结合。比如“统计数组中逆序对数量”就是归并排序的经典变体；“寻找第 K 大元素”可以用快排的 partition 实现；“合并 K 个有序链表”可以用堆或归并解决。做完这些变体，你会发现自己对排序的理解上了一个台阶。

我个人在实际操作中的体会是：不要追求“一天速成”。第一遍先看懂算法思想，能写出代码；第二遍隔三天，不看答案，直接默写；第三遍再隔一周，把优化版（比如三路快排、TimSort 风格的归并）也写一遍。三次下来，这个算法才真正属于你。踩过几次坑之后你会发现，所谓“精通”不是记住了多少种算法，而是你能在写的过程中知道自己为什么会写错，以及怎么绕开这些坑——这种手感，才是面试和工作中真正值钱的东西。