快排递归到小数组（≤10～16）时切插入排序更高效，因递归开销占比增大且插入排序自适应、原地稳定、无栈消耗；Go标准库即采用该优化策略。
为什么快排递归到小数组时要切到插入排序
快排在递归深度变大、子数组长度变小时，递归开销和比较交换的常数因子开始占主导——这时候 partition 的收益远不如直接扫一遍排好。实测表明，当子数组长度 ≤ 10～16 时，插入排序通常比继续递归快排快 1.5～3 倍，且无额外栈空间消耗。
Go 标准库 sort.go 就用了这个策略：对长度 len(p) 的切片直接调用 <code>insertionSort，你也能照着做。
怎么在 quickSort 递归出口里嵌入插入排序
关键不是“替换整个排序”，而是控制递归终止条件，在足够小的子问题上跳过 partition，改用 insertionSort 原地处理。
- 递归基设为
high - low （即长度 ≤ 9），而非 <code>low >= high - 此时对
data[low:high+1]调用插入排序，注意区间是闭区间[low, high] - 插入排序必须写成原地、稳定、不依赖额外内存的版本，避免破坏快排的内存友好性
示例片段：
立即学习“go语言免费学习笔记（深入）”；
Golang Uber Dig
下载
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等
func quickSort(data []int, low, high int) {
if high-low < 10 {
insertionSort(data[low:high+1])
return
}
p := partition(data, low, high)
if p > low {
quickSort(data, low, p-1)
}
if p < high {
quickSort(data, p+1, high)
}
}插入排序怎么写才不拖慢整体性能
Go 切片传参是引用语义，但插入排序内部仍需高效访问元素。常见坑是用 for i := range s + s[i] 再加边界检查，其实编译器未必能完全消除 bounds check。更稳的方式是手动控制索引，并复用一个临时变量减少读取次数。
- 不要用
append或新建切片 —— 必须原地操作data[i] - 内层循环用
j := i; j > 0 && data[j] ，避免重复计算 <code>data[j-1] - 提前 break：一旦
data[j] >= data[j-1]就停止移动，插入排序本身有自适应性
精简版实现：
func insertionSort(s []int) {
for i := 1; i < len(s); i++ {
v := s[i]
j := i
for j > 0 && v < s[j-1] {
s[j] = s[j-1]
j--
}
s[j] = v
}
}实际效果和要注意的边界
优化后在随机小数组（如长度 8、16、32）上，基准测试 BenchmarkSortSmall 通常能提速 20%～40%，但对大数组影响微乎其微——因为只影响最底层约 1/4 的递归调用。
- 阈值别硬写死成
10：不同数据分布（近序、逆序、重复多）下最优值不同，建议通过go test -bench在目标硬件上实测8/10/12/16 - 如果排序的是结构体或带接口的切片，
insertionSort的比较逻辑必须和快排的Less一致，否则结果错乱 - 并发安全不在此优化范围内——若多个 goroutine 共享同一底层数组，得自己加锁，插入排序本身不提供同步保障
最易被忽略的一点：插入排序虽快，但它不改变快排的最坏时间复杂度；只是把原本 O(n) 层递归里每层 O(log n) 的 partition 开销，换成了 O(k²) 的局部整理——k 是阈值，所以只要 k 是常数，就仍是 O(n log n) 平均，但常数项确实变小了。
