Hoare分区快速排序时间复杂度及O(n)缺失元素查找代码验证

1. Hoare分区的时间复杂度 #

Hoare分区（Hoare's partitioning）的时间复杂度为O(n)，其中n是分区内的元素总数。它通过双指针从分区两端向中间遍历，每个元素最多被访问、比较一次，整个过程仅需线性遍历分区内所有元素，无论基准值（pivot）如何选择，时间复杂度始终保持线性。

2. 代码评估与时间复杂度分析 #

作业要求符合度 #

你的代码完全满足要求：

• 基于快速排序的Hoare分区逻辑修改：实现了双指针移动、元素交换，最终将基准值放置到正确位置的分区流程；
• 采用递归实现：通过递归处理左右子分区完成缺失元素查找。

时间复杂度 #

• 最优/平均场景：O(n)
  每次分区后，若缺失元素位于当前分区的某一侧，递归仅会深入该侧子分区。总操作次数为 n + n/2 + n/4 + ...，求和后为线性时间O(n)，符合题目要求的O(n)复杂度。
• 最坏场景：O(n²)
  当缺失元素是序列的最后一个元素（例如原数组[1,2,3,4,5]移除5后变为[4,3,2,1]），此时需要递归处理所有分区，每次分区都要遍历整个子数组，时间复杂度退化为O(n²)。

逻辑正确性 #

代码核心逻辑成立：分区完成后，检查基准值位置leftPointer，若leftPointer + 1 != array[leftPointer]，则该值即为缺失的首个元素（正常连续序列中，索引i对应的元素应为i+1）。若当前分区无缺失，则递归检查左右子分区，测试用例的输出结果也验证了逻辑的正确性。

内容的提问来源于stack exchange，提问作者Baran