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