java 中的快速排序算法未正确排序（第一个元素作为枢轴）

Question

我正在处理一个任务，我们应该在其中实现快速排序，第一个元素作为主元。我的代码中有一个小错误导致列表的元素（用于测试）排序不正确。输出应该是 1 3 7 8 9 10 但最终是 1 7 3 8 9 10 （7 和 3 应该交换位置）。我怀疑错误可能在第 15-26 行之间的某处，但我似乎无法找到它，尽管已尝试修复它。

谁能看出有什么不对？

（在第一个 while 循环中，我试过使用 i <= j 而不是 i < j，但这似乎会导致无限循环。在其他示例中看到过这种方法，但不知道为什么这对我来说不起作用）

public static void quickSort(int[] a, int lo, int hi) {
    if (!(hi > lo)) {
        return;
    }
    int pivot = a[lo];
    int i = lo;
    int j = hi + 1;
    int temp;
    i++;
    j--;
    while (i < j) {
        while (a[i] < pivot) {
            i++;
        }
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {
            switchPlace(a, i, j);
            i++;
            j--;
        }
    }
    switchPlace(a, lo, j);
    quickSort(a, lo, j - 1);
    quickSort(a, j + 1, hi);
}

public static void switchPlace(int[] a, int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

public static void printList(int[] a) {
    String res = "";
    for (int i = 0; i < a.length; i++) {
        res += a[i] + " ";
    }
    System.out.println(res);
}

public static void main(String[] args) {
    int[] a = { 9, 3, 10, 1, 8, 7 };
    quickSort(a, 0, a.length - 1);
    printList(a);
}

感谢任何帮助！

Answer 1

这应该可以解决您的问题：

public static void quickSort(int[] a, int lo, int hi) {
        if (!(hi > lo)) {
            return;
        }
        int pivot = a[lo];
        int i = lo - 1;
        int j = hi + 1;
        int temp;
        while (i < j) {
            do {
                i++;
            } while (a[i] < pivot);
            do {
                j--;
            } while (a[j] > pivot);
            if (i < j) {
                switchPlace(a, i, j);
                i++;
                j--;
            }
        }
        switchPlace(a, lo, j);
        quickSort(a, lo, j - 1);
        quickSort(a, j + 1, hi);
    }

Answer 2

我将在这里描述一种调试此类算法的简单方法，其中包括：

对代码的较小部分应该产生一些预期；
验证是否满足这些期望。

第一点涉及详细了解代码试图做什么，而第二点意味着使用某种工具进行检查。这个特定答案中举例说明的 "tool" 包括使用 print 消息，但通常它可以是其他东西（例如步调试器）。

qsort算法的主要操作是交换枢轴周围的元素，使得较小的值在前，较大的值在后。此过程发生在 lo 和 hi 索引之间的各种子序列。

现在让我们检查每个子序列是否正确完成了这个操作。为此，我们可以显示初始的子序列，以及发生交换后的子序列，以便我们事后手动检查是否正确执行了此操作。

我们可以在交换部分之前使用类似这样的代码：

    System.out.print("before: ");
    for (int k = lo; k <= hi; k++) {
        System.out.print(a[k] + ", ");
    }
    System.out.println();

交换部分之后是这样的：

    System.out.print("after: ");
    for (int k = lo; k <= hi; k++) {
        System.out.print(a[k]);
        if (k == j) {
            System.out.print(" (pivot)");
        }
        System.out.print(", ");
    }
    System.out.println();
    System.out.println();

示例中序列的输出如下所示：

before: 9, 3, 10, 1, 8, 7,
after: 8, 3, 7, 1, 9 (pivot), 10,

before: 8, 3, 7, 1,
after: 1, 3, 7, 8 (pivot),

before: 1, 3, 7,
after: 1 (pivot), 3, 7,

before: 3, 7,
after: 7, 3 (pivot),

我们可以看到最后一个长度为2的子序列出现了问题。好处是我们现在可以只专注于这种情况，并准确了解发生了什么。

例如我们甚至可以直接传递给算法 int[] a = {3, 7};.

仔细考虑这种情况下会发生什么，我们可以看到问题在于 j 索引没有跳过大于主元的元素，因为 while (i < j) 在这种情况下立即退出一种情况（从一开始我们就有 i == j）。有多种解决方案，一个似乎有效的方法是在各自的条件下使用 while (i <= j)——尽管你明确提到它可能导致无限循环，但实际上情况似乎并非如此。

下面是包含此修复程序的代码（以及上面描述的其他 print）：

public static void quickSort(int[] a, int lo, int hi) {
    if (!(hi > lo)) {
        return;
    }
    int pivot = a[lo];
    int i = lo;
    int j = hi + 1;
    int temp;
    i++;
    j--;

    System.out.print("before: ");
    for (int k = lo; k <= hi; k++) {
        System.out.print(a[k] + ", ");
    }
    System.out.println();

    while (i <= j) {
        while (a[i] < pivot) {
            i++;
        }
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {
            switchPlace(a, i, j);
            i++;
            j--;
        }
    }
    switchPlace(a, lo, j);

    System.out.print("after: ");
    for (int k = lo; k <= hi; k++) {
        System.out.print(a[k]);
        if (k == j) {
            System.out.print(" (pivot)");
        }
        System.out.print(", ");
    }
    System.out.println();
    System.out.println();

    quickSort(a, lo, j - 1);
    quickSort(a, j + 1, hi);
}

public static void switchPlace(int[] a, int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

public static void printList(int[] a) {
    String res = "";
    for (int i = 0; i < a.length; i++) {
        res += a[i] + " ";
    }
    System.out.println(res);
}

public static void main(String[] args) {
    //int[] a = {3, 7};
    //int[] a = { 9, 3, 10, 1, 8, 7 };
    int[] a = {24, 2 , 45 ,20 ,56 ,75 ,2 ,56 ,99 ,53 ,12};
    quickSort(a, 0, a.length - 1);
    printList(a);
}

java 中的快速排序算法未正确排序（第一个元素作为枢轴）

Quicksort-algorithm in java not sorting correctly (first element as pivot)

java

algorithm

quicksort