1. 为什么用动画拆解排序算法这件事值得认真做排序算法是计算机科学里最基础也最容易被低估的一块内容。很多人刷题的时候背了快排和归并的模板面试也能写出来但一旦被追问“为什么快排最坏是O(n²)”“堆排序的建堆为什么是O(n)”“希尔排序的增量序列到底怎么选”就开始含糊其辞。我自己带过几个刚入行的同学发现一个共性问题他们能写出代码但脑子里没有“数据在内存里怎么一步步挪动”的画面。动画恰好能补上这一环。这个项目标题里的“下”字很关键说明前面已经聊过一部分经典算法下半场通常覆盖的是希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序这几类。相比上半场那些冒泡、选择、插入的“入门三件套”下半场这些算法才是真正拉开差距的地方——它们要么在时间复杂度上做了质变从O(n²)降到O(n log n)要么在特定场景下能做到线性时间计数、桶、基数。用Java实现它们不只是翻译伪代码还要处理泛型、比较器、递归深度、内存开销这些工程细节。我写这篇东西的目的很直接把每个算法的动画思维翻译成可运行的Java代码同时把那些动画里看不出来的坑点讲清楚。比如归并排序的临时数组到底开多大、快排的三路划分什么时候比双路更划算、堆排序的siftDown边界条件为什么容易写错、基数排序的负数怎么处理。这些细节在教科书里往往一笔带过但实际写代码的时候一个边界条件就能让你debug半小时。适合谁看如果你已经能写出冒泡和插入排序想进一步搞懂那些“看起来很快”的算法到底快在哪这篇就是给你准备的。如果你正在准备技术面试需要把排序算法的原理、复杂度、稳定性、适用场景串成一条线这里的内容可以直接拿去当复习提纲。如果你只是好奇“动画里那些柱子跳来跳去到底对应代码的哪一行”我也会在关键步骤标注出行号级别的对应关系。2. 下半场七个算法的整体设计思路2.1 从比较排序到非比较排序的分水岭上半场的冒泡、选择、插入本质上都是比较排序——通过两两比较来决定元素顺序。比较排序有一个理论下界O(n log n)。这个下界不是随便说说的可以用决策树模型证明n个元素有n!种排列每次比较最多区分两种情况所以至少需要log₂(n!)次比较而log₂(n!)约等于n log n。这意味着任何基于比较的排序算法平均情况下都不可能比O(n log n)更快。下半场的七个算法里希尔、归并、快排、堆排仍然属于比较排序它们的目标是逼近这个下界。而计数、桶、基数则跳出了比较的框架利用元素本身的数值特征比如范围有限、可以按位拆分来达到线性时间。这个分水岭是理解下半场算法的关键前四个是在“比较”这个约束下做到极致后三个是换了一条赛道。我在设计Java实现的时候刻意保持了接口的一致性所有排序类都实现同一个Sorter接口接收一个int[]数组原地排序或者返回新数组。这样做的好处是方便写一个统一的测试框架用随机数据、有序数据、逆序数据、大量重复数据四种场景去跑对比它们的实际耗时和交换次数。动画里看到的“柱子移动”对应到代码里就是数组元素的读写统计这些操作的次数能帮你直观感受不同算法的常数因子差异。2.2 递归与迭代的取舍逻辑归并排序和快速排序天然适合递归实现因为它们的子问题结构非常清晰把数组分成两半分别排序再合并。递归写出来的代码短、可读性强和动画里的分治过程一一对应。但递归有两个现实问题一是递归深度快排在极端情况下比如每次选到最小或最大元素作为基准递归深度会达到n对于百万级数组可能栈溢出二是函数调用开销虽然现代JVM对递归有一定优化但在性能敏感的场合迭代版本往往更可控。我的做法是归并排序提供递归和迭代两个版本递归版用于教学和理解迭代版用于实际生产。快速排序则重点讲三路划分的递归实现同时给出一个“尾递归优化”的技巧——每次递归只对较小的一半继续递归较大的一半用循环处理这样最坏递归深度降到O(log n)。堆排序本身就是迭代的希尔排序也是迭代的计数、桶、基数都是迭代的所以下半场里真正需要纠结递归的还是归并和快排这两个。2.3 空间换时间的尺度把握归并排序需要O(n)的辅助数组计数排序需要O(k)的计数数组k是数值范围桶排序需要O(nk)的桶空间基数排序需要O(nb)的临时空间b是基数。这些额外的内存开销在动画里是看不见的但实际写代码时必须考虑。比如对一个一亿个整数的数组排序归并排序的辅助数组就是400MB假设每个int 4字节如果内存紧张可能就得换堆排序或者快排。我的经验是数据量小于十万随便用哪个都行十万到千万级别优先考虑快排或堆排千万以上且数值范围集中计数或基数排序的优势才真正体现出来。这个尺度不是绝对的还要看数据分布。如果数据本身已经基本有序插入排序甚至比快排还快因为它的最好情况是O(n)。所以我在每个算法的实现里都加了一个“适用场景”的注释方便你根据实际情况选择。3. 希尔排序的动画拆解与Java实现细节3.1 增量序列的选择为什么影响巨大希尔排序的核心思想是先让数组中相隔某个“增量”的元素有序然后逐步缩小增量最后当增量为1时整个数组已经基本有序再做一次插入排序就会很快。动画里通常会用不同颜色的柱子表示不同增量下的分组你能看到随着增量缩小数组逐渐从混乱变得“局部有序”最后一步插入排序几乎不需要移动元素。增量序列的选择直接决定希尔排序的时间复杂度。最原始的是希尔本人提出的n/2序列每次把增量除以2直到1。这个序列的最坏时间复杂度是O(n²)虽然比插入排序好但并没有质变。后来有人提出了Knuth序列1, 4, 13, 40, 121...递推公式是h 3h 1这个序列的最坏时间复杂度是O(n^(3/2))。还有更激进的Sedgewick序列能把最坏情况降到O(n^(4/3))。我在Java实现里默认用Knuth序列因为它在大多数数据集上表现稳定而且生成增量的代码很简单。public class ShellSorter implements Sorter { Override public void sort(int[] arr) { int n arr.length; // 生成Knuth增量序列 int h 1; while (h n / 3) { h 3 * h 1; } // 按增量分组进行插入排序 while (h 1) { for (int i h; i n; i) { int temp arr[i]; int j i; while (j h arr[j - h] temp) { arr[j] arr[j - h]; j - h; } arr[j] temp; } h / 3; } } }这段代码里有一个容易写错的地方while (h n / 3)这个条件。如果写成h n生成的增量可能超过数组长度导致后续循环里j - h越界。用n / 3是为了保证最大的增量不超过n的三分之一这样第一轮分组时每组至少有三个元素排序才有意义。这个细节在动画里看不出来但写代码的时候不注意就会数组越界。3.2 希尔排序的稳定性与适用场景希尔排序是不稳定的。原因很简单相同的元素可能被分到不同的组里在组内排序时相对顺序可能改变。比如数组[2a, 2b, 1]增量取2时2a和1一组排序后变成[1, 2b, 2a]两个2的相对顺序就反了。如果你需要稳定排序希尔排序不能直接用。那什么时候用希尔排序我的经验是数据量在几千到几万之间且对稳定性没有要求同时希望代码比快排简单、比插入排序快。希尔排序的代码量只有快排的三分之一而且不需要递归没有栈溢出的风险。在一些嵌入式场景或者对代码体积敏感的地方希尔排序是一个很务实的折中方案。实测下来对一万个随机整数排序Knuth序列的希尔排序比插入排序快大约20倍比归并排序慢大约30%但代码量少了一半。注意希尔排序的性能对增量序列非常敏感。如果你自己设计增量序列一定要保证最后一个增量是1否则数组不会完全有序。另外增量序列最好是递减到1的不要出现跳跃或者重复。4. 归并排序的分治动画与工程化实现4.1 分治的递归树在动画里长什么样归并排序的动画通常是这样先把数组从中间劈开左右两半分别显示为两组柱子然后递归地继续劈直到每组只剩一个柱子。接着开始合并两个有序的小组比较头部元素小的先放到临时数组里最后把临时数组复制回原数组。动画里你会看到柱子从底部一个个被“取走”放到新的位置这个过程就是归并的核心。递归树的高度是log n每一层的合并操作总共处理n个元素所以总时间复杂度是O(n log n)。这个结论在动画里很直观每一层你都能看到所有柱子被处理一遍而层数是log n。但动画不会告诉你的是归并排序需要额外的O(n)空间而且这个空间是在递归过程中反复分配的。如果每次合并都new一个临时数组会产生大量的对象分配和垃圾回收压力。我的做法是在排序开始前一次性分配一个和原数组等大的辅助数组然后在递归过程中复用这个数组的不同区间。public class MergeSorter implements Sorter { Override public void sort(int[] arr) { int[] temp new int[arr.length]; mergeSort(arr, temp, 0, arr.length - 1); } private void mergeSort(int[] arr, int[] temp, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, temp, left, mid); mergeSort(arr, temp, mid 1, right); // 优化如果已经有序跳过合并 if (arr[mid] arr[mid 1]) return; merge(arr, temp, left, mid, right); } private void merge(int[] arr, int[] temp, int left, int mid, int right) { System.arraycopy(arr, left, temp, left, right - left 1); int i left, j mid 1; for (int k left; k right; k) { if (i mid) { arr[k] temp[j]; } else if (j right) { arr[k] temp[i]; } else if (temp[i] temp[j]) { arr[k] temp[i]; } else { arr[k] temp[j]; } } } }这段代码里有两个优化点值得说。第一个是if (arr[mid] arr[mid 1]) return;如果左半部分的最大值小于等于右半部分的最小值说明整个区间已经有序不需要合并。这个判断在数据部分有序时能省掉大量操作。第二个是用System.arraycopy来复制到临时数组这比手动循环快因为JVM对这个方法有 intrinsic 优化底层会用内存拷贝指令。4.2 迭代版归并排序的边界处理递归版归并排序的代码很优雅但递归深度是log n对于千万级数组来说log₂(10⁷)约等于23其实不算深栈溢出风险不大。但如果你在面试里被要求写非递归版本或者你想避免递归调用的开销迭代版就派上用场了。迭代版的核心是从步长1开始两两合并相邻的子数组然后步长翻倍直到步长超过数组长度。public void sortIterative(int[] arr) { int n arr.length; int[] temp new int[n]; for (int size 1; size n; size * 2) { for (int left 0; left n - size; left 2 * size) { int mid left size - 1; int right Math.min(left 2 * size - 1, n - 1); merge(arr, temp, left, mid, right); } } }迭代版的坑在于边界条件。left n - size这个条件保证至少有两个子数组可以合并。如果写成left n当left size超过数组长度时mid会越界。right用Math.min来限制防止最后一个子数组不完整时越界。这些边界在动画里是看不到的因为动画通常假设数组长度是2的幂但实际数据不会这么巧。提示归并排序是稳定的因为合并时如果左右元素相等优先取左边的。这个特性在需要保持相同元素原始顺序的场景下很重要比如对对象数组按某个字段排序时希望相同字段值的对象保持原有顺序。5. 快速排序的动画逻辑与三路划分实战5.1 基准选择如何决定动画的“分裂”效果快速排序的动画通常是这样选一个基准元素通常是最后一个或第一个然后用两个指针从两端向中间扫描把小于基准的放到左边大于基准的放到右边最后把基准放到正确位置。这个过程叫分区partition。动画里你会看到指针像两把扫帚一样把柱子往两边扫基准元素最后“落”在中间然后左右两段分别递归。基准的选择直接影响分区的平衡性。如果每次选到的基准都是中位数递归树是平衡的时间复杂度O(n log n)。如果每次选到最小或最大元素递归树退化成链表时间复杂度O(n²)。动画里通常展示的是理想情况但实际数据往往有各种分布。我的做法是三数取中取左端、中间、右端三个元素的中位数作为基准这样在大多数情况下能避免极端不平衡。private int medianOfThree(int[] arr, int left, int right) { int mid left (right - left) / 2; if (arr[left] arr[mid]) swap(arr, left, mid); if (arr[left] arr[right]) swap(arr, left, right); if (arr[mid] arr[right]) swap(arr, mid, right); // 此时arr[mid]是中位数把它换到right-1位置作为基准 swap(arr, mid, right - 1); return arr[right - 1]; }三数取中还有一个好处它顺便把左端、中间、右端三个元素排好了序这样在后续分区时左端元素一定小于等于基准右端元素一定大于等于基准分区循环可以从left1和right-2开始减少两次边界判断。5.2 三路划分为什么能处理大量重复元素标准的双路快排在遇到大量重复元素时性能会退化。比如数组里所有元素都相等双路快排每次分区只能确定一个元素的位置递归深度还是n时间复杂度O(n²)。三路划分把数组分成三部分小于基准、等于基准、大于基准。等于基准的部分不需要再递归直接跳过。这样在重复元素很多时递归的区间会大幅缩小。private void quickSort3Way(int[] arr, int left, int right) { if (left right) return; // 三数取中 int pivot medianOfThree(arr, left, right); int lt left, gt right, i left 1; while (i gt) { if (arr[i] pivot) { swap(arr, lt, i); } else if (arr[i] pivot) { swap(arr, i, gt--); } else { i; } } quickSort3Way(arr, left, lt - 1); quickSort3Way(arr, gt 1, right); }这段代码里lt指向小于区的下一个位置gt指向大于区的前一个位置i是当前扫描位置。当arr[i] pivot时交换lt和i然后lt和i都右移当arr[i] pivot时交换i和gtgt左移但i不动因为换过来的元素还没检查当arr[i] pivot时i直接右移。这个逻辑在动画里会显示成三个区域逐渐扩大等于区在中间“吃掉”重复元素。注意三路划分的递归调用只对小于区和大于区进行等于区不参与递归。这是它比双路快排在重复元素场景下快得多的原因。实测对一百万个随机0到10之间的整数排序三路快排比双路快排快大约5倍。6. 堆排序的树形动画与siftDown边界6.1 建堆为什么是O(n)而不是O(n log n)堆排序的动画通常分两个阶段第一阶段把数组调整成一个大顶堆第二阶段反复把堆顶元素和末尾元素交换然后缩小堆的范围并重新调整。动画里你会看到一棵完全二叉树父节点总是大于等于子节点交换堆顶和末尾时最大的元素被“沉”到数组末尾。建堆的过程是从最后一个非叶子节点开始依次向前对每个节点执行siftDown。很多人以为建堆的时间复杂度是O(n log n)因为每个节点siftDown最多走log n层有n个节点。但实际上大部分节点都在树的底层siftDown的层数很少。精确计算下来建堆的总操作次数是O(n)。这个结论在动画里不容易看出来但你可以这样想叶子节点不需要siftDown倒数第二层每个节点最多走1层倒数第三层最多走2层……加权求和后总次数收敛到2n。private void buildHeap(int[] arr) { int n arr.length; for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n); } } private void siftDown(int[] arr, int i, int n) { while (true) { int left 2 * i 1; int right 2 * i 2; int largest i; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest i) break; swap(arr, i, largest); i largest; } }siftDown的边界条件是left n和right n这里的n是当前堆的有效范围不是整个数组长度。在排序阶段每次交换堆顶和末尾后n会减1所以siftDown的第二个参数要传当前的堆大小。这个细节如果写错会把已经排好的元素又搅乱。6.2 堆排序的适用场景与稳定性堆排序是不稳定的因为交换堆顶和末尾元素时相同元素的相对顺序可能改变。但堆排序有一个独特的优势最坏时间复杂度是O(n log n)且空间复杂度是O(1)。归并排序需要O(n)辅助空间快排最坏是O(n²)而堆排序在这两个维度上都很稳。所以在内存紧张且对最坏情况有要求的场景堆排序是首选。另一个实用场景是求Top K问题。如果你只需要数组中最大的K个元素不需要完全排序可以用一个大小为K的小顶堆遍历数组如果当前元素大于堆顶就替换堆顶并siftDown。这样时间复杂度是O(n log K)空间O(K)。这个技巧在面试里经常考比完全排序再取前K个高效得多。提示Java的PriorityQueue默认是小顶堆如果要大顶堆可以传Comparator.reverseOrder()。但PriorityQueue不支持直接修改堆中元素如果需要更新优先级得先删除再插入或者用索引堆。自己手写堆排序能让你更清楚这些操作的底层逻辑。7. 非比较排序三剑客的动画与实现7.1 计数排序的数值范围陷阱计数排序的动画很直观先统计每个数值出现的次数然后根据次数依次输出。动画里通常用一个计数数组下标对应数值值对应出现次数。然后遍历计数数组把数值按顺序填回原数组。整个过程不需要比较所以时间复杂度是O(n k)k是数值范围。但计数排序有一个硬性限制数值范围不能太大。如果数组里有一个元素是1000000计数数组就得开1000001个位置内存直接爆炸。所以计数排序只适合数值范围集中的场景比如年龄、分数、等级这种。我的实现里加了一个检查如果最大值和最小值的差超过数组长度的10倍就抛异常提示不适合用计数排序。public void sort(int[] arr) { if (arr.length 0) return; int min arr[0], max arr[0]; for (int num : arr) { if (num min) min num; if (num max) max num; } int range max - min 1; if (range arr.length * 10) { throw new IllegalArgumentException(数值范围过大不适合计数排序); } int[] count new int[range]; for (int num : arr) { count[num - min]; } int index 0; for (int i 0; i range; i) { while (count[i]-- 0) { arr[index] i min; } } }注意num - min这个偏移量。如果数组里有负数直接拿数值当下标会越界所以要先减去最小值把范围平移到从0开始。这个细节在动画里通常被忽略因为动画里的数据都是正整数。7.2 桶排序的分桶策略与链表实现桶排序可以看作是计数排序的升级版计数排序每个桶只装一个数值桶排序每个桶装一个区间。动画里你会看到元素被分配到不同的桶里每个桶内部再排序最后按桶的顺序拼接。桶排序的性能取决于分桶是否均匀如果所有元素都落到一个桶里就退化成桶内排序的复杂度。我的Java实现用ArrayListInteger[]来表示桶每个桶是一个动态数组。分桶策略用(num - min) * bucketCount / range来计算桶下标这样能保证元素均匀分布。桶内排序我直接调用Collections.sort因为桶内元素通常不多用TimSort足够快。public void sort(int[] arr) { if (arr.length 0) return; int min arr[0], max arr[0]; for (int num : arr) { if (num min) min num; if (num max) max num; } int bucketCount Math.max(1, arr.length / 10); ListInteger[] buckets new List[bucketCount]; for (int i 0; i bucketCount; i) { buckets[i] new ArrayList(); } int range max - min 1; for (int num : arr) { int idx (int) ((long) (num - min) * bucketCount / range); if (idx bucketCount) idx bucketCount - 1; buckets[idx].add(num); } int index 0; for (ListInteger bucket : buckets) { Collections.sort(bucket); for (int num : bucket) { arr[index] num; } } }这里有一个容易忽略的细节(num - min) * bucketCount可能会溢出int。如果num - min接近20亿乘以bucketCount就爆了。所以我用了(long)强制转换先做乘法再除以range。这个坑在处理大范围数据时很容易踩到。7.3 基数排序的按位分配与负数处理基数排序的动画通常是从最低位开始按每一位的数字把元素分配到0到9的桶里然后按桶的顺序收集再处理下一位。动画里你会看到元素在桶之间来回移动每一位处理完后数组就变得更有序一点。基数排序的时间复杂度是O(d * (n b))d是最大位数b是基数通常是10。基数排序最大的坑是负数。如果直接对负数取模得到的余数是负数不能直接当桶下标。我的处理方式是先把所有元素加上一个偏移量变成非负数排序后再减回去。或者更优雅的方式是把负数和非负数分开处理分别排序后再合并。我选择了偏移量方案因为代码更简洁。public void sort(int[] arr) { if (arr.length 0) return; int min arr[0]; for (int num : arr) { if (num min) min num; } // 加上偏移量变成非负数 for (int i 0; i arr.length; i) { arr[i] - min; } int max arr[0]; for (int num : arr) { if (num max) max num; } int[] temp new int[arr.length]; for (int exp 1; max / exp 0; exp * 10) { countingSortByDigit(arr, temp, exp); } // 减回偏移量 for (int i 0; i arr.length; i) { arr[i] min; } } private void countingSortByDigit(int[] arr, int[] temp, int exp) { int[] count new int[10]; for (int num : arr) { count[(num / exp) % 10]; } for (int i 1; i 10; i) { count[i] count[i - 1]; } for (int i arr.length - 1; i 0; i--) { int digit (arr[i] / exp) % 10; temp[--count[digit]] arr[i]; } System.arraycopy(temp, 0, arr, 0, arr.length); }注意countingSortByDigit里从后往前遍历原数组这是为了保证稳定性。如果从前往后遍历相同数字的元素相对顺序会反转基数排序就不稳定了。稳定性在基数排序里很重要因为每一位的排序结果要保留到下一次。8. 常见问题与排查技巧实录8.1 排序结果不对时的排查顺序写排序算法最让人抓狂的就是结果不对但又不报错。我的排查顺序是这样的先检查边界条件数组长度为0或1时是否直接返回left right的判断有没有写反再检查循环边界i n还是i nj 0还是j 0这些差一错误是排序bug的重灾区。然后检查交换逻辑swap(arr, i, j)有没有写错参数顺序临时变量有没有正确保存最后检查递归参数归并的mid和mid 1有没有搞混快排的递归区间有没有包含基准元素我建议在排序过程中加一个checkSorted方法每次递归返回后验证子数组是否有序。这样能快速定位到是哪一层递归出了问题。8.2 性能不如预期的常见原因有时候代码逻辑是对的但跑起来比预期慢很多。常见原因有问题现象可能原因排查方法快排比归并慢很多基准选择不当分区不平衡打印每次分区的左右长度归并排序内存飙升每次合并都new临时数组检查是否复用了辅助数组堆排序建堆特别慢siftDown的n参数传错确认建堆时n是数组长度计数排序OOM数值范围过大打印max-min和数组长度基数排序结果错乱没有从后往前遍历检查countingSortByDigit的循环方向提示用System.nanoTime()测量耗时的时候记得先跑几轮预热让JIT编译器把热点代码编译成机器码。直接测第一轮的结果往往偏慢因为解释执行的开销很大。8.3 面试中关于排序的高频追问面试官问排序算法通常不会只让你写代码还会追问一些延伸问题。我整理了几个高频追问和回答思路“快排的最坏情况是什么怎么避免”最坏是每次选到极值递归深度n时间O(n²)。避免方法是三数取中或随机选基准把最坏情况的概率降到极低。“归并排序为什么稳定快排为什么不稳定”归并合并时相等元素优先取左边所以稳定。快排分区时相等元素可能被交换到任意位置所以不稳定。“堆排序的建堆为什么是O(n)”因为大部分节点在底层siftDown的层数很少加权求和后是O(n)。可以画递归树解释。“计数排序能排负数吗”可以加偏移量把最小值平移到0。但要注意偏移量可能溢出。“Java的Arrays.sort()用的是什么排序”对基本类型用双轴快排对对象类型用TimSort。双轴快排是两个基准的三路划分TimSort是归并和插入的混合。9. 我在实际写这些排序时踩过的坑第一个坑是归并排序的临时数组复用。我一开始在merge方法里每次都new int[right - left 1]结果对一百万个元素排序时GC日志刷屏耗时是复用数组版本的3倍。后来改成在sort入口处分配一个和原数组等大的temp所有merge操作都往这个temp的对应区间里写性能立刻上来了。这个经验告诉我在递归算法里能复用的内存一定要复用否则GC的压力会吃掉算法本身的优势。第二个坑是快排的三数取中边界。我写medianOfThree的时候一开始没有把中位数换到right - 1位置导致分区循环的边界判断特别复杂经常数组越界。后来看了Sedgewick的写法把中位数换到right - 1这样left位置一定小于等于基准right位置一定大于等于基准分区循环可以从left 1和right - 2开始代码简洁了很多bug也少了。第三个坑是基数排序的负数偏移量溢出。有一次测试数据里有一个Integer.MIN_VALUE我给它加上偏移量后直接溢出成了正数排序结果完全错乱。后来改成用long来做偏移计算排序完再转回int才解决了这个问题。这个坑让我意识到处理边界值的时候一定要考虑数据类型的极限情况。第四个坑是希尔排序的增量序列生成。我一开始用h n / 2然后每次除以2结果对某些数据排序后数组不是完全有序的。排查了半天才发现当n是奇数时n / 2最后会变成0循环直接退出了最后一个增量不是1。后来改成Knuth序列用while (h n / 3) h 3 * h 1;生成保证最后一个增量一定是1问题才解决。这些坑在动画里都看不到因为动画展示的是理想情况下的算法流程不会告诉你内存分配、边界溢出、增量序列这些工程细节。但正是这些细节决定了你的代码能不能在实际项目里跑起来。