Java-sort

为什么 Java 的 Arrays.sort 对基本类型不直接用归并排序？

因为归并排序需要 O(n) 的辅助空间。基本类型通常不需要稳定性，快排的 Dual-Pivot 实现在 CPU 缓存利用率和内存占用上更具优势。

如果数据已经接近排好序了，哪种 O(n2) 算法会进化成 O(n)？

插入排序。因为它只需要进行最少量的比较，且几乎不需要移动元素。

选择排序在生产中几乎不用的核心原因是什么？

即使数据完全有序，它也会进行 O(n2) 次比较。它对数据的“既有秩序”完全不敏感，且是不稳定的。

快速排序在什么情况下会发生“降维打击”变成 O(n2)？

当数据已经有序或高度重复，且基准点（Pivot）选择极度糟糕（每次都选到最大/最小值）时，递归树会退化成单向链表。

堆排序相较于快排的优点是什么？

堆排序的最坏时间复杂度也是稳定的 O(nlogn)，且它是原地排序，不需要快排那样的递归栈空间。

归并排序的“空间换时间”体现在哪里？

体现在它需要一个和原数组同样大小的临时数组来完成 merge 操作，空间复杂度为 O(n)。

冒泡排序 (Bubble Sort)：相邻竞争的淘汰赛

• ​一句话核心​：“各扫门前雪。” 通过相邻两两比对，把最大的那个“显眼包”一步步推到最后。

• 生活化类比：操场排队。
  老师要求学生按身高排队。每个学生只看一眼右边的人，如果对方比自己矮，就互换位置。

  • ​比较过程​：对应代码中的 if (arr[j] > arr[j+1])​。

  • ​交换动作​：对应 swap​ 临时变量操作。

• ​关键矛盾​：如果没有这个机制，你可能需要一个拥有全局视野的超级计算机来指挥。但冒泡虽然简单，却极度​低效​。在数据量巨大时，每一轮都要进行大量无意义的微调，导致系统响应极慢。

选择排序 (Selection Sort)：执着的“全局猎头”

• ​一句话核心​：“只取当下最好。” 每一轮都扫描全场，只为了找出剩下的里面最小的那一个，并把它安放在指定位置。

• 生活化类比：水果店分级。
  老板从一大堆混杂的苹果里，先挑出全场最小的一个放进 1 号筐，再从剩下的苹果里挑出最小的放进 2 号筐。

  • ​猎头寻找​：对应 minIdx​ 的不断更新。

  • ​精准入库​：对应每一轮结束后的那一次 swap​。

• ​关键矛盾​：如果没有这个机制，我们就无法从杂乱无章的原始数据中快速定位极端值。但它的死穴是**“死脑筋”**——即便苹果已经排好序了，它依然会坚持把全场扫一遍，完全没有利用既有信息的智慧。

插入排序 (Insertion Sort)：打麻将的“手牌管理”

• ​一句话核心​：“在有序中寻找位置。” 假设左边已经是排好的，将新成员插入到合适的地方，这种算法对“几乎有序”的数据有奇效。

• 生活化类比：摸扑克牌。
  你手里已经有几张排好序的牌，新摸一张 7，你会从右往左看：10 比它大，往右挪；9 比它大，往右挪；直到遇到 6，把 7 插入。

  • ​挪动空间​：对应 arr[j+1] = arr[j]​。

  • ​落位​：对应 arr[j+1] = key​。

• ​关键矛盾​：如果不用插入排序，当你往一个有序系统（如日志流）中增加少量数据时，你可能需要重启全局排序。它是维护局部秩序成本最低的方式。

快速排序 (Quick Sort)：基于“权威”的权力下放

• ​一句话核心​：“先定调子，再分山头。” 选一个基准，把天下分为“比我大”和“比我小”两拨人，然后让他们自己去内部排序。

• 生活化类比：公司组织架构。
  CEO（基准值）下令：所有年薪高于 100 万的站右边，低的站左边。然后左右两边各自任命一个 VP，重复这个指令。

  • ​CEO/基准点​：对应 Pivot​。

  • ​递归授权​：对应 quickSort​ 自身调用。

• ​关键矛盾​：如果没有快排，在大规模并发处理（如百万级用户画像排序）时，单线程扫描会直接导致内存溢出。快排通过​递归拆解​，将 的灾难降维打击成了 。

归并排序 (Merge Sort)：标准化的“拉链合龙”

• ​一句话核心​：“极致的稳定与分工。” 哪怕数据再乱，也先拆成一个个体，再按固定规则两两合并。

• 生活化类比：银行多窗口汇合。
  两个窗口的客户都排好了序，现在要合并到一个VIP窗口。柜员只需要看两个队列的最前面哪个人更急（小），就请谁先进。

  • ​窗口队头对比​：对应 L[i] <= R[j]​。

  • ​合并操作​：对应 merge​ 函数。

• ​关键矛盾​：它是**“稳定性”**的守护神。如果没有归并，在处理具有相同权重的复杂对象（如订单列表）时，数据可能会发生莫名其妙的“位移”，导致业务逻辑错误。

堆排序 (Heap Sort)：高效的“金字塔选拔”

• ​一句话核心​：“建立等级森严的选拔机制。” 利用二叉树结构，让最大（或最小）的元素始终待在塔尖。

• 生活化类比：大型选秀比赛。
  1024 个人参加海选，通过两两对决建立胜者组（堆）。每次只取冠军（堆顶），然后让剩下的第二名补位，再次比拼。

  • ​建立金字塔​：对应 buildHeap​。

  • ​塔尖出货​：对应将堆顶元素与末尾交换并重新调整堆。

• ​关键矛盾​：当内存空间极度紧张，又不允许像归并那样申请额外空间时，堆排序是**“空间效率”**的王者。没有它，嵌入式系统或超大规模内存映射文件的排序将无从谈起。