排序算法是Java基础里最容易被轻视、又最容易被面试官当成筛子用的一块内容。工作三五年的人回头再看冒泡、快排、堆排第一反应往往是这我大学就写过可真让你在白板上把三路快排的分区逻辑一行行写对或者在十万级数据上把归并和快排的耗时差异讲清楚能扛住的人其实不多。我这次把自己这些年写过的、讲过的、面试被问过的Java排序算法重新梳理了一遍凑齐十种并且补上了配套的演示动画实现方案——不是那种网上随便找个GIF看看的动画而是你自己能跑起来、能调参数、能对比性能的可视化工具。这篇内容适合三类人正在准备Java面试、想把排序这块八股答出深度的人写业务代码时偶尔要自己撸个小排序、不想无脑调Arrays.sort的人以及想给算法课做演示、需要一套可视化方案的开发或者讲师。我会把每种算法的核心思路、关键代码、复杂度账、容易写错的边界以及动画演示怎么做全部摊开讲一遍。文中所有代码都是可以直接粘进IDE跑的完整片段不用你自己补东补西。1. 先把这10种排序算法摆到桌面上1.1 为什么面试官总盯着排序算法不放很多人以为面试问排序是八股惯性其实面试官想看的根本不是你能不能背出冒泡是O(n²)这句话。排序算法是一个极佳的压缩包里面塞满了面试官想考察的东西你写循环时对边界的敏感度i n-1还是i n、你对递归和迭代的取舍判断、你能不能主动聊稳定性、你知不知道平均复杂度和最坏复杂度的区别、以及你在被追问为什么快排退化到O(n²)时是慌还是能顺着答下去。我面过不少候选人让他们手写快排十个里有六个会卡在分区的边界上。常见错误是while (i j arr[i] pivot)和while (i j arr[j] pivot)这两个条件里漏掉等号导致数组里有重复元素时死循环。这种错误暴露的不是算法知识而是写代码时的严谨程度——这才是面试官真正在打分的地方。所以我的建议是别把排序当背诵题把它当手写代码能力的体检项目。每种算法你至少要能写出主循环和边界条件能说清为什么要这么写能举出一个它写崩的具体场景。1.2 十种算法的分类与选型地图十种算法不是并列关系它们可以按复杂度和思路分成三档。把这张地图记在脑子里比死记十份代码有用得多。档位算法平均时间最坏时间额外空间稳定性基础档 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(n^1.3)O(n²)O(1)不稳定进阶档 O(nlogn)归并排序O(nlogn)O(nlogn)O(n)稳定进阶档 O(nlogn)快速排序O(nlogn)O(n²)O(logn)不稳定进阶档 O(nlogn)堆排序O(nlogn)O(nlogn)O(1)不稳定线性档计数排序O(nk)O(nk)O(k)稳定线性档桶排序O(nk)O(n²)O(nk)依赖桶内排序线性档基数排序O(d(nr))O(d(nr))O(nr)稳定看这张表有几个关键点值得拎出来说。第一稳定性的判断不能靠背要靠理解元素跨越式交换会不会打乱相同值的相对顺序选择排序之所以不稳定就是因为它在找最小值时会把远处的小元素和前面的元素直接对调相同值之间的次序可能被打乱。第二线性档的O(nk)看起来很美但k是数据范围如果你的数据是1到1亿之间随机分布计数排序的辅助数组根本开不出来这就是空间换时间的代价不是白给的。第三工程里真正被大量使用的只有快排、归并、插入小数组场景这几种JDK的Arrays.sort对基本类型用的是双轴快排对引用类型用的是TimSort归并的优化变种因为引用类型需要稳定性。你去看java.util.Arrays的源码注释就能看到这一点这也是一个很有说服力的回答素材。2. 三个O(n²)入门算法别看不起它们是最好的教学样本2.1 冒泡排序交换次数的艺术与提前退出优化冒泡的核心动作只有一句话相邻两个元素比大小大的往后挪。每一轮走完当前未排序区间里最大的元素会被冒到末尾。朴素写法是嵌套两层循环外层控制轮数内层负责比较和交换。public static void bubbleSort(int[] arr) { 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]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped true; } } if (!swapped) break; } }这段代码有两个优化点值得讲。第一个是swapped标志位如果某一轮一次交换都没发生说明数组已经有序可以直接跳出。这一个标志位把最好情况从O(n²)拉到了O(n)代价是每次比较多一次布尔赋值实测下来基本无感。第二个优化点是内层循环的上界n - 1 - i因为后面i个位置已经是有序的最大值了再比较纯属浪费。很多人写的时候偷懒写成n - 1算法结果正确但多做了一倍的无效比较。这种结果对但效率差的写法在面试里是会被扣分的因为它说明你没理解每轮结束后数组的状态。对了交换操作我用的是临时变量而不是位运算异或那一套。网上流传的a ^ b; b ^ a; a ^ b;虽然看起来高级但有两个坑一是当a和b指向同一个位置时也就是自己和自己交换会直接清零二是可读性差。生产代码里别炫技。2.2 选择排序一次交换换一个最小值选择排序的思路是每一轮在未排序区间里找到最小值的下标然后和未排序区间的第一个位置交换。它的交换次数最多只有n-1次这个特性在某些写操作很贵的场景下是有意义的比如元素是存储在闪存上、每次写入都有损耗。public static void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) minIdx j; } if (minIdx ! i) { int tmp arr[i]; arr[i] arr[minIdx]; arr[minIdx] tmp; } } }这里if (minIdx ! i)这个判断不是必须的但加上能省掉一次自交换。更重要的是理解它为什么不稳定假设数组是[5a, 5b, 2]第一轮找到最小值2和第一个位置的5a交换数组变成[2, 5b, 5a]两个5的相对顺序被打乱了。这个例子我建议你在面试时直接说出来比选择排序不稳定六个字有说服力得多。选择排序还有一个特点是它的比较次数固定是n(n-1)/2和数据初始状态完全无关。也就是说一个已经有序的数组和一个完全逆序的数组选择排序的耗时一模一样。这和冒泡、插入形成鲜明对比。2.3 插入排序小数组场景下的隐形王者插入排序是这三个里唯一在工业代码里被大量使用的。它的逻辑像打扑克摸牌左手是已排好序的牌堆右手摸一张新牌从牌堆末尾往前找位置插进去。public static void insertionSort(int[] arr) { for (int i 1; i arr.length; 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; } }注意这里用的是挪位而不是交换arr[j 1] arr[j]把元素整体右移最后把cur放到空出来的位置。这个写法的赋值次数比反复交换少很多是插入排序快的一个原因。插入排序最重要的特性是它对接近有序的数据极其敏感。如果数组已经基本有序内层while循环几乎不执行整体接近O(n)。JDK的Arrays.sort在数组长度小于47不同版本阈值略有差异时会退化成插入排序TimSort在归并到小片段时也会切插入排序就是因为这个特性。所以下次有人问你插入排序是不是没用你可以直接把这个工程事实甩出去。提示插入排序的哨兵优化是很多教材里的加分项。把while (j 0 arr[j] cur)拆成先找位置再判断可以减少一次边界比较但在Java里取数组越界的代价很小这个优化收益有限了解即可别为了它牺牲可读性。3. 进阶四件套希尔、归并、快排、堆排3.1 希尔排序给插入排序装上跳跃引擎插入排序慢在哪慢在它每次只能把元素往前挪一格。如果一个很小的元素在数组末尾它要挪n次才能到前面。希尔排序的思路就是先做几轮大步长的插入排序让元素能一次跨很远等数组大致有序了再用步长1的插入排序收尾。public static void shellSort(int[] arr) { int n arr.length; for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int cur arr[i]; int j i - gap; while (j 0 arr[j] cur) { arr[j gap] arr[j]; j - gap; } arr[j gap] cur; } } }这段代码和插入排序几乎是同一份只是把所有的1换成了gap这也是它被称为增量插入排序的原因。关键问题是增量序列怎么选我这里用的是最简单的折半序列n/2, n/4, ..., 1它的最坏情况仍然是O(n²)。常见的更好选择是Hibbard序列1, 3, 7, 15, ...即2^k - 1最坏能到O(n^1.5)还有Sedgewick序列实践表现更好但计算稍复杂。这个知识点在面试里属于答出来加分、答不出来不减分的层级但如果面试官追问希尔排序的复杂度到底是多少你答取决于增量序列折半序列最坏O(n²)Hibbard是O(n^1.5)这个回答的含金量就完全不一样了。希尔排序是不稳定的原因很简单相同的元素可能被分到不同的增量组里各自移动后相对顺序就乱了。3.2 归并排序分治与稳定性的正解归并排序的骨架是分而治之把数组从中间劈成两半各自排好再把两个有序数组合并成一个。合并的过程需要一块额外的辅助数组这是它O(n)空间开销的来源。public static void mergeSort(int[] arr) { if (arr.length 2) return; int[] tmp new int[arr.length]; sort(arr, tmp, 0, arr.length - 1); } private static void sort(int[] arr, int[] tmp, int left, int right) { if (left right) return; int mid left (right - left) / 2; sort(arr, tmp, left, mid); sort(arr, tmp, mid 1, right); merge(arr, tmp, left, mid, right); } private static void merge(int[] arr, int[] tmp, int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { tmp[k] arr[i] arr[j] ? arr[i] : arr[j]; } while (i mid) tmp[k] arr[i]; while (j right) tmp[k] arr[j]; System.arraycopy(tmp, left, arr, left, right - left 1); }两个细节值得抠。第一mid left (right - left) / 2这种写法是为了防溢出虽然Java的int范围下(left right) / 2在数组长度不可能超2^31的情况下其实不会溢出但这个写法是通用习惯写出来面试官会认为你知道这回事。第二合并时判断用的是arr[i] arr[j]而不是这个等号就是归并排序稳定性的全部秘密所在。当左右两边出现相同值时优先取左边的保持原有相对顺序。很多人写归并从来没注意过这个等号被问到归并为什么稳定时会愣住。归并排序的实际价值在于它是外排序的基础。当数据大到内存放不下时你会把文件切成若干块分别排序写回磁盘然后再做多路归并。这个思路在数据库的排序实现、日志归并处理里到处都是。3.3 快速排序pivot的选择决定了你的下限快排的核心是分区partition选一个基准值把小于它的扔左边大于它的扔右边然后对左右两边递归。它的平均性能是所有内排序里最好的因为它的常数因子小、内存访问局部性好。最经典的Lomuto分区写法public static void quickSort(int[] arr, int lo, int hi) { if (lo hi) return; int p partition(arr, lo, hi); quickSort(arr, lo, p - 1); quickSort(arr, p 1, hi); } private static int partition(int[] arr, int lo, int hi) { // 随机化pivot防止有序数组导致退化 int rand lo (int) (Math.random() * (hi - lo 1)); swap(arr, rand, hi); int pivot arr[hi]; int i lo; for (int j lo; j hi; j) { if (arr[j] pivot) { swap(arr, i, j); } } swap(arr, i, hi); return i; } private static void swap(int[] arr, int i, int j) { int t arr[i]; arr[i] arr[j]; arr[j] t; }这里我特意加了随机化pivot。原因是如果每次固定取最右边的元素作为pivot那么对一个已经有序的数组每次分区都会把区间分成0和n-1两部分递归深度变成n时间复杂度退化到O(n²)同时栈深度也会爆。这不是理论问题早期很多系统的快排就是这么被有序数据打崩的。随机化之后退化概率降到可以忽略。当数组里有大量重复元素时两路分区也会退化等于pivot的元素全被分到一边。这时候要用三路快排把数组分成小于、等于、大于三段public static void quickSort3Way(int[] arr, int lo, int hi) { if (lo hi) return; int pivot arr[lo (int) (Math.random() * (hi - lo 1))]; int lt lo, gt hi, i lo; while (i gt) { if (arr[i] pivot) swap(arr, lt, i); else if (arr[i] pivot) swap(arr, i, gt--); else i; } quickSort3Way(arr, lo, lt - 1); quickSort3Way(arr, gt 1, hi); }三路快排对大量重复键的数据比如按年龄段排序、按状态码排序性能提升非常明显因为重复元素不会再参与后续递归。这也是JDK对基本类型排序的思路来源之一。3.4 堆排序用数组模拟一棵完全二叉树堆排序的独特之处在于它是唯一一个既保证O(nlogn)最坏复杂度、又只用O(1)额外空间的算法。它的短板是缓存不友好——访问模式是跳跃的父节点和子节点下标相差一倍CPU缓存命中率低所以在实测中通常比快排慢一截。先建立下标映射关系对下标i左孩子是2i1右孩子是2i2父节点是(i-1)/2。这个映射是堆用数组存储的全部基础。public static void heapSort(int[] arr) { int n arr.length; // 建堆从最后一个非叶子节点开始下沉 for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n); } // 依次把堆顶最大值换到末尾 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 size) { while (true) { int left 2 * i 1, right left 1, max i; if (left size arr[left] arr[max]) max left; if (right size arr[right] arr[max]) max right; if (max i) break; swap(arr, i, max); i max; } }建堆为什么从n/2 - 1开始因为下标大于等于n/2的节点全都是叶子节点叶子本身就是一个合法的堆不需要调整。这个细节是很多人写堆排序时的第一个卡点。建堆的复杂度是O(n)而不是O(nlogn)这个结论经常被误解。直觉上的解释是大部分节点都在底层下沉的层数很少把所有节点的下沉代价加起来是一个收敛的级数。严格的数学推导你可以去翻《算法导论》面试时答建堆是O(n)因为底层节点多但下沉距离短基本就够了。堆这个结构本身的应用比堆排序更广优先队列、Top K问题、定时任务调度、带优先级的消息队列全都是堆的变体。所以哪怕你一辈子不手写堆排序理解堆的调整逻辑也是划算的。4. 三种线性时间排序计数、桶、基数4.1 计数排序用空间换时间的第一课计数排序跳出了比较这个框架。既然元素都是整数那我直接统计每个值出现了几次然后按值从小到大把它们铺回去不就行了整个过程没有任何两个元素之间的比较。public static int[] countingSort(int[] arr) { int max arr[0], min arr[0]; for (int v : arr) { if (v max) max v; if (v min) min v; } int range max - min 1; int[] count new int[range]; for (int v : arr) count[v - min]; // 前缀和得到每个值在结果中的结束位置 for (int i 1; i range; i) count[i] count[i - 1]; int[] res new int[arr.length]; // 倒序遍历保证稳定性 for (int i arr.length - 1; i 0; i--) { res[--count[arr[i] - min]] arr[i]; } return res; }这段代码有两个必须理解的细节。第一我用了min做偏移因为数组可能有负数如果直接用值当下标会越界。第二最后一步是倒序遍历这决定了稳定性——倒着填相同值的元素后出现的先被放到更靠后的位置最终顺序和原数组一致。如果改成正序遍历结果依然正确但稳定性就没了。计数排序的致命限制在于range。如果数据是[1, 100000000]两个元素你要开一个一亿长度的数组内存直接炸。所以它只适合数据范围集中的场景比如学生成绩0-100、年龄、状态码。4.2 桶排序与基数排序分工不同的两条路桶排序可以理解为计数排序的泛化版本不再给每个值开一个格子而是把值域均分成若干个区间桶元素按区间丢进对应的桶桶内各自排序最后按桶的顺序拼起来。public static void bucketSort(double[] arr, int bucketCount) { ListListDouble buckets new ArrayList(bucketCount); for (int i 0; i bucketCount; i) buckets.add(new ArrayList()); for (double v : arr) { int idx (int) (v * bucketCount); if (idx bucketCount) idx bucketCount - 1; buckets.get(idx).add(v); } int k 0; for (ListDouble bucket : buckets) { Collections.sort(bucket); for (double v : bucket) arr[k] v; } }桶排序的性能高度依赖数据分布。如果数据均匀分布每个桶里元素数量差不多整体接近O(n)。但如果数据全部挤在一个桶里退化成对这个桶做一次完整的排序最坏是O(n²)。所以桶排序的核心工程问题是桶的数量怎么定和数据分布是否均匀这两点答不上来说明你只是在背代码。基数排序走的是另一条路按位排序从最低位到最高位每一位用一次稳定的计数排序。因为每一位的排序是稳定的所以低位排好的顺序在高位相同时会被保留下来。public static void radixSort(int[] arr) { int max Arrays.stream(arr).max().getAsInt(); for (int exp 1; max / exp 0; exp * 10) { int[] count new int[10]; int[] out new int[arr.length]; for (int v : arr) count[(v / exp) % 10]; for (int i 1; i 10; i) count[i] count[i - 1]; for (int i arr.length - 1; i 0; i--) { int d (arr[i] / exp) % 10; out[--count[d]] arr[i]; } System.arraycopy(out, 0, arr, 0, arr.length); } }基数排序对负数的处理需要额外小心上面这段只适用于非负整数。如果要支持负数通常的做法是把数组拆成正负两部分分别排或者做一次整体偏移。三种线性排序的共同前提是数据有结构可利用——要么范围小要么能拆位要么能分桶。理解了这个前提你就不会在面试里说出计数排序比快排好应该都用计数排序这种话了。5. 演示动画怎么做把算法过程看见5.1 动画的三个核心要素状态快照、延时、颜色语义看静态代码理解算法和自己动手把过程画出来是两个层次的认知。我做过好几版排序动画踩过的坑总结下来一个能用的动画必须解决三件事。第一是状态快照。排序过程中变量太多你不能把整个数组状态都画出来。要挑关键状态当前比较的两个下标、当前选中的pivot、已经确定位置的元素区间。这些才是观众想看的。第二是延时控制。延时太快人眼跟不上太慢又等得烦躁。我的经验是数组长度50左右时每帧延时30到60毫秒比较舒服长度20以内可以放到150毫秒。而且延时最好做成可调参数因为不同的人接受度不一样。第三是颜色语义。颜色不能乱用必须有稳定含义。我的约定是蓝色是待排序元素红色是当前正在比较或交换的两个元素绿色是已经确定最终位置的元素橙色是pivot。这个约定一旦定下来整段动画不改观众看两眼就能自己读懂状态。5.2 用Java Swing写一个排序可视化器Java做动画最直接的选择还是Swing不用引入任何第三方库一个继承JPanel的类就够了。核心结构是数组数据放在面板里paintComponent负责把数组画成柱状图排序逻辑在后台线程跑每次交换或比较后调用repaint()并sleep一小会。import javax.swing.*; import java.awt.*; import java.util.Random; public class SortPanel extends JPanel { private final int[] data; private volatile int markA -1; private volatile int markB -1; private volatile int settledFrom -1; private static final int W 900; private static final int H 420; public SortPanel(int size) { data new int[size]; Random r new Random(20240101L); for (int i 0; i size; i) { data[i] 15 r.nextInt(H - 60); } setPreferredSize(new Dimension(W, H)); setBackground(Color.WHITE); } Override protected void paintComponent(Graphics g) { super.paintComponent(g); int barW Math.max(2, W / data.length); for (int i 0; i data.length; i) { if (i markA || i markB) g.setColor(new Color(220, 60, 60)); else if (settledFrom 0 i settledFrom) g.setColor(new Color(60, 160, 90)); else g.setColor(new Color(70, 130, 180)); g.fillRect(i * barW, H - data[i], barW - 1, data[i]); } } public synchronized void swap(int i, int j) { markA i; markB j; repaint(); int t data[i]; data[i] data[j]; data[j] t; sleep(40); markA -1; markB -1; } public void markSettled(int from) { settledFrom from; repaint(); } private void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } public int[] data() { return data; } }这段代码有几个设计决策值得说明。markA和markB声明成volatile是因为它们会被后台排序线程写、被EDT事件分发线程读。严格来说Swing的规范要求所有UI相关状态都在EDT里操作但做演示动画时为了代码简洁用volatile保证可见性、只在paint里读实际跑起来不会有问题。如果你想让代码更正规可以用SwingUtilities.invokeLater把repaint包起来。settledFrom这个变量用得很省事只要记录从哪个下标开始已经排好就能一次性把它们画成绿色不用维护一个布尔集合。延时我放在swap方法里而不是放在排序算法内部。这样做的好处是排序算法本身保持纯净可视化只是插进去的一层。启动类长这样public class VisualizerApp { public static void main(String[] args) { JFrame frame new JFrame(排序可视化演示); SortPanel panel new SortPanel(60); frame.add(panel); frame.pack(); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.setVisible(true); new Thread(() - { int[] arr panel.data(); // 这里替换成你想看的算法 for (int i 0; i arr.length - 1; i) { for (int j 0; j arr.length - 1 - i; j) { if (arr[j] arr[j 1]) { panel.swap(j, j 1); } } panel.markSettled(arr.length - i); } }).start(); } }把中间那段换成快排或者堆排的循环就能看到完全不同的视觉节奏。我自己的感受是冒泡的动画看起来像一排柱子在慢慢往右滑归并的动画是分块变绿快排的动画是红色标记乱跳但整体很快收敛。这种看到算法性格的体验是看代码得不到的。提示如果你要把动画录成视频或者GIF记得把sleep调大一点比如120毫秒并且固定随机种子否则每次跑出来的数据分布都不一样录像会不连贯。5.3 动画之外用计数器和耗时做量化对比动画解决的是看得懂但工程选型需要的是量得出。我在同一套代码里加了一对计数器比较次数和交换/赋值次数。这两个数字比耗时更能说明问题因为耗时会受机器负载影响而操作次数是算法的固有属性。算法10000个随机数比较次数约10000个随机数移动次数约冒泡排序5000万2500万选择排序5000万1万插入排序2500万2500万希尔排序约200万约150万归并排序12万24万快速排序15万5万这张表里最有意思的是选择排序那一行它的比较次数和冒泡一样多但移动次数几乎可以忽略。所以当你写操作代价极高的时候选择排序反而值得考虑。另一个有意思的是插入排序它在随机数据下的移动次数和冒泡相当但对接近有序的数据会骤降到几千次这个弹性是冒泡和选择都没有的。6. 实测数据与常见坑排查6.1 我用10万随机数跑了8种算法我在同一台机器上用JMH之外的简单计时方式跑了一轮数组长度10万随机整数每轮前先跑一次预热。结论大致是快排三路随机pivot最快大概18毫秒归并紧随其后25毫秒左右堆排60毫秒上下希尔排80到150毫秒取决于增量序列插入排序因为数据量太大直接飙到十几秒冒泡和选择更不用说几十秒级别我中途就掐掉了。这个结果基本符合理论预期但有几个反直觉的点值得记下来。第一堆排序理论上和快排同为O(nlogn)实测慢三倍以上。原因就是前面提到的缓存局部性——快排的分区是顺序扫描CPU预取器非常吃这一套堆排的父子跳转把预取器完全打乱了。这说明复杂度分析只是第一层常数因子和内存访问模式才是决定实际性能的关键。第二如果数据本身就接近有序插入排序在小数组上能直接吊打快排。我在长度小于30的数组上用插入排序替代快排的递归出口整体耗时能降一到两个百分点。JDK就是这么干的这不是玄学。第三Arrays.sort永远比你自己手写的快排快。除了双轴快排本身更优JDK还用了哨兵、插入排序阈值、以及针对小数组的手工展开。手写代码的价值在于理解不在于替代标准库。6.2 常见问题速查表症状大概率原因处理方式快排遇到有序数组变得极慢固定pivot导致分区极度不平衡随机化pivot或三数取中快排递归报StackOverflowError递归深度退化到n随机化pivot或改成显式栈的迭代写法数组有大量重复值时快排很慢两路分区把相等的元素都挤到一边换三路分区归并排序结果不稳定合并时用了而不是左端优先时用计数排序直接OOM数据值域过大辅助数组开不出来先做值域检查或改用桶排序基数排序结果错乱某一位的排序不稳定或没处理负数检查计数排序是否为稳定实现负数单独处理堆排序结果差一个元素没排好建堆从n/2开始而不是n/2 - 1最后一个非叶子节点下标是n/2 - 1排序后部分元素位置随机交换用了异或写法且i等于j用临时变量或交换前判断i ! j这张表里的每一条我自己都踩过。尤其是第一行的随机化pivot我是有一次用快排处理一批日志时间戳本来就有序时发现耗时从毫秒级跳到秒级才回过头去补的。6.3 面试八股里的排序陷阱现在的Java面试八股文里排序相关的题目已经形成了几套固定套路但陷阱也藏在固定套路里。我把被问得最多、也最容易答错的几个问题整理一下。第一个经典问题是快排和归并的区别。标准答案是快排不稳定、原地、平均更快归并稳定、需要额外空间、适合外排序和链表。但面试官如果追问为什么链表适合归并你要能答出链表的归并可以做到O(1)额外空间因为合并两个有序链表只需要改指针不需要额外的数组。这个点很多人答不上来。第二个是JDK的Arrays.sort用什么算法。正确答案是基本类型用双轴快排DualPivotQuicksort对象数组用TimSort。追问为什么区分答案在于稳定性——基本类型没有两个相等的元素谁在前这种语义问题而对象数组有所以必须保证稳定。这个回答能直接把话题从八股引到工程权衡面试官一般都会给高分。第三个是时间复杂度O(nlogn)是哪里来的。这个问题考验的是你懂不懂信息论的角度n个元素的排列有n!种可能每次比较最多区分两种情况所以至少要log2(n!)次比较而log2(n!)约等于nlogn。这个下界证明能说出来说明你不是在背数字。第四个是线程池里任务排队需要排序吗这类场景问题。答案是不需要——线程池用的是阻塞队列追求的是入队出队的O(1)而不是全排序。这种题考查的是你能不能跳出算法本身看到实际工程里排序和优先级调度的区别。我在准备面试的时候有个习惯每学一个算法强迫自己想三个它被真实使用的地方。快排是JDK基本类型排序和内存受限的排序场景归并是TimSort和外排序堆是优先队列和Top K计数排序是成绩统计和直方图。想不出来使用场景的算法多半你也没真懂。最后分享一个我自己用了好几年的练习方法拿一张纸把十种算法各自的核心循环默写一遍写完对着编译器跑一遍边界用例——空数组、单元素、全相同、已有序、完全逆序这五种。能全过说明你对边界是真的有感觉了而不是记住了代码的形状。