0

我创建了以下类来对字符串数组进行排序。

public class StringSort {
private String[] hotelNames;
private int arrayLength;

public void sortHotel(String[] hotelArray) {
    if (hotelArray.length <= 1) {
        return;
    }
    this.hotelNames = hotelArray;
    arrayLength = hotelArray.length;
    quicksort(0, arrayLength - 1);
}

private void quicksort(int low, int high) {
    int i = low, j = high;
    String first = hotelNames[low];
    String last = hotelNames[high];     
    String pivot = hotelNames[low + (high - low) / 2];

    while( (first.compareTo(last)) < 0 ) { // first is less than last
        while( (hotelNames[i].compareTo(pivot)) < 0 ) { // ith element is < pivot
            i++;
        }
        while( (hotelNames[j].compareTo(pivot)) > 0) { // jth element is > pivot
            j--;
        }
        if ( ( hotelNames[i].compareTo( hotelNames[j] )) <= 0 ) {
            swap(i, j);
            i++;
            j--;                
        }

        //recursive calls
        if (low < j) {
            quicksort(low, j);
        }
        if (i < high) {
            quicksort(i, high);
        }
    }
}

private void swap(int i, int j) {
    String temp = hotelNames[i];
    hotelNames[i] = hotelNames[j];
    hotelNames[j] = temp;
}

}

但是在我的主类（一个测试 StringSort 的类）中，当我这样做时：

StringSort str = new StringSort();
String[] hotel1 = {"zzzz", "wwww", "dddd", "bbbbb", "bbbba", "aaaf", "aaag", "zzz"};
str.sortHotel(hotel1);

然后我有另一种方法可以打印出数组。但是，当它打印出来时，它会按原样输出 hotel1 数组，保持不变。没有“排序”发生，我不确定我哪里出错了。

4

1 回答 1

6

在您的快速排序实现中存在几个问题：

  1. 第一次/最后一次比较。只要第一个元素小于最后一个元素，此代码将使您的快速排序不执行任何操作，无论任何其他顺序如何。

    while( (first.compareTo(last)) < 0 ) { // first is less than last

  2. 交换前检查。此行是不必要的：

    if ( ( hotelNames[i].compareTo( hotelNames[j] )) <= 0 ) {

你真正想做的是看看是否i仍然小于j并退出循环。如果没有，那就换吧。完成分区循环后，只要每个子数组中有两个以上的元素，就可以进行递归调用。

于 2013-03-31T20:12:57.543 回答