31

これが私が書いたクイックソートコードです。基本ケースに到達できないため、関数は機能しません。ピボットをコンソールに記録するrとl、並べ替え関数が何回呼び出されても同じままです。したがって、引数l,rが実際にはデータとして関数に渡されていないのではないかと思います。なぜそれが起こったのですか？

function sort(data){
    if(data.length < 2){
        return data;
    }
    else{
        var l = [];
        var r = [];
        var pivot = parseInt(data.length/2);
        for(i=0; i<data.length; i++){
            if(data[i] > data[pivot]){
                r.push(data[i]);
            }
            else{
                l.push(data[i]);
            }
        }
        return sort(l).concat(sort(r));
    }
}
4

3 に答える 3

337

ここでの問題は、パーティション分割のステップが必ずしも入力配列を縮小するとは限らないことだと思います。たとえば、[1, 2] を並べ替えてみるとどうなるかをたどってみましょう。この場合、ピボット要素は要素 2 になります。1 > 2 は false なので、リストに 1 が追加されますl。2 > 2 は false であるため、リストに 2 が追加されますl。その結果、リストの再帰呼び出しはl元の呼び出しとまったく同じ引数になり、無限再帰が発生します。

これを修正するには、入力を 3 つのリスト (小さい値、等しい値、大きい値の 1 つ) に分割してみてください。このコードを次に示します。

function sort(data){
  if (data.length < 2){
    return data;
  } else {
    var l = [];
    var r = [];
    var e = [];
    var i = 0;
    var pivot = (data.length / 2) | 0;

    for(i = 0; i < data.length; i++) {
      if (data[i] > data[pivot]) {
        r.push(data[i]);
      } else if (data[i] < data[pivot]) {
        l.push(data[i]);
      } else {
        e.push(data[i]);
      }
    }  
    return sort(l).concat(e, sort(r)); 
  }
}

この新しいバージョンは、等しい要素を明示的に独自のリストにグループ化するため、再帰呼び出しのいずれによっても再帰的にソートされません。また、重複する要素を適切に処理します。

お役に立てれば！

于 2013-02-07T21:20:43.063 に答える
1

If you pick the largest value of the array as the pivot element, then all values of data will end up in the array l and none in r. Thus will make the recursion never stop (and keep l, r and pivot at the same values). Unless this is a brain excercise, using data.sort() should do a better job. ;)

于 2013-02-07T21:25:24.497 に答える
0

JavaScriptは参照によってオブジェクトを渡します（配列もオブジェクトです）。それらを値で渡したい場合は、ここで説明するようにスプライス関数を使用する必要があります。

これにより、データのコピーが大量に作成されることに注意してください。おそらく、ネイティブのsort（）関数を使用することをお勧めします。

于 2013-02-07T21:23:21.063 に答える