Quicksort - 具有重复值的 Hoare 分区
Quicksort - Hoare's partitioning with duplicate values
我已经为 Quicksort 实现了经典的 Hoare 分区算法。它适用于任何唯一数字列表 [3、5、231、43]。唯一的问题是当我有一个包含重复项 [1, 57, 1, 34] 的列表时。如果我得到重复值，我将进入无限循环。
private void quicksort(int[]a, int lo, int hi) {
if (lo < hi) {
int q = hoare_partition(a, lo, hi);
quicksort(a, lo, q - 1);
quicksort(a, q + 1, hi);
}
}
private int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[hi];
int i = lo;
int j = hi;
while (true) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i < j) swap(a, i, j);
else return j;
}
}
有没有可能是 Hoare 的实现不正确，无法处理重复项？
我知道这个问题已经被问过很多次了（我都试过了）但是我很难找到这个实现的解决方案。
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo – 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot
do
j := j – 1
while A[j] > pivot
if i >= j then
return j
swap A[i] with A[j]
上面的伪代码取自Wikipedia。让我们将它与您的代码进行比较。
问题是您必须在交换后移动索引。伪代码使用 do-while 循环而不是 while 循环在交换后移动索引。还要注意 i 和 j.
的初始值
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
对于递归步骤，您可能需要处理边缘情况（即索引）。如果您将 quicksort(a, lo, q-1) 更改为 quicksort(a, lo, q).
，它应该可以工作
我刚刚写的一个完整的工作版本：
import java.util.Arrays;
public class Test {
public static void main(String[] args) throws Exception {
int[] input = {1, 57, 1, 34};
quicksort(input, 0, input.length - 1);
System.out.println(Arrays.toString(input));
}
private static void quicksort(int[]a, int lo, int hi) {
if (lo < hi) {
int q = hoare_partition(a, lo, hi);
quicksort(a, lo, q);
quicksort(a, q + 1, hi);
}
}
private static int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[lo];
int i = lo - 1;
int j = hi + 1;
while (true) {
do {
i++;
}
while (a[i] < pivot);
do {
j--;
}
while (a[j] > pivot);
if (i >= j) {
return j;
}
swap(a, i, j);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
如果您更喜欢 while 循环而不是 do-while:
private static int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[lo];
int i = lo;
int j = hi;
while (true) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i >= j) {
return j;
}
swap(a, i, j);
i++;
j--;
}
}
这里是一个 C++ 示例，它实现了 Hoare 方案加上中位数 3 检查，一个 pivot 检查的副本以排除等于 pivot 的中间值（注意等于 pivot 的值可以在任何地方结束，而不仅仅是中间，所以这没有多大帮助），仅在较小的部分使用递归，对较大的部分进行循环（这可以防止堆栈溢出）。最坏情况下的时间复杂度仍然是 O(n^2)，但它需要相当具体的数据模式来产生这个（3 的中位数必须始终保持接近最小值或接近最大值）。
void QuickSort(uint32_t a[], size_t lo, size_t hi) {
while(lo < hi){
size_t i = lo, j = (lo+hi)/2, k = hi;
uint32_t p;
if (a[k] < a[i]) // median of 3
std::swap(a[k], a[i]);
if (a[j] < a[i])
std::swap(a[j], a[i]);
if (a[k] < a[j])
std::swap(a[k], a[j]);
p = a[j];
i--; // Hoare partition
k++;
while (1) {
while (a[++i] < p);
while (a[--k] > p);
if (i >= k)
break;
std::swap(a[i], a[k]);
}
i = k++;
while(i > lo && a[i] == p) // exclude middle values == pivot
i--;
while(k < hi && a[k] == p)
k++;
// recurse on smaller part, loop on larger part
if((i - lo) <= (hi - k)){
QuickSort(a, lo, i);
lo = k;
} else {
QuickSort(a, k, hi);
hi = i;
}
}
}
这是 while 循环的另一个例子
private static int partition(int[] a, int start, int end){
int i = start-1, j = end+1;
while(true){
while(a[++i] < a[start]);
while(a[start] < a[--j]);
if (i >= j) return j;
swap(a, i, j);
}
}
上面@Terry Li 的回答的地址，因为我的声誉不足以发表评论。首先非常感谢您的详细post。但是，我认为您提供的 while 循环的替代函数存在一些问题。它不是 return 原始枢轴的索引，它本身是不准确的。 （请用 hoare_partition([6,7,8,9,1,2,3,4,5], 0, 8) 试试）问题是由于 i 递增和 j 同时递减，导致你失去了对枢轴的追踪。因此，在下面提议的修复中，我插入了一个小条件以确保存储数据透视表的索引不会被更改。
如有错误请指正
private static int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[lo];
int i = lo;
int j = hi;
while (true) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i >= j) {
return i;
}
swap(a, i, j);
if (a[j] == pivot)
i++;
elif (a[i] == pivot)
j--;
}
}
Is it possible that Hoare's implementation is incorrect and is unable to cope with duplicates?
没错，当枢轴在数组中出现多次时，Hoare 算法就会失效。
一种解决方法是使用 a three-way partitioning algorithm。它没有返回单个索引，而是 returns 两个索引：数据透视部分开始的位置和结束的位置。
我知道这个 post 已经过时了，但我相信我已经找到了解决方案。当 hoare_partition 立即发现 i = lo 处的 a[i] 需要换出它的位置时，问题就出现了，但它从来没有找到合适的 a[j] 来交换。我们知道如果 q == lo 就会发生这种情况。当枢轴是数组中的最小值并且是重复的时，就会出现此问题。为了解决这个问题，我们在快速排序中检查 q == lo，如果是，我们手动交换 a[lo] 和 a[pivot_index] 以确保 a[lo] 被移出它的位置并进入一个有效的位置。我们只需要进行一次递归调用，因为左侧分区的大小为 1。
我还对内部 while 循环中的条件进行了轻微修改。除了外循环之外，您还需要检查内循环中的 i < j 是否。第二个内部 while 现在检查 a[j] 是否 >= pivot，而不是严格 >。最后一次递归调用使用 q 而不是 q+1 作为新的 lo。我把 pivot_index 作为参数。最后，我返回了 j 而不是 i。
private void quicksort(int[] a, int lo, int hi) {
if (lo < hi) {
// int pivot_index = (rand() % (hi - lo + 1)) + lo; // randomized pivot_index is better. should be in range [lo, hi] inclusive
int pivot_index = hi;
int q = hoare_partition(a, lo, hi, pivot_index);
if (q == lo) {
swap(a, lo, pivot_index);
quicksort(a, lo + 1, hi);
} else {
quicksort(a, lo, q - 1);
quicksort(a, q, hi);
}
}
}
private int hoare_partition(int[] a, int lo, int hi, int pivot_index) {
int pivot = a[pivot_index];
int i = lo;
int j = hi;
while (true) {
while (i < j && a[i] < pivot) i++;
while (i < j && a[j] >= pivot) j--;
if (i < j) swap(a, i, j);
else return j;
}
}
我已经为 Quicksort 实现了经典的 Hoare 分区算法。它适用于任何唯一数字列表 [3、5、231、43]。唯一的问题是当我有一个包含重复项 [1, 57, 1, 34] 的列表时。如果我得到重复值，我将进入无限循环。
private void quicksort(int[]a, int lo, int hi) {
if (lo < hi) {
int q = hoare_partition(a, lo, hi);
quicksort(a, lo, q - 1);
quicksort(a, q + 1, hi);
}
}
private int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[hi];
int i = lo;
int j = hi;
while (true) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i < j) swap(a, i, j);
else return j;
}
}
有没有可能是 Hoare 的实现不正确，无法处理重复项？
我知道这个问题已经被问过很多次了（我都试过了）但是我很难找到这个实现的解决方案。
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo – 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot
do
j := j – 1
while A[j] > pivot
if i >= j then
return j
swap A[i] with A[j]
上面的伪代码取自Wikipedia。让我们将它与您的代码进行比较。
问题是您必须在交换后移动索引。伪代码使用 do-while 循环而不是 while 循环在交换后移动索引。还要注意 i 和 j.
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
对于递归步骤，您可能需要处理边缘情况（即索引）。如果您将 quicksort(a, lo, q-1) 更改为 quicksort(a, lo, q).
我刚刚写的一个完整的工作版本：
import java.util.Arrays;
public class Test {
public static void main(String[] args) throws Exception {
int[] input = {1, 57, 1, 34};
quicksort(input, 0, input.length - 1);
System.out.println(Arrays.toString(input));
}
private static void quicksort(int[]a, int lo, int hi) {
if (lo < hi) {
int q = hoare_partition(a, lo, hi);
quicksort(a, lo, q);
quicksort(a, q + 1, hi);
}
}
private static int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[lo];
int i = lo - 1;
int j = hi + 1;
while (true) {
do {
i++;
}
while (a[i] < pivot);
do {
j--;
}
while (a[j] > pivot);
if (i >= j) {
return j;
}
swap(a, i, j);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
如果您更喜欢 while 循环而不是 do-while:
private static int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[lo];
int i = lo;
int j = hi;
while (true) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i >= j) {
return j;
}
swap(a, i, j);
i++;
j--;
}
}
这里是一个 C++ 示例，它实现了 Hoare 方案加上中位数 3 检查，一个 pivot 检查的副本以排除等于 pivot 的中间值（注意等于 pivot 的值可以在任何地方结束，而不仅仅是中间，所以这没有多大帮助），仅在较小的部分使用递归，对较大的部分进行循环（这可以防止堆栈溢出）。最坏情况下的时间复杂度仍然是 O(n^2)，但它需要相当具体的数据模式来产生这个（3 的中位数必须始终保持接近最小值或接近最大值）。
void QuickSort(uint32_t a[], size_t lo, size_t hi) {
while(lo < hi){
size_t i = lo, j = (lo+hi)/2, k = hi;
uint32_t p;
if (a[k] < a[i]) // median of 3
std::swap(a[k], a[i]);
if (a[j] < a[i])
std::swap(a[j], a[i]);
if (a[k] < a[j])
std::swap(a[k], a[j]);
p = a[j];
i--; // Hoare partition
k++;
while (1) {
while (a[++i] < p);
while (a[--k] > p);
if (i >= k)
break;
std::swap(a[i], a[k]);
}
i = k++;
while(i > lo && a[i] == p) // exclude middle values == pivot
i--;
while(k < hi && a[k] == p)
k++;
// recurse on smaller part, loop on larger part
if((i - lo) <= (hi - k)){
QuickSort(a, lo, i);
lo = k;
} else {
QuickSort(a, k, hi);
hi = i;
}
}
}
这是 while 循环的另一个例子
private static int partition(int[] a, int start, int end){
int i = start-1, j = end+1;
while(true){
while(a[++i] < a[start]);
while(a[start] < a[--j]);
if (i >= j) return j;
swap(a, i, j);
}
}
上面@Terry Li 的回答的地址，因为我的声誉不足以发表评论。首先非常感谢您的详细post。但是，我认为您提供的 while 循环的替代函数存在一些问题。它不是 return 原始枢轴的索引，它本身是不准确的。 （请用 hoare_partition([6,7,8,9,1,2,3,4,5], 0, 8) 试试）问题是由于 i 递增和 j 同时递减，导致你失去了对枢轴的追踪。因此，在下面提议的修复中，我插入了一个小条件以确保存储数据透视表的索引不会被更改。
如有错误请指正
private static int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[lo];
int i = lo;
int j = hi;
while (true) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i >= j) {
return i;
}
swap(a, i, j);
if (a[j] == pivot)
i++;
elif (a[i] == pivot)
j--;
}
}
Is it possible that Hoare's implementation is incorrect and is unable to cope with duplicates?
没错，当枢轴在数组中出现多次时，Hoare 算法就会失效。
一种解决方法是使用 a three-way partitioning algorithm。它没有返回单个索引，而是 returns 两个索引：数据透视部分开始的位置和结束的位置。
我知道这个 post 已经过时了，但我相信我已经找到了解决方案。当 hoare_partition 立即发现 i = lo 处的 a[i] 需要换出它的位置时，问题就出现了，但它从来没有找到合适的 a[j] 来交换。我们知道如果 q == lo 就会发生这种情况。当枢轴是数组中的最小值并且是重复的时，就会出现此问题。为了解决这个问题，我们在快速排序中检查 q == lo，如果是，我们手动交换 a[lo] 和 a[pivot_index] 以确保 a[lo] 被移出它的位置并进入一个有效的位置。我们只需要进行一次递归调用，因为左侧分区的大小为 1。
我还对内部 while 循环中的条件进行了轻微修改。除了外循环之外，您还需要检查内循环中的 i < j 是否。第二个内部 while 现在检查 a[j] 是否 >= pivot，而不是严格 >。最后一次递归调用使用 q 而不是 q+1 作为新的 lo。我把 pivot_index 作为参数。最后，我返回了 j 而不是 i。
private void quicksort(int[] a, int lo, int hi) {
if (lo < hi) {
// int pivot_index = (rand() % (hi - lo + 1)) + lo; // randomized pivot_index is better. should be in range [lo, hi] inclusive
int pivot_index = hi;
int q = hoare_partition(a, lo, hi, pivot_index);
if (q == lo) {
swap(a, lo, pivot_index);
quicksort(a, lo + 1, hi);
} else {
quicksort(a, lo, q - 1);
quicksort(a, q, hi);
}
}
}
private int hoare_partition(int[] a, int lo, int hi, int pivot_index) {
int pivot = a[pivot_index];
int i = lo;
int j = hi;
while (true) {
while (i < j && a[i] < pivot) i++;
while (i < j && a[j] >= pivot) j--;
if (i < j) swap(a, i, j);
else return j;
}
}