1

1 つはインプレースで、もう 1 つは別の配列を使用して、2 つの方法でクイックソートをコーディングしようとしています。私はいくつかのロジックに行き詰まっています。私が持っているものを見てください。事前に助けてくれてありがとう!

public List<Integer> sort(List<Integer> arr){
  if(arr.length > 0)
    List<Integer> ret = new ArrayList<Integer>();
  ret = quickSort(arr);
  return ret;
 }

public List<Integer> quickSort(List<Integer> arr){
  if(arr.length < 2)
    return;

  int pivot = arr[0];
  List<Integer> left = new ArrayList<Integer>();
  List<Integer> right = new ArrayList<Integer>();

  for(int i = 0; i < arr.length; i++){
    if(arr[i] <= pivot)
      left.add(arr[i]);
    else
      right.add(arr[i]);
  }
  quickSort(left);
  quickSort(right);

}

今、私は立ち往生しています。両方のセットを再帰的に通過した後、どうすればよいかわかりません。ほとんどの場合、それらを接続してソートされたリストを返す方法に固執しています。

4

3 に答える 3

1

left組み合わせてrightシーケンスする必要があります。アルゴリズムの最後 (終了前) でそれを行う必要があります}。擬似コード:

int leftpos = 0, rightpos = 0;
List newlist = new ArrayList();
for(int pos = 0; pos < arr.length; pos++)
  if left[pos] < right[pos] newlist.add(left[leftpos++]);
    else newlist.add(right[rightpos++]);
return newlist;

これは単なる疑似コードです。for サイクルで各配列 (leftおよび)の長さをチェックするコードを追加する必要があります。right

また、これはクイックソートとはほど遠いことに注意する必要があります。非常に多くのnew配列割り当てにより、アルゴリズムが非常に遅くなり、並べ替え時には歓迎されません。

また、3 行目の右側は冗長です。次の行で上書きされるため、ここでは何も割り当てる必要はありません。3〜5行目を次のように置き換えるだけです：

return quickSort(arr);
于 2012-11-28T03:08:52.093 に答える
0

私はあなたのためにこれをクラックさせてください.

まず、リンクリストを使用していない限り、常にインプレース ソートを実行する必要があります (その場合でも、通常は、配列に変換し、その場でソートしてから、リンク リストに戻すのに費用がかかります。ガベージコレクターへの圧力）。.NET List<> は、実際には展開配列です。

次に、クイックソートはピボット操作がすべてです。これを行う1つの方法は次のとおりです。

// Quicksort the sub-array xs[lo..hi].
void QSort(int[] xs, int lo, int hi) {
    if (hi <= lo) return; // Don't sort empty or singleton sub-arrays.
    var p = [choose some pivot value from xs[lo..hi]];
    var a = lo; // Invariant: x[lo..a - 1] <= p.
    var z = hi; // Invariant: p < x[z + 1..hi].
    while (a <= z) {
        if (xs[a] <= p) a++; else Swap(xs, a, z--);
    }
    QSort(xs, lo, a - 1); // Sort the items <= p.
    QSort(xs, z + 1, hi); // Sort the items > p.
}

void Swap(int[] xs, int i, int j) {
    var tmp = xs[i];
    xs[i] = xs[j];
    xs[j] = tmp;
}
于 2012-11-28T04:34:04.373 に答える