查找、排序与区间

本页按场景选择方法；通过各条目链接阅读完整推演、源码和输出。

这些 package main 程序应分别保存到独立练习模块（Go 1.22+）；本轮未运行。原地排序会改输入，归并/计数/桶排序返回新结果。数值和分配大小必须落在本机 int 与可用内存范围内，桶宽必须为正；无效输入的返回约定不替代生产 API 校验。

要解决的问题	可选方法	选择前确认
只查询少量或无序数据	线性查找；有序输入才用二分查找	二分答案还要求可行性单调且上下界覆盖解。
学习局部交换，或处理小数组、近乎有序数据	冒泡排序、选择排序、插入排序、希尔排序	插入最坏仍为 O(n²)；选择排序不稳定，希尔性能取决于间隔序列。
需要保留相等元素的原顺序	归并排序	时间 O(n log n)，需要 O(n) 合并空间。
比较平均性能与原地排序的时间上界	快速排序或堆排序	快排平均 O(n log n)、最坏 O(n²)；堆排序原地且有 O(n log n) 上界，但不稳定。
已知整数值域、位数或数据分布	计数排序、基数排序、桶排序	计数和基数示例只处理非负整数；桶排序效果依赖分布和桶宽。
只保留最大的 k 个值	Top K 最小堆	时间 O(n log k)；返回堆内部顺序，展示时可能还需排序。
安排最多活动、合并覆盖范围或降低文件合并成本	区间调度、区间合并、最小代价合并	分别按结束时间、起点和当前最小文件选择；端点是否冲突须按业务定义。

估算成本并选择查找方式

时间与空间复杂度

正文、推演与完整示例：时间与空间复杂度。

先确定 n 表示什么，再统计循环或递归会执行多少次。示例只遍历一次切片，所以输入翻倍时工作量大致翻倍；累计变量只占固定空间。 示例时间 O(n)、额外空间 O(1)。

复杂度描述的是增长趋势，常数开销和真实输入分布仍会影响性能。

线性查找

正文、推演与完整示例：线性查找。

从头检查每个元素，第一次相等时返回下标。它不要求预处理或排序，数据很少或只查询一次时常是最简单的选择。 时间 O(n)。

若在同一大集合上反复查找，可以考虑排序后二分或建立哈希索引。

二分查找

正文、推演与完整示例：二分查找。

维护一个可能包含目标值的半开区间 [l,r)，根据中点与目标的比较缩小一侧。循环结束后还需检查候选下标是否真的匹配。 时间 O(log n)。

前提是输入按相同规则排序；否则二分的排除逻辑不成立。

二分答案

正文、推演与完整示例：二分答案。

使用前要证明边界覆盖解，并防止不可行时把 hi 误当作有效答案。

从简单排序比较到归并、快排与堆排序

插入排序

正文、推演与完整示例：插入排序。

循环开始时，左侧前缀始终有序；当前值向左寻找位置，并把较大的元素右移。输入接近有序时移动次数很少，因此小数组或排序算法的收尾阶段常会采用它。 最坏时间 O(n²)。

完全逆序时仍需 O(n²) 次移动。

冒泡排序

正文、推演与完整示例：冒泡排序。

真实项目通常直接使用 sort 包；该算法主要帮助理解局部交换与不变式。

选择排序

正文、推演与完整示例：选择排序。

在未排序部分找到最小元素，与当前位置交换，然后缩小待处理范围。它始终需要二次方级比较，却只进行线性次数的交换。 时间 O(n²)，交换次数 O(n)。

交换会改变相等元素的相对顺序，因此这个基本版本不稳定。

希尔排序

正文、推演与完整示例：希尔排序。

它就地工作且代码不复杂，但最坏性能依赖所选间隔序列，通常不如标准库排序具有明确保证。

归并排序

正文、推演与完整示例：归并排序。

递归把数组分成两半，分别排序后通过比较两边当前元素完成合并。合并时优先取左侧相等元素可保持稳定性。 时间 O(n log n)、额外空间 O(n)。

每层总工作为 O(n)，层数为 O(log n)；代价是需要额外的合并空间。

快速排序

正文、推演与完整示例：快速排序。

选择一个基准值，用双指针把较小值移到左侧、较大值移到右侧，再分别递归。分区均衡时性能很好；若基准长期偏向一侧，递归深度和时间会恶化。 平均时间 O(n log n)，最坏 O(n²)。

工程实现通常加入随机化或深度限制。

堆排序

正文、推演与完整示例：堆排序。

先自底向上建立最大堆，根节点就是当前最大值。将根与末尾交换后缩小堆，再向下调整新的根，直到全部元素有序。 时间 O(n log n)、额外空间 O(1)。

它有稳定的 O(n log n) 时间上界且原地排序，但相等元素的顺序不保留。

利用值域、位数或分布减少比较

计数排序

正文、推演与完整示例：计数排序。

先统计每个整数值出现的次数，再按值域顺序写回结果。它不通过比较决定先后，因此在值域 k 较小时可优于比较排序。 时间 O(n+k)、空间 O(k)，k 为值域大小。

示例只支持 0 到 maxValue 的非负整数；值域很大时计数数组会浪费内存。

基数排序

正文、推演与完整示例：基数排序。

从个位开始，对每一位进行稳定的计数排序，让低位顺序在处理高位时得以保留。位数固定时可获得接近线性的性能。 时间 O(d(n+b))，d 为位数、b 为进制。

本例基数排序用 exp 表示当前十进制位的权重。处理完一轮后，exp > max/10 表示下一位已经超过最大输入的最高位，应立即退出；这样既避免无意义的继续排序，也防止 exp 乘十溢出。它只接受非负整数，负数需要另行编码。

示例采用十进制并只处理非负整数；负数或不同类型的键需要额外编码策略。

桶排序

正文、推演与完整示例：桶排序。

根据值与最小值的距离把元素放进不同桶，每个桶内部排序后依次连接。效果依赖数据是否均匀分布以及桶宽是否合适。 分布较均匀时接近线性。

示例要求 bucketSize 大于零；所有值落入同一桶时优势会消失。

只筛选最大的 k 个值

Top K

正文、推演与完整示例：Top K。

扫描元素时，堆中只保留目前最大的 k 个值，堆顶是这些值中最小的一个。新值若不大于堆顶即可跳过，否则替换堆顶。 时间 O(n log k)。

示例返回的是堆内部顺序，不保证有序；需要按大小展示时再排序输出。

安排区间与选择合并顺序

区间调度

正文、推演与完整示例：区间调度。

把活动按结束时间排序，优先选择最早结束且不与上一个活动冲突的区间。较早结束会给后续活动留下最多可用空间，这可用交换论证证明最优。 目标是最多可安排的活动数。

示例把区间视为允许端点相接；是否相接算冲突须按业务定义。

区间合并

正文、推演与完整示例：区间合并。

按起点排序后，只需和当前合并区间比较：若重叠就扩展终点，否则把新区间放进结果。排序保证后续区间不可能回到已结束区间的左侧。 时间 O(n log n)。

示例会原地排序输入切片；若调用方需要保留原顺序，应先复制。

最小代价合并

正文、推演与完整示例：最小代价合并。

示例反复排序，实际处理大量文件时可换成最小堆。

静态自检

预测 RadixSort 对 {最大int,0,10} 的结果，以及最后一轮为何必须先判断再 exp*=10。提示：最后有效十进制位之后无需继续。

参考解法

应升序为 {0,10,最大int}；当 exp > max/10 时已处理最高位，直接结束，避免下一次乘十溢出造成错误位数或异常循环。此结论为静态推导，修改后的示例未执行。