JavaScript快速排序中的无限递归？

Question

这是我写的快速排序代码.该功能不起作用,因为它无法到达基本情况.如果我记录枢轴r和l控制台,无论调用sort函数多少次,它们都保持不变.所以我想如果参数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));
    }
}

Answer 1

我认为这里的问题是你的分区步骤不一定会缩小输入数组.例如,让我们跟踪如果您尝试排序[1,2]会发生什么.在这种情况下,您的pivot元素将是元素2.由于1> 2为false,因此将1添加到列表中l.由于2> 2为假,因此将2添加到列表中l.因此,对列表的递归调用l将与原始调用具有完全相同的参数,从而导致无限递归.

要解决此问题,请尝试将输入拆分为三个列表 - 一个较小的值,一个相等的值和一个较大的值.此代码显示在此处:

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

这个新版本显式地将相等的元素组合到它们自己的列表中,因此它们不会通过任何递归调用进行递归排序.它还优雅地处理重复元素.

希望这可以帮助!