是否有一种不依赖于数组中存在的枢轴元素的就地分区算法(在快速排序实现中使用的那种)?
也就是说,数组元素必须按以下顺序排列:
- 小于枢轴的元素(如果有的话)
- 与枢轴相等的元素(如果有的话)
- 大于枢轴的元素(如果有的话)
如果pivot元素恰好在数组中,则必须返回该元素的索引(排序后),否则返回一个特殊值;这可以是索引的1的补码,在索引中插入元素以保持顺序(类似于Java的标准二进制搜索函数的返回值)。
我见过的实现需要将pivot元素的索引作为参数给出(或者总是在数组的开头)。不幸的是,我事先不知道枢轴是否存在于数组中(或者它在数组中的位置)
编辑(回复meriton的评论):我们也可以假设下列条件之一为真:
- 数组长度为<2, 或
- 至少有一个元素为<= pivot 且至少有一个元素为>= pivot
数组中可能有重复的值(包括重复的枢轴值)
这是一个有趣的问题。您可以通过单个顺序遍历数组来实现。下面是c#代码示例。它假设一个名为a
的整数数组和一个pivot
值。
// Skip initial items that are < pivot
int iInsert = 0;
while (iInsert < a.Length && a[iInsert] < pivot)
{
++iInsert;
}
// Skip items that are = pivot
int numPivot = 0;
while (iInsert < a.Length && a[iInsert] == pivot)
{
++iInsert;
++numPivot;
}
int iCurrent = iInsert;
// Items will be added AFTER iInsert.
// Note that iInsert can be -1.
--iInsert;
while (iCurrent < a.Length)
{
if (a[iCurrent] < pivot)
{
if (numPivot == 0)
{
++iInsert;
int temp = a[iInsert];
a[iInsert] = a[iCurrent];
a[iCurrent] = temp;
}
else
{
++iInsert;
int temp = a[iInsert];
a[iInsert - numPivot] = a[iCurrent];
a[iCurrent] = temp;
a[iInsert] = pivot;
}
}
else if (a[iCurrent] == pivot)
{
++iInsert;
int temp = a[iInsert];
a[iInsert] = pivot;
a[iCurrent] = temp;
++numPivot;
}
++iCurrent;
}
int firstPivot = iInsert - numPivot + 1;
可能有一些优化的机会。
这种方法的有趣之处在于,您可以轻松地调整它以从传入数据流构建。你不需要知道有多少项进来。只需使用一个可以动态调整大小的列表。当最后一项进来时,你的列表就按正确的顺序排列了。
您很幸运:上个月编写kata是为了实现快速排序。这是我想到的:
/**
* Sorts the elements with indices i such that l <= i < r
*/
private static void qsort(int[] a, int left, int right) {
int l = left;
int r = right - 1;
if (l >= r) {
return;
}
int pivot = a[l];
l++;
for (;;) {
while (l <= r && a[l] <= pivot) l++;
while (a[r] > pivot && l < r) r--;
if (l < r) {
int t = a[l];
a[l] = a[r];
a[r] = t;
} else {
break;
}
}
l--;
a[left] = a[l];
a[l] = pivot;
qsort(a, left, l);
qsort(a, r, right);
}
如您所见,该算法仅使用pivot的原始位置来查找pivot的值,并在分区之间将pivot交换为索引。
如果我们不知道枢轴是否存在,我们可以简单地把value = pivot当作values <Pivot,也就是说,与其把小于,等于,大于Pivot的元素分成三组,不如把小于,等于Pivot,大于Pivot的元素分成两组,然后对每一组进行递归。这个解决方案是正确的。>
但是,不再保证终止:已知QuickSort会终止,因为每个递归步骤使用的数组切片比调用者短,并且已知数组切片更短,因为它们不包含pivot元素。这对你修改后的算法来说就不成立了。实际上,很容易看出终止将取决于您的枢轴值选择策略。
另一种可能性是将方法分成两个,一个将结果分割成[<= pivot,> pivot],另一个将结果的第一部分分割成[<>= Pivot].
public static int partitionLE(double[] a, int left, int right, double pivot) {
double x, y;
if (left >= right) return left;
for (;;) {
while ((x = a[left]) <= pivot) {
if (++ left >= right) return left;
}
while ((y = a[right-1]) > pivot) {
if (left >= -- right) return left;
}
if (left < right) {
a[left] = y;
a[right-1] = x;
} else {
return left;
}
}
}
public static int partitionLT(double[] a, int left, int right, double pivot) {
double x, y;
if (left >= right) return left;
for (;;) {
while ((x = a[left]) < pivot) {
if (++ left >= right) return left;
}
while ((y = a[right-1]) >= pivot) {
if (left >= -- right) return left;
}
if (left < right) {
a[left] = y;
a[right-1] = x;
} else {
return left;
}
}
}
public static int partition(double[] a, int left, int right, double pivot) {
int lastP = partitionLE(a, left, right, pivot);
int firstP = partitionLT(a, left, lastP, pivot);
if (firstP < lastP) {
return firstP;
} else {
return ~firstP;
}
}