0

このソート アルゴリズムのバグを見つけるのに苦労しています。並べ替えメソッドに配列を渡すと、たとえば 5,6,4,7,1 と同じ配列が結果として得られます。私はコードを調べてきましたが、どこが間違っているのかわかりません。SortThread タスクは無視してください。進行状況バーを更新する引数ですが、現在は使用していません。

class QuickSort extends Sort {

@Override
ArrayList<Integer> sort(ArrayList<Integer> array, SortThread task) {

    if (array.size() <= 1) {
        return array;
    }

    int middle = (int) Math.ceil((double) array.size() / 2);
    int pivot = array.get(middle);

    ArrayList<Integer> less = new ArrayList<>();
    ArrayList<Integer> greater = new ArrayList<>();

    for (int i = 0; i < array.size(); i++) {
        if (array.get(i) <= pivot) {
            if (i == middle) {
                continue;
            }
            less.add(array.get(i));
        } else {
            greater.add(array.get(i));
        }
    }

    return concatenate(sort(less, task), pivot, sort(greater, task));
}

private ArrayList<Integer> concatenate(ArrayList<Integer> less, int pivot, ArrayList<Integer> greater) {

    ArrayList<Integer> list = new ArrayList<>();

    for (int i = 0; i < less.size(); i++) {
        list.add(less.get(i));
    }

    list.add(pivot);

    for (int i = 0; i < greater.size(); i++) {
        list.add(greater.get(i));
    }

    return list;
}

}

4

3 に答える 3

1

他の人は、コードが正常に動作するため、おそらくオリジナルを印刷していると考えています。

代わりにこれを試すことができます。これにより、その場でソートされるため、予期しない動作が少なくなり、効率がわずかに向上します。私が行ったのはconcatenate、結果を配置する場所である新しいパラメーターを取得することだけです。

ところで：比較する前に to を引き出すことをお勧めしますif (i == middle) { continue; }。これも少し効率的です。

static class QuickSort {

  public static ArrayList<Integer> sort(ArrayList<Integer> array) {

    if (array.size() <= 1) {
      return array;
    }

    int middle = (int) Math.ceil((double) array.size() / 2);
    int pivot = array.get(middle);

    ArrayList<Integer> less = new ArrayList<>();
    ArrayList<Integer> greater = new ArrayList<>();

    for (int i = 0; i < array.size(); i++) {
      if (array.get(i) <= pivot) {
        if (i == middle) {
          continue;
        }
        less.add(array.get(i));
      } else {
        greater.add(array.get(i));
      }
    }

    return concatenate(sort(less), pivot, sort(greater), array);
  }

  private static ArrayList<Integer> concatenate(ArrayList<Integer> less, int pivot, ArrayList<Integer> greater, ArrayList<Integer> list) {

    list.clear();

    for (int i = 0; i < less.size(); i++) {
      list.add(less.get(i));
    }

    list.add(pivot);

    for (int i = 0; i < greater.size(); i++) {
      list.add(greater.get(i));
    }

    return list;
  }
}

次のように連結をさらに改善できます。

    list.clear();
    list.addAll(less);
    list.add(pivot);
    list.addAll(greater);
于 2012-12-07T16:34:40.670 に答える
0

実際の並べ替えは行っていません。すべてを小さなリストに入れてから、大きなリストに戻すだけです。そこでいくつかの比較が必要です。

連結メソッドを見てください。あなたはただ少ないリストを少ないリストに戻しているだけです。値をピボットと比較して、その値をどこに配置するかを決定する必要があります。

編集：私の最初の考えは間違っていました。私はあなたのコードをテストしました、そしてそれは働きました。

渡した配列を出力していると思いますか？ソート関数に渡す実際の配列はソートされないことに注意してください。1つだけが戻ってきました。

于 2012-12-07T16:03:27.197 に答える
-1

array.get（i）は整数を返します。ラップされた整数を抽出する必要があります。そうでない場合は、ポインターを比較します。

于 2012-12-07T16:03:40.760 に答える