2

だから私はjavascriptに非常に慣れていない（cから来た）ので、いくつかの演習で練習しながら構文を学び始めたばかりです。クイックソートアルゴリズムを実装しました:

function sort(a)
{
    var _sort = function(l, r)
    {
        if (l >= r - 1)
            return;
        var p = r - 1;
        var y = l;
        var tmp;
        for (var i = l; i < r - 1; i++)
            if (a[i] < a[p])
            {
                tmp = a[i];
                a[i] = a[y];
                a[y] = tmp;
                y++;
            }
        tmp = a[y];
        a[y] = a[r - 1];
        a[r - 1] = tmp;
        _sort(l, y);
        _sort(y + 1, r);
    }

    _sort(0, a.length);
}

小さな配列では問題なく動作しますが、5000 要素を超える配列ではスタック サイズの制限を超えてしまいます。増やそうとしましたが、うまくいきませんでした。アルゴリズムの実装方法に何か問題があると思われますが、そうでしょうか?

私の質問は、それを機能させるために、どのようにアルゴリズムを実装するか、スタックサイズの制限を回避する必要がありますか (5000 要素の配列は小さいと思います)? また、スタイルの提案もいただければ幸いです。

4

2 に答える 2

4

配列を使用してスタックをシミュレートできますが、これはより長くなる可能性があります。これで非常に限られたテストを行いましたが、うまくいくようでした。

function sort(a) {
  var stack = [[0, a.length]];
  while (1) {
    var stackLength = stack.length;
    if (! stackLength) {
      break;
    }
    var l = stack[stackLength - 1][0], 
        r = stack[stackLength - 1][1];
    if (l >= r - 1) {
      stack.pop();
      continue;
    }
    var p = r - 1;
    var y = l;
    var tmp;
    for (var i = l; i < r - 1; i++)
      if (a[i] < a[p])
    {
      tmp = a[i];
      a[i] = a[y];
      a[y] = tmp;
      y++;
    }
    tmp = a[y];
    a[y] = a[r - 1];
    a[r - 1] = tmp;
    stack.pop();
    stack.push([y + 1, r]);
    stack.push([l, y]);
  }
  return a;
}
于 2013-07-21T00:40:55.020 に答える
4

ご存じのように、クイックソートは、既にソート済みまたはリバース ソート済みの入力に対して、病理学的にパフォーマンスが低下します。このような場合、O(n) スタック スペースを使用することになり、スタック オーバーフロー エラーが発生する可能性があります。

これらの問題を回避するために、ピボット要素 "y" を 3 つ (最初、中間、最後) の中央値として選択できますが、その場合でも病的なパフォーマンスを引き起こすシーケンスがあるようです。この問題を完全に取り除くには、代わりにマージソートまたはヒープソートを実装できます。または、再帰を使用する代わりに配列をスタックとして使用します。

于 2013-07-21T00:52:11.270 に答える