algorithm - 为重复键算法选择枢轴

Question

我试图了解在尝试查找数组中的重复键时如何选择枢轴。我见过的大多数示例总是选择第一个元素作为枢轴，假装这个元素在数组中重复。如果不是这样呢？如何正确选择支点？

假设一个数组a[lo...hi]和 v 是分区元素，v = a[lo]。我们还有 2 个索引 gt 和 lt，其中

• a[lo ... lt]小于 v
• a[lt ... gt]等于 v
• a[gt ... hi]大于 v

所以想法是从左到右扫描直到 i > gt ：

• (a[i] < v)：swap(a[i], a[lt]), i++, lt++
• (a[i] > v) : swap(a[i], a[gt]); gt--
• (a[i] == v): i++

这个想法与快速排序分区非常相似，我想知道在这种情况下如何正确选择枢轴。

Answer 1

是否选择数据透视副本都没有关系。您的算法应该尝试递归查找重复元素，并且在找到重复键之前它不会停止。

 /*
 *assume that all element are positive, reutrn -1 when there is no duplicate keys
 */
int duplicate_key(int a[], int lo, int ho) { 
 if (ho - lo <= 1) return -1; //no duplicate keys when there is no more than 2 keys
 a[lo ... lt] are less than v
 a[lt ... gt] are equal to v
 a[gt ... hi] are greater than v
 if (gt - lt > 1) return v;
 return max(duplicate_key(a, lo, it), duplicate_key(gt, hi));
}