31

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

3 回答 3

337

我认为这里的问题是您的分区步骤不一定会缩小输入数组。例如，让我们跟踪如果您尝试对 [1, 2] 进行排序会发生什么。在这种情况下，您的枢轴元素将是元素 2。由于 1 > 2 为假，因此将 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)); 
  }
}

这个新版本明确地将相等的元素分组到它们自己的列表中，因此它们不会被任何一个递归调用递归排序。它还优雅地处理重复元素。

希望这可以帮助！

于 2013-02-07T21:20:43.063 回答
1

如果您选择数组的最大值作为枢轴元素，那么 的所有值都data将在数组中结束，l而在r. 因此将使递归永远不会停止（并保持l,r和pivot相同的值）。除非这是一项大脑练习，否则使用data.sort()应该做得更好。;)

于 2013-02-07T21:25:24.497 回答
0

JavaScript 通过引用传递对象（数组也是对象）。如果要按值传递它们，则需要使用此处说明的 splice 函数。

请注意，这将创建大量数据副本。您可能想要使用本机 sort() 函数。

于 2013-02-07T21:23:21.063 回答