java - 字典顺序快速排序

Question

我尝试使用 Java 中的快速排序算法按字典顺序对 Strings 数组进行排序。该数组使用 Scanner 通过终端读取并保存在 ArrayList 中。此 ArrayList 后来被转换为一个数组，我(尝试)在其中应用快速排序算法。 我有两种方法:

private static void sortA(String[] s, int start, int end) {
    if (end > start) {
        int pivot = partition(s, start, end);
        sortA(s, start, pivot - 1);
        sortA(s, pivot + 1, end);
    }
}

private static int partition(String[] s, int start, int end) {
    String pivot = s[end];
    int left = start;
    int right = end;
    String temp = "";
    do {
        while ((s[left].compareTo(pivot) <= 0) && (left < end))
            left++;
        while ((s[right].compareTo(pivot) > 0) && (right > start))
            right--;
        if (left < right) {
            temp = s[left];
            s[left] = s[end];
            s[right] = temp;
            printRow(s);

        }
    } while (left < right);
    temp = s[left];
    s[left] = s[end];
    s[end] = temp;
    return left;
}

代码似乎随机地工作正常然后突然就不行了。例如，数组 {"java", "application", "system"} 可以很好地排序为 {"application", "java", "system"}。数组{"library", "content", "bin"}排序为{"bin", "library", "contents"}，不是字典序命令。当然，计算机不会随机工作，所以我的代码一定有问题。我试图在纸上找出一个例子，但后来我会发现一些完全错误的东西。但是，我的代码基于对双数组进行排序的快速排序实现，因此我认为我没有犯大的推理错误。 提前致谢。

Answer 1

您以错误的方式拆分数组: 正确的拆分是 "pivot-1""pivot"

sortA(s, start, pivot-1);
sortA(s, pivot, end);