近乎有序数组如何高效排序？为什么可以用小顶堆？

简化版

如果数组中每个元素距离它最终位置最多不超过 k，可以用大小为 k + 1 的小顶堆排序。

因为当前位置的最小候选元素一定出现在接下来的 k + 1 个元素中。每次从堆中弹出最小值放到结果里，再加入下一个元素。

复杂度是 O(n log k)，当 k 远小于 n 时比完整排序更快。

详细版

近乎有序数组也叫 k-sorted array。

做法：

先把前 k + 1 个元素入小顶堆；
每次弹出堆顶作为当前位置答案；
把数组后续元素继续入堆；
最后清空堆。

heap size <= k + 1
每个元素入堆一次，出堆一次

方法	复杂度
完整排序	`O(n log n)`
小顶堆	`O(n log k)`

前提是题目给出或能推断每个元素最多偏离 k 个位置。

完整版教学

1. 什么是近乎有序数组

近乎有序通常指每个元素距离它在最终有序数组中的位置不超过 k。

例如 k = 2 时，一个本该在下标 5 的元素，当前可能在 3..7 范围内。

这种数组没有完全乱序，可以利用这个性质优化排序。

2. 为什么最小值在前 k+1 个元素中

最终排序后的第 0 个元素，不可能在原数组下标大于 k 的位置。

因为如果它在更远位置，距离最终位置就超过了 k。

所以第一个输出的最小值一定在：

0..k

也就是前 k + 1 个元素里。

近乎有序排序的关键观察是：当前位置答案只需要在一个小窗口里找。

3. 为什么用小顶堆

每个位置都要从当前候选窗口中取最小值。

小顶堆正好支持：

插入新候选：O(log k)；
取出最小候选：O(log k)；
查看堆顶：O(1)。

堆大小始终控制在 k + 1 左右。

4. 算法流程怎么写

伪代码：

heap = first k + 1 elements
idx = 0
for i from k + 1 to n - 1:
  nums[idx++] = heap.pop()
  heap.push(nums[i])
while heap not empty:
  nums[idx++] = heap.pop()

如果不允许原地覆盖，也可以写到新数组。

5. 为什么每次弹出是正确的

假设当前要填位置 idx。

由于每个元素最多偏移 k，最终应该落在 idx 的元素一定已经进入当前堆。

堆中保存的是所有可能成为当前答案的候选。弹出最小值，就是当前位置正确元素。

填完后，再加入下一个新候选，窗口向右滑动。

6. 复杂度分析

每个元素最多入堆一次、出堆一次。

堆大小最多是 k + 1。

因此时间复杂度是：

O(n log k)

空间复杂度是：

O(k)

当 k 很小，比如 k = 10，这个方法非常有优势。

7. 和插入排序的关系

插入排序也适合近乎有序数组。

如果逆序程度很低，插入排序移动次数少，表现很好。

方法	适合
插入排序	几乎完全有序，逆序很少
小顶堆	明确每个元素最多偏移 `k`
TimSort	工程中利用天然有序段

面试中如果题目明确给了 k，小顶堆是非常标准的答案。

8. 常见误区与追问

误区：近乎有序数组仍必须完整 O(n log n) 排序。 如果有 k 偏移约束，可以做到 O(n log k)。
误区：堆大小应该是 k。 候选范围包含当前位置和后面 k 个元素，所以是 k + 1。
误区：小顶堆会丢失后续更小元素。 更远的元素不可能属于当前位置，否则会违反偏移不超过 k。
追问：如果 k 接近 n 怎么办？ 复杂度接近普通堆排序，不再有明显优势。
追问：为什么插入排序也适合近乎有序？ 因为元素移动距离短，实际移动次数少。

简化版

详细版