Quicksort 偶尔不完成？

Question

我已经对快速排序算法做了很多尝试，但似乎无法奏效。这段代码是我得到的最接近的代码，除了大约五分之一的代码没有完全排序——它输出类似 266, 186, 219, 276, 357, 405, 686, 767, 834, 862 的内容。我试图在执行此操作的所有数字集之间找到共性，但我找不到任何东西。我花了很多时间使用调试器逐步完成它，但看不到任何东西（尽管我觉得我遗漏了一些明显的东西）。我做错了什么？

public static void sort(ArrayList<Integer> arr, int left, int right) {
    int i = left - 1, j = right, v = arr.get(right);
    if(right - i == 0 || right - i == 1)return;

    for(;;) {
        while(arr.get(++i) < v);
        while(v < arr.get(--j) && j != 0)
            if(j == 1)break;
        if(i >= j)break;

        Collections.swap(arr, i, j);
    }
    Collections.swap(arr, i, right);

    sort(arr, left, i - 1);
    sort(arr, i, right);
}

Answer 1

我对你的代码做了两件事来让它工作：

在方法集的开头 j = right +1 并将 v = arr.get(right) 移动到第一个 if 语句之后。

应该看起来像这样：

public static void sort(ArrayList<Integer> arr, int left, int right) {
        int i = left - 1;
        int j = right + 1;
        if (right - i == 0 || right - i == 1) return;
        int v = arr.get(right);

        for (;;) {
            while (arr.get(++i) < v);
            while (v < arr.get(--j) && j != 0)
                if (j == 1) break;
            if (i >= j) break;

            Collections.swap(arr, i, j);
        }
        Collections.swap(arr, i, right);

        sort(arr, left, i - 1);
        sort(arr, i, right);
    }

但这确实是不可读的代码，你应该阅读 CleanCode 这本书。

Quicksort 偶尔不完成？

Quicksort occasionally not completing?

java

sorting

algorithm

quicksort