如何选择初始pivot以保证三路快速排序分区的正确性？

问题分析 #

你提供的三路分区快速排序实现中，固定选择数组最后一个元素作为Pivot会导致极端场景下的分区错误。比如输入[2,3,9,2,2]时，Pivot是最后一个元素2，所有元素要么等于2要么大于2，全程不会触发a[mid] < pivot的分支，导致low指针始终停在初始位置0，最终返回的分区点i = low -1 = -1。虽然递归基会跳过无效的左区间，但分区后的数组[2,2,2,9,3]并未完成正确的大小分区，后续递归处理右区间时仍需额外排序，甚至在更复杂的输入下可能引发逻辑错误。

解决方案：优化Pivot选择策略 #

要避免这类问题，核心是避免选择数组中的极值作为Pivot，推荐两种可靠的Pivot选择方式：

1. 随机选择Pivot #

在low到high的范围内随机挑选一个元素，将其与数组末尾元素交换后，再沿用原分区逻辑。这种方式能有效规避固定Pivot带来的最坏情况，让算法的平均时间复杂度保持在O(n log n)。

修改后的partition3函数开头添加随机选择逻辑：

void partition3(vector<int> &a, int low, int high, int &i, int &j) {
    // 随机选择Pivot并交换到末尾
    int pivot_idx = low + rand() % (high - low + 1);
    swap(a[pivot_idx], a[high]);
    
    int mid = low;
    int pivot = a[high];
    while (mid <= high) {
        if (a[mid] < pivot)
            swap(a[low++], a[mid++]);
        else if (a[mid] == pivot)
            mid++;
        else if (a[mid] > pivot)
            swap(a[mid], a[high--]);
    }
 
    // update i and j
    i = low - 1;
    j = mid; 
}

2. 三数取中法选择Pivot #

选择数组low、mid、high三个位置元素的中位数作为Pivot，再交换到末尾。这种方式能更稳定地避免极值Pivot，尤其在接近有序的数组中表现更优。

修改后的partition3函数开头添加三数取中逻辑：

void partition3(vector<int> &a, int low, int high, int &i, int &j) {
    // 三数取中选择Pivot并交换到末尾
    int mid_idx = low + (high - low) / 2;
    // 调整三个位置的元素，让a[high]成为中位数
    if (a[low] > a[mid_idx]) swap(a[low], a[mid_idx]);
    if (a[low] > a[high]) swap(a[low], a[high]);
    if (a[mid_idx] > a[high]) swap(a[mid_idx], a[high]);
    
    int mid = low;
    int pivot = a[high];
    while (mid <= high) {
        if (a[mid] < pivot)
            swap(a[low++], a[mid++]);
        else if (a[mid] == pivot)
            mid++;
        else if (a[mid] > pivot)
            swap(a[mid], a[high--]);
    }
 
    // update i and j
    i = low - 1;
    j = mid; 
}

额外注意事项 #

你的快速排序函数中存在笔误：递归调用的randomized_quick_sort应该改为threeway_quick_sort，否则会调用其他排序函数导致逻辑错误：

void threeway_quick_sort(vector<int> &a, int l, int r) {
  if (l >= r) {
    return;
  }

  int m1 = 0 , m2 = 0; 
  partition3(a, l, r, m1, m2); 

  threeway_quick_sort(a, l, m1 - 1); // 修正为当前函数名
  threeway_quick_sort(a, m2 + 1, r); // 修正为当前函数名
}

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