java中的快速排序算法排序不正确(第一个元素作为枢轴)[重复]

我将在这里描述调试此类算法的简单方法,包括:

2. 验证是否满足这些期望。

第一点涉及到对代码试图做什么的一些详细理解,而第二点意味着使用一些工具进行检查。本特定答案中举例说明的“工具”包括使用 print 步骤调试器)。

此过程发生在 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();

之前:9、3、10、1、8、7、,

之后:1、3、7、8(枢轴),

之后:1(枢轴)、3、7、,

之前:3、7、,

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

int[] a = {3, 7}; .

j 索引不会跳过大于轴的元素,因为 while (i < j) 在这种情况下立即退出(我们从一开始就有i==j)。有多种解决方案,其中一种似乎有效的方法是使用 while (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--;

    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);
}

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

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);
    }