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

Question

这是 quicksort我写的代码。该功能不起作用，因为它无法达到基本情况。如果我将数据透视表、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));
    }
}

Answer 1

我认为这里的问题是您的分区步骤不一定会缩小输入数组。例如，让我们跟踪如果您尝试对 [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)); 
  }
}

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

希望这对您有所帮助!