1

一个简单的快速排序将花费 O(n^2) 时间来对不包含唯一键的数组进行排序，因为所有键都将在枢轴值之前或之后进行分区。有一些方法可以处理重复的键（例如Quicksort is Optimal中描述的一种）。建议的解决方案仅适用于 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 一致（即使认为这不是必需的）

4

0 回答 0