Javascript快速排序算法实现

Question

所以我对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个元素的数组很小），才能使其工作？我也很乐意提供任何风格建议。

Answer 1

您可以用数组模拟堆栈，数组可以更长。我用这个做了非常有限的测试，但它似乎有效。

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;
}

Answer 2

正如您所知，对于已经排序或反向排序的输入，quicksort具有病态的糟糕性能。在这些情况下，您最终会使用O（n）堆栈空间，这可能会导致堆栈溢出错误。

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