基于Hoare分区的C++快速排序实现咨询：面试复习代码验证

嘿，我来帮你捋一捋这个Hoare分区的实现，先拆解代码里的问题和可优化的点：

代码正确性验证 #

你给出的代码片段存在几个关键问题，先逐一说明：

1. 无符号索引的溢出风险
   你用size_t作为索引类型，这会引发严重的未定义行为：当leftIndex为0时，i = leftIndex - 1会因为无符号类型的溢出规则变成SIZE_MAX（一个极大的正数），后续inputs[++i]会直接访问数组越界的内存，程序大概率崩溃或出现诡异的运行结果。同理，若rightIndex是vector的最大有效索引，j = rightIndex + 1也会溢出，但这个场景出现的概率相对更低。

2. 未完成的终止逻辑
   你写到if (i >= j)...就中断了，Hoare分区的正确终止逻辑是：当i >= j时，直接返回j作为分区分界点——后续递归排序时，左边处理[leftIndex, j]，右边处理[j+1, rightIndex]；如果i < j，则需要交换inputs[i]和inputs[j]，然后继续循环。

3. 潜在的越界隐患
   假设索引类型问题解决了，当数组所有元素都小于pivot时，++i会一直走到rightIndex+1导致越界；同理所有元素大于pivot时，--j会走到leftIndex-1。不过因为你的pivot是数组内的元素inputs[leftIndex]，所以至少会在pivot位置停下，这个隐患在正常逻辑下不会触发，但仍需注意。

优化建议 #

基于以上问题，给你几个实用的优化方向：

• 改用有符号索引类型
  把size_t换成int或ptrdiff_t，这样当leftIndex为0时，i = leftIndex - 1会变成-1，后续++i会回到0，不会出现无符号溢出的问题，且越界时的错误更容易被调试发现。

• 优化pivot选择策略
  当前直接选leftIndex作为pivot，在数组有序/逆序的场景下，快速排序会退化成O(n²)的时间复杂度。建议改用三数取中法：取leftIndex、midIndex（leftIndex + (rightIndex - leftIndex)/2）、rightIndex三个位置元素的中位数作为pivot，或者随机选择pivot，大幅降低最坏情况出现的概率。

• 添加边界检查
  在函数开头加上判断：如果leftIndex >= rightIndex，直接返回leftIndex（或rightIndex），避免无效的分区操作。

• 补全完整的分区逻辑
  修正后的完整分区函数示例（含三数取中优化）：

  #include <vector>
  #include <algorithm>
  
  int partition(std::vector<int> &inputs, int leftIndex, int rightIndex) {
      // 边界检查，直接返回
      if (leftIndex >= rightIndex) return leftIndex;
  
      // 三数取中选择pivot，避免最坏情况
      int mid = leftIndex + (rightIndex - leftIndex) / 2;
      // 调整三个位置的元素，让中位数移到left位置作为pivot
      if (inputs[mid] < inputs[leftIndex]) std::swap(inputs[mid], inputs[leftIndex]);
      if (inputs[rightIndex] < inputs[leftIndex]) std::swap(inputs[rightIndex], inputs[leftIndex]);
      if (inputs[rightIndex] < inputs[mid]) std::swap(inputs[rightIndex], inputs[mid]);
      std::swap(inputs[mid], inputs[leftIndex]);
  
      int pivotValue = inputs[leftIndex];
      int i = leftIndex - 1;
      int j = rightIndex + 1;
  
      while (true) {
          while (inputs[++i] < pivotValue);
          while (inputs[--j] > pivotValue);
          if (i >= j) {
              return j;
          }
          std::swap(inputs[i], inputs[j]);
      }
  }
  

• 优化重复元素场景
  当数组存在大量重复元素时，当前逻辑已能避免性能退化（相等元素会被分到分区两边），也可以进一步改用三路分区（将数组分为小于、等于、大于pivot的三部分），让这类场景的排序效率更高。

总结 #

你的代码核心思路是对的，主要问题在于无符号索引的溢出和未完成的终止逻辑，调整索引类型并补全逻辑后即可正确运行。加上pivot选择的优化，能让快速排序在绝大多数场景下保持O(nlogn)的高效性能。

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