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し、ループから抜け出すことです。そうでない場合は、交換します。分割ループが終了したら、各部分配列に 3 つ以上の要素がある限り、再帰呼び出しを行います。

于 2013-03-31T20:12:57.543 に答える