1

要素が Comparable を実装している限り、ジェネリック リストで再帰的なマージ ソートを行うクラスがあります。mergeSort(List toSort) という void メソッドと、既に並べ替えられた 2 つのリストを取得し、それらを 1 つの並べ替えられたリストに結合するメソッド mergeSortedLists(List left, List right) があります。問題は、mergeSort(...) メソッドが toSort 変数を操作していないように見えることです。それはそうですが、レベルを上げた後、変更は表示されません。並べ替え方法は次のとおりです。

public static <E extends Comparable<E>> void mergeSort(List<E> toSort)
{
  if(toSort.size() > 1)
  {
    List<E> temp = toSort.subList(0, toSort.size()/2);

    ArrayList<E> left = new ArrayList<E>(0);
      for(E e : temp) left.add(e);

    temp = toSort.subList(toSort.size()/2, toSort.size());

    ArrayList<E> right = new ArrayList<E>(0);
      for(E e : temp) right.add(e);

    if(right.size() != 1) mergeSort(right);
    if(left.size() != 1) mergeSort(left);

    toSort = mergeSortedLists(left, right);
  }
}


public static <E extends Comparable<E>> List<E> mergeSortedLists(List<E> leftList, List<E> rightList)
{
  ArrayList<E> list = new ArrayList<E>();

  while(!leftList.isEmpty() && !rightList.isEmpty())
  {
    if((leftList.get(0)).compareTo(rightList.get(0)) <= 0)
      list.add(leftList.remove(0));

    else
      list.add(rightList.remove(0));
  }

  while(!leftList.isEmpty())
    list.add(leftList.remove(0));

  while(!rightList.isEmpty())
    list.add(rightList.remove(0));

  return list;
}

私は通常、エラーチェック用の print ステートメントを持っています。それらは、mergeSortedLists(...) が正しくソートされ、正しいリストを返すことを示しています。次に、mergeSort(...) の toSort 変数を、mergeSortedLists(...) が返すものに割り当てます。その割り当ては機能します。ここで、そのリストを別のリストと結合するためにレベルを上にジャンプすると、変更が失われたように見えます。何が起こっているのかわかりません。

4

2 に答える 2

1

これの代わりに

toSort = mergeSortedLists(left, right);

試す

toSort.clear();
toSort.addAll(mergeSortedLists(left, right));

アプローチの問題は、リストへの参照をリセットすることですが、それは元の関数に伝播しません。提案されたバージョンは、参照が与えられた元のリストを操作します。参照を変更しないため、元のリストへの変更は、関数が戻った後に呼び出し元に表示されます。

明確にするために：関数に引数を渡すと、関数内のローカル変数として機能するその引数のコピーが作成されます。その変数自体の値に変更を加えると、それらの変更は元のファイル（関数が呼び出されたときにコピーが作成された元）ではなく、コピーに加えられます。提案されたバージョンでは、コピーは参照であるため、参照はコピーされますが、オブジェクト（ここではlist）はコピーされないため、2つの参照は同じオブジェクトを指します。したがって、コピー（ローカル変数）を介してオブジェクトに加えられた変更は、関数が戻ったときに「表示」されます。

于 2012-04-26T23:36:11.500 に答える
1

パラメータ（オブジェクトへの参照も！）はJavaで値toSortによって渡されるため、呼び出し元の関数ではなく、のローカルコピーを変更します。これを回避する1つの方法は、渡したリストを再度返すことです。

public static <E extends Comparable<E>> List<E> mergeSort(List<E> toSort)

次に、次のように言います。

right = mergeSort(right);

など、および使用して戻ります：

return mergeSortedLists(left, right);

残りのコードを完全に読んだわけではありませんが、うまくいけば、正しい行にたどり着くはずです:)

于 2012-04-26T23:32:38.827 に答える