Sort | NoRipple

type

Post

status

Published

date

Jun 2, 2025 02:37 AM

slug

summary

简单梳理不同时间复杂度和稳定性的算法，附带核心代码。

选择、冒泡和插入排序 O(n2)

大量无效的比较行为

选择排序 SelectionSort

i ~ n-1 范围上，找到最小值并放到 i 位置，然后在 i+1 ~ n-1 范围上继续选择排序 - OI Wiki

冒泡排序 BubbleSort

i ~ end(n-1) 范围上，找到最大值并放到 end 位置，然后在 i ~ end-1 范围上继续

插入排序 InsertionSort

0 ~ i 范围上有序，新加入数从右到左滑动到不再小的位置插入，然后继续。插入排序 - OI Wiki

折半插入排序

归并、快速和堆排序 O(nlogn)

比较行为没有浪费

归并排序 MergeSort

左部分排好序、右部分排好序，再利用 merge() 过程使得左右整体有序。归并排序 - OI Wiki

快速排序 QuickSort

快速排序 - OI Wiki

为什么要随机选位？当然也可以根据业务确定划分方式经典快速排序（如固定选择第一个或最后一个元素作为基准）在某些特殊输入下会退化为 O(n²) 的时间复杂度。例如：

已排序或逆序数组：每次划分只能将数组分成一个元素和剩余部分，导致递归深度为 O(n)，时间复杂度为 O(n²)。

重复元素较多的数组：基准元素可能无法有效分割数组。

随机选择基准 通过引入随机性，使得每个元素被选为基准的概率均等，从而打破输入的有序性规律。这样，最坏情况（如每次选到最小或最大元素）出现的概率被大大降低，即使输入是已排序的数组，也能以高概率实现平衡划分。随机化选择基准后，算法在平均情况下的时间复杂度为 O(n log n)。

调整场景示例：重复元素多：选择中位数作为基准（如三数取中法），避免划分不平衡。部分有序数据：结合随机性和固定策略（如选择中间位置）。动态数据：根据历史数据调整随机范围，避免极端值。分布式系统：根据数据分片特性选择基准，平衡负载。

堆排序 HeapSort

堆排序 - OI Wiki

堆结构完全二叉树和数组前缀范围对应，树或者堆大小由单独的变量 size 控制。父亲节点 i-1 / 2；左孩子 i * 2 + 1；右孩子 i * 2 + 2；都必须小于 size；大根堆（每一子树的最大值都在顶部） & 小根堆堆的调整： heapInsert（不断向上判断并调整，直至合法） heapfy(不断向下判断相对大的孩子并调整，直至合法)