为什么我的快速排序以相反的顺序对数组进行排序？

Question

我正在尝试为字符串数组实现快速排序，但似乎它将数组按相反的顺序排序，我想知道为什么会这样，以及如何解决这个问题以正常排序...这是我的实现代码：

public class Main {

    public static void main(String[] args) {
        String[] list = {"a", "f", "c", "b"};
        quickSort(list, 0, list.length - 1);
        for (String s : list) {
            System.out.println(s);
        }
    }

    private static void quickSort(String[] list, int start, int end) {
        if (start < end) {
            int pIndex = partition(list, start, end);
            quickSort(list, start, pIndex - 1);
            quickSort(list, pIndex + 1, end);
        }
    }

    private static int partition(String[] list, int start, int end) {
        String pivot = list[end];

        int leftCounter = start;
        int rightCounter = end;

        while (leftCounter < rightCounter) {
            while (list[leftCounter].compareTo(pivot) <= 0 && leftCounter < end && rightCounter > leftCounter) {
                leftCounter++;
            }
            while (list[rightCounter].compareTo(pivot) >= 0 && rightCounter > start && rightCounter >= leftCounter) {
                rightCounter--;
            }
            if (leftCounter < rightCounter) {
                swap(list, leftCounter, rightCounter);
            }
        }
        swap(list, start, end);
        return end;
    }

    private static void swap(String[] list, int start, int end) {
        String aux = list[start];
        list[start] = list[end];
        list[end] = aux;
    }
}

- Gustavo

---

我正在审查你的代码，但在快速排序这个主题上，有一个相当迷人的新版本叫做双轴快速排序。它最近被纳入Java的核心库中。你可以在这里获取原始的白皮书。 - CodeMouse92

你的分区返回值看起来不正确。 - user2357112

其实，我很好奇为什么你要基于索引而不是值来判断“是否应该交换”。即使值是有序的，如果leftCounter < rightCounter返回的索引分别为0和2，它也会返回true。 - CodeMouse92

Answer 1

问题中提供的实现让我感到困惑。这并不是说它不正确（或者至少接近正确），但我发现它很难理解（这可能更重要）。可能是因为我比较慢，而这个实现实际上非常直观，但我倾向于认为这个实现比较聪明而不是连贯的。

通常，快速排序是一种递归算法，它将数据集分成相对于一个枢轴的三个箱子（小于、等于和大于），然后对非等值箱进行排序（使用相同的算法），最后合并结果以形成排序后的数据集。用英语表达，它应该如何工作非常直观。在代码中也没有理由不能这样做。我总是会尽力编写您可以理解的代码（然后根据需要使其更有效率），而不是试图编写您无法理解的代码，然后当它不起作用时束手无策。

下面是一个更详细的实现，对我来说（至少）在操作上似乎更清晰。它也非常低效（仅为了排序单个数据集就创建了半打不同的列表和数组）。我对此不做任何道歉；我假设这个问题是学术性质的。如果您确实需要使其更有效率，则需要用户自己练习，但是没有理由不能将其分解为直观的步骤，如下所示（这将节省您很多头痛）。

public class QuickSortTest {
    private static String[] data = new String[] {"a", "b", "c", "f", "b", "e", "b"};

    public static void main(String[] args) {
        String[] sortedData = quickSort(data);
        for (String str : sortedData) {
            System.out.println(str);
        }
    }

    private static String[] quickSort(String[] data) {
        // Edge case: return just the data if there are 0 or 1 elements (already sorted)
        if (data.length <= 1) {
            return data;
        }

        // Initialize the return structure
        String[] sortedData = new String[data.length];

        // Choose the pivot (can be any value)
        String pivot = data[data.length - 1];

        // Initialize the bins
        ArrayList<String> lessThan = new ArrayList<String>();
        ArrayList<String> equalTo = new ArrayList<String>();
        ArrayList<String> greaterThan = new ArrayList<String>();

        // Place the data into bins (based on the pivot)
        for (String str : data) {
            int compareValue = str.compareTo(pivot);
            if (compareValue < 0) {
                lessThan.add(str);
            }
            else if (compareValue > 0) {
                greaterThan.add(str);
            }
            else {
                equalTo.add(str);
            }
        }

        // Sort the non-equal data
        String[] lessThanSorted = quickSort(lessThan.toArray(new String[0]));
        String[] greaterThanSorted = quickSort(greaterThan.toArray(new String[0]));

        // Merge the data
        int length = 0;
        for (String less : lessThanSorted) {
            sortedData[length++] = less;
        }
        for (String equal : equalTo) {
            sortedData[length++] = equal;
        }
        for (String greater : greaterThanSorted) {
            sortedData[length++] = greater;
        }

        return sortedData;
    }
}

顺便提一下，如果有人想在实践中对数据进行排序，只需使用Collections.sort()。

- Ironcache

Answer 2

问题出现在你的partition方法中：

   private static int partition(String[] list, int start, int end) {
        String pivot = list[end];

        int leftCounter = start;
        int rightCounter = end;

        while (leftCounter < rightCounter) {
            while (list[leftCounter].compareTo(pivot) <= 0 && leftCounter < end && rightCounter > leftCounter) {
                leftCounter++;
            }
            while (list[rightCounter].compareTo(pivot) >= 0 && rightCounter > start && rightCounter >= leftCounter) {
                rightCounter--;
            }
            if (leftCounter < rightCounter) {
                swap(list, leftCounter, rightCounter);
            }
        }

在这个阶段之前，这基本上是标准的Hoare划分。在循环结束时，您的列表将变成[l1, l2, ..., lx, g1, g2, ..., gy, pivot]，其中l1，l2，..., lx都小于或等于枢轴点，而g1，g2，..., gy都大于或等于枢轴点。leftCounter指向g1，而rightCounter指向lx。您需要确保枢轴点将两个集合分开，并返回正确的索引：

        swap(list, start, end);
        return end;
    }

以下两行是问题的根源。您需要 swap(list, leftCounter, end) 来将枢轴移到列表的正确位置。现在您的列表将会变成 [l1, l2, ..., lx, pivot, g2, g3, ..., gy, g1]。您需要返回枢轴的索引，即 leftCounter。

---

至于为什么它按相反的顺序排序：您很幸运。尝试对其他输入进行操作，它不总是按相反的顺序排序。

String[] list = { "a", "c", "a", "b","c","f","g","a","b" }

[ a, g, b, a, f, c, c, b, a ] 是一个包含九个元素的列表，每个元素都是一个字母。

- Jeffrey

---

我不禁注意到，您的版本仍然缺少"if(leftCounter < rightCounter)"，这将始终评估为true... - CodeMouse92

@JasonMc92 在循环的最后一次迭代中，它将不会被评估为真。在最后一次迭代中，rightCounter >= leftCounter 将不会执行该 if 语句并退出循环。 - Jeffrey

啊，我确实忽略了一部分。但是，我仍然不确定这个块是否正确，因为它比较的是索引，但交换的是值。 - CodeMouse92

@JasonMc92 leftCounter将指向数组中第一个大于pivot的值，而rightCounter将指向数组中第一个小于pivot的值。有两种情况需要考虑。1）如果leftCounter >= rightCounter，那么数组中存在一个点p，使得p左侧的所有值都<= pivot，而p右侧的所有值都>= pivot：数组已经被分割，我们完成了任务。 - Jeffrey

如果 leftCounter < rightCounter，那么数组左边有一个接近 pivot 并且比 pivot 大的值，右边有一个接近 pivot 并且比 pivot 小的值。交换这两个值并继续进行。最终，我们会在中间汇聚一个完全分区的数组，完成排序。 - Jeffrey

好的，我现在明白了。我想这让我感到困惑，因为那不是我习惯的实现方式。（我刚刚删除了我的先前评论，因为在你的解释中我错过了其他东西。我需要喝咖啡>0） - CodeMouse92