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

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

Answer 1

问题中提供的实现让我感到困惑。这并不是说它不正确(或者至少接近正确)，但我确实觉得它很难读(这可能更重要)。有可能我只是速度慢，而且这个实现实际上非常直观，但我倾向于它的实现比连贯更聪明。

一般来说，快速排序是一种递归算法，它将一组数据分成相对于主元(小于、等于和大于)的三个 bin，然后对不相等的 bin 进行排序(使用相同的算法)，然后合并结果以形成排序的数据集。在英语中，它的工作方式非常直观。没有理由它在代码中不能相同。我始终致力于编写您可以理解的代码(然后根据需要使其更高效)，而不是尝试编写您无法理解的代码，然后在它不理解的时候就陷入困境”不工作。

下面是一个更详细的实现，(至少对我而言)它的操作似乎更加清晰。它的效率也非常低(它制作了六个不同的列表和数组只是为了对一组数据进行排序)。我不会为此道歉；我假设这个问题本质上是学术性的。如果您确实需要提高效率，这对用户来说是一种练习，但没有理由不能将其分解为直观的步骤，如下所示(这会让您省去很多麻烦)。

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()