为重复键算法选择枢轴

Question

我想了解如何在尝试在数组中找到重复键时选择枢轴。我见过的大多数例子总是选择第一个元素作为支点，假装这个元素在数组中重复。如果情况并非如此呢？如何正确选择枢轴？

假设数组a[lo...hi]和v分区元素v = a[lo]。我们也有2个指标GT和LT其中

• a[lo ... lt]少比伏
• a[lt ... gt]是等于V
• a[gt ... hi]是更大的比伏

这样的想法是从扫描从左到右，直到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)); 
}