algorithm - 快速排序三向分区

Question

我正在尝试使用 3 路分区技术实现快速排序算法，使用“m1”和“m2”作为索引来划定元素等于主元的区域。这是我的代码:

public class Sorting {
private static Random random = new Random();

private static int[] partition3(long[] a, int l, int r) {
    long x = a[l];
    int m1 = l;
    int m2 = l;

    for (int i = l + 1; i <= r; i++) {
        if (a[i] < x) {
            m1++;
            m2++;
            swap(a, m1, m2);

        }

        if (a[i] == x) {
            m2++;
            swap(a, i, m1);
        }
    }
    swap(a, l, m1);


    int[] m = {m1, m2};
    return m;
}

private static void swap(long[] a, int i, int j) {
    long temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

private static void randomizedQuickSort(long[] a, int l, int r) {
    if (l >= r) {
        return;
    }
    int k = random.nextInt(r - l + 1) + l;
    long t = a[l];
    a[l] = a[k];
    a[k] = t;
    int m[] = partition3(a, l, r);
    randomizedQuickSort(a, l, m[0] - 1);
    randomizedQuickSort(a, m[1] + 1, r);
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    long[] a = new long[n];
    for (int i = 0; i < n; i++) {
        a[i] = scanner.nextLong();
    }
    randomizedQuickSort(a, 0, n - 1);
    for (int i = 0; i < n; i++) {
        System.out.print(a[i] + " ");
    }
}

}

大多数时候它会为我的测试输出正确答案，但有时不会。谁能告诉我我做错了什么？

Answer 1

当列表中有重复数字时，您的代码会失败。例如，您的代码未通过测试用例:

1 2 1 3 1

由于随机数的生成，每次都会返回不同的东西，但它不会是正确的答案。这是您的 partition3() 函数的问题，特别是您的 for 循环中的情况，您可以在其中决定递增和翻转的位置。在这种情况下:

if (a[i] < x) {
    m1++;
    m2++;
    swap(a, m1, m2);
}

您缺少将第 i 个索引移动到正确位置的交换。该交换看起来像这样:

if (a[i] < x) {
    m1++;
    m2++;
    swap(a, m1, m2);
    swap(a, m1, i); //The missing swap.
}

在您的另一个 if 条件中，您遗漏了两件事。首先，它应该是一个 else-if，以避免意外进入两个 if 条件。其次，您在错误的位置交换。您应该在 m2(第二面墙)而不是 m1 交换。这是因为第二堵墙处理的值与枢轴相同，而不是第一堵墙。更正后，您的第二个 if 条件将如下所示:

else if (a[i] == x) { //Note the addition of the else
    m2++;
    swap(a, i, m2); //Corrected, now swaps at m2
}

通过这些更正，您的代码似乎可以按预期工作。