处理快速排序中的重复键

Question

简单的快速排序将花费 O(n^2) 时间对不包含唯一键的数组进行排序，因为所有键都将在主值之前或之后进行分区。有多种方法可以处理重复的键（如 快速排序是最佳的）。建议的解决方案仅适用于 Hoare 分区，但我已经实现了 Lomuto 分区。为了处理重复的键，我交替将重复项移动到枢轴的左侧和将重复项移动到枢轴的右侧。该算法的工作原理如下：

//partition array from index start to end
select pivot element and move it to array[start]
boolean dupHandler=true;
int index=start;
for(i from start+1 to end)
     int val=array[start].compareTo(array[i]);
     if(val==0)
          if(dupHandler)
               swap array[++index] and array[i]
          dupHandler=!dupHandler;
     else if(val>0)
          swap array[++index] and array[i]
swap array[start] and array[index]

是否有更好（更有效）的方法来处理重复键？

编辑：我的代码（如图所示）要求compareTo与equals一致（即使认为这不是要求）