如何保证在此快速排序 3 路分区实现中正确分区？

问：

我正在尝试实现一种具有三向分部的快速排序算法，当只有几个唯一元素时，它被提到是加快排序算法的一种方法。我在网上找到了以下基于“荷兰国旗问题”的实现，但我注意到它在某些情况下无法正确分区数组。

void partition3(vector<int> &a, int low, int high, int &i, int &j) {
    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; 
}

对于输入情况，其中生成的分区数组为 。在这种特殊情况下，当最后一个元素被选为枢轴点时，永远不会出现指针永远不会递增的情况。因此，分区算法输出枢轴点和 .a = [2,3,9,2,2]a'=[2,2,2,9,3]a[mid] < pivotlowi=-1j=3

应该如何选择初始枢轴，以便正确分区输入数组？

上面的算法适合如下：Quicksort

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); //compute partition points m1 and m2 for 3 way split 

  randomized_quick_sort(a, l, m1 - 1); //recursively sort the lower array
  randomized_quick_sort(a, m2 + 1, r); //recursively sort the upper array 
}

where 和l=0r=a.size()-1