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

如您所知，对于已经排序或反向排序的输入，快速排序的性能非常糟糕。在这些情况下，您最终会使用 O(n) 堆栈空间，这可能会导致堆栈溢出错误。

为了避免这些问题情况，您可以选择枢轴元素“y”作为三个（第一个、中间和最后一个）的中位数，尽管显然即使在那时也有触发病理表现的序列。要完全摆脱这个问题，您可以实现合并排序或堆排序。或者使用数组作为堆栈而不是使用递归。

于 2013-07-21T00:52:11.270 回答
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 回答