java - 在字符串数组上使用快速排序

Question

我是一名编程专业的学生，​​我不会发布整个作业，而是寻求帮助解决我已经尝试了几个小时才能理解的问题。我的任务是使用快速排序方法对字符串数组进行排序。作为这个问题的一部分，我所负责的其他一切都很好，但是当我通过打印字符串数组来测试排序方法时，它完全困惑了，没有任何看似押韵或理由。请帮助我查明我的代码中的错误，或者我忽略的几个明显的错误。提供的字符串数组是这个包含 65 个名称的列表:http://pastebin.com/jRrgeV1E方法代码如下:

private static void quickSort(String[] a, int start, int end)
{
        // index for the "left-to-right scan"
        int i = start;
        // index for the "right-to-left scan"
        int j = end;

        // only examine arrays of 2 or more elements.
        if (j - i >= 1)
        {
            // The pivot point of the sort method is arbitrarily set to the first element int the array.
            String pivot = a[i];
            // only scan between the two indexes, until they meet.
            while (j > i)
            {
                // from the left, if the current element is lexicographically less than the (original)
                // first element in the String array, move on. Stop advancing the counter when we reach
                // the right or an element that is lexicographically greater than the pivot String.
                while (a[i].compareTo(pivot) < 0 && i <= end && j > i){
                    i++;
                }
                // from the right, if the current element is lexicographically greater than the (original)
                // first element in the String array, move on. Stop advancing the counter when we reach
                // the left or an element that is lexicographically less than the pivot String.
                while (a[j].compareTo(pivot) > 0 && j >= start && j >= i){
                    j--;
                }
                // check the two elements in the center, the last comparison before the scans cross.
                if (j > i)
                    swap(a, i, j);
            }
            // At this point, the two scans have crossed each other in the center of the array and stop.
            // The left partition and right partition contain the right groups of numbers but are not
            // sorted themselves. The following recursive code sorts the left and right partitions.

            // Swap the pivot point with the last element of the left partition.
            swap(a, start, j);
            // sort left partition
            quickSort(a, start, j - 1);
            // sort right partition
            quickSort(a, j + 1, end);
        }
    }
    /**
     * This method facilitates the quickSort method's need to swap two elements, Towers of Hanoi style.
     */
    private static void swap(String[] a, int i, int j)
    {
    String temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    }

Answer 1

好吧，我误以为它会起作用并发现了你的小错误。

看看wikipedias pseudo code

您会注意到 while 循环中的条件导致了错误

如果你改变(a[i].compareTo(pivot) < 0 && i <= end && j > i)和 (a[j].compareTo(pivot) > 0 && j >= start && j >= i)到

(a[i].compareTo(pivot) <= 0 && i < end && j > i)和 (a[j].compareTo(pivot) >= 0 && j > start && j >= i) .