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

Using quicksort on a string array

提问by Mackenzie

I'm a programming student and rather than post the whole assignment I'll just ask for help solving what I've tried for hours now to understand. I'm tasked with sorting an array of strings using the quicksort method. Everything else I've been tasked with as part of this problem is fine but when I tested the sorting method by printing out the String Array, it's completely jumbled up without any seeming rhyme or reason. Please help me pinpoint the error in my code, or the several glaring errors I've overlooked. The array of strings provided is this list of 65 names: http://pastebin.com/jRrgeV1Eand the method's code is below:

我是一名编程学生，而不是发布整个作业，我只是寻求帮助解决我已经尝试了几个小时来理解的问题。我的任务是使用快速排序方法对字符串数组进行排序。作为这个问题的一部分，我负责的其他所有事情都很好，但是当我通过打印出字符串数组来测试排序方法时，它完全混乱了，没有任何看起来的押韵或原因。请帮助我查明代码中的错误，或者我忽略的几个明显错误。提供的字符串数组是 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;
    }

采纳答案by SomeJavaGuy

Ok, i was mistaken that it would work and found your tiny mistake.

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

Take a look at wikipedias pseudo code

看看维基百科的伪代码

You will notice that your conditions in the while loop are causing the error

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

if you change (a[i].compareTo(pivot) < 0 && i <= end && j > i)and (a[j].compareTo(pivot) > 0 && j >= start && j >= i)to

如果你改变(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)and (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)。

回答by John Smith

Thought this would help for those who seek for a string sorting algorithm based on quick sorting method.

认为这对那些寻求基于快速排序方法的字符串排序算法的人有帮助。

public class StringQuickSort {

    String names[];
    int length;

    public static void main(String[] args) {
        StringQuickSort sorter = new StringQuickSort();
        String words[] = {"zz", "aa", "cc", "hh", "bb", "ee", "ll"}; // the strings need to be sorted are put inside this array
        sorter.sort(words);

        for (String i : words) {
            System.out.print(i);
            System.out.print(" ");
        }
    }

    void sort(String array[]) {
        if (array == null || array.length == 0) {
            return;
        }
        this.names = array;
        this.length = array.length;
        quickSort(0, length - 1);
    }

    void quickSort(int lowerIndex, int higherIndex) {
        int i = lowerIndex;
        int j = higherIndex;
        String pivot = this.names[lowerIndex + (higherIndex - lowerIndex) / 2];

        while (i <= j) {
            while (this.names[i].compareToIgnoreCase(pivot) < 0) {
                i++;
            }

            while (this.names[j].compareToIgnoreCase(pivot) > 0) {
                j--;
            }

            if (i <= j) {
                exchangeNames(i, j);
                i++;
                j--;
            }
        }
        //call quickSort recursively
        if (lowerIndex < j) {
            quickSort(lowerIndex, j);
        }
        if (i < higherIndex) {
            quickSort(i, higherIndex);
        }
    }

    void exchangeNames(int i, int j) {
        String temp = this.names[i];
        this.names[i] = this.names[j];
        this.names[j] = temp;
    }
}