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

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

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 partition。在此循环结束时，您的列表将类似于 [l1, l2, ..., lx, g1, g2, ..., gy, pivot]，其中 l1, l2, ..., lx 均小于或等于基准，而 g1, g2, ..., gy 均大于或等于基准。 leftCounter 指向 g1，rightCounter 指向 lx。您需要确保枢轴将两组分开并且您 return 正确的索引：

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

这两行是您问题的根源。您需要 swap(list, leftCounter, end) 才能将枢轴移动到列表中的正确位置。现在您的列表看起来像 [l1, l2, ..., lx, pivot, g2, g3, ..., gy, g1]。您需要 return 枢轴的索引，即 leftCounter.

至于为什么它以相反的顺序排序：你很幸运。在其他输入上尝试，它并不总是以相反的顺序排序。

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

[a, g, b, a, f, c, c, b, a]

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

Why does my quicksort sorts the array in a reverse order?

java

arrays

sorting

quicksort