QuickSort 无法正常工作

Question

我从多个来源改编的快速排序算法无法完全正常工作，我无法弄清楚它有什么问题。我认为某处存在一个差一错误，但我已经尝试了一个小时，但没有不同的结果。

public static <T extends Comparable<T>> void serialSort(List<T> list){
    if (list == null || list.size() <= 1) {
        return;
    }
    T pivot = list.get(list.size() / 2 - 1);
    int i = 0;
    int j = list.size() - 1;
    while (i <= j){
        while (list.get(i).compareTo(pivot) == -1){
            i++;
        }
        while (list.get(j).compareTo(pivot) == 1){
            j--;
        }
        if (i <= j) {
            Collections.swap(list, i, j);
            i++;
            j--;
        }
    }
    if (0 < j)
        serialSort(list.subList(0, j));
    if (i < list.size())
        serialSort(list.subList(i, list.size()));
}

我应该将其适配到多线程版本，但我想先修复错误。

示例输入：

[2, 9, 4, 1, 7, 2, 1, 1, 6, 6, 3, 8, 4, 7, 6, 7, 8, 6, 3, 3, 3, 1, 4, 1, 1, 2, 9, 7, 7, 2]

输出：

[1, 1, 1, 1, 1, 2, 2, 1, 2, 3, 3, 3, 2, 4, 4, 4, 3, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 9, 9]

Answer 1

我从 java 文档中发现 List.subList(int, int) 是这样的：

Returns a view of the portion of this list between the specified fromIndex, 
inclusive, and toIndex, exclusive.

因为我怀疑这是一个错误。我没有在每个递归调用中包含 "left" 子列表的最后一个元素。这样做修复了它：

if (0 < j)
        serialSort(list.subList(0, j + 1));

Answer 2

如@FFritz 所述，使用 < 0 和 > 0 进行 compareTo 比较（这只是一般的好习惯）。
在构建递归的第一个 subList 时使用 j + 1。

此代码有效：

public static <T extends Comparable<T>> void serialSort(List<T> list){
    if (list == null || list.size() <= 1) {
        return;
    }
    T pivot = list.get(list.size() / 2 - 1);
    int i = 0;
    int j = list.size() - 1;
    while (i < j){
        while (list.get(i).compareTo(pivot) < 0){
            i++;
        }
        while (list.get(j).compareTo(pivot) > 0 && j > i){
            j--;
        }
        if (i <= j) {
            Collections.swap(list, i, j);
            i++;
            j--;
        }
    }
    if (0 < j)
        serialSort(list.subList(0, j + 1));
    if (i < list.size())
        serialSort(list.subList(i, list.size()));
}

QuickSort 无法正常工作

QuickSort not fully working

java

quicksort