JavaScript快速排序中的无限递归

Infinite recursion in JavaScript quicksort?

本文关键字：无限 递归 快速排序 JavaScript      更新时间：2023-09-26

这是我编写的快速排序代码。函数无法工作，因为它无法到达基本情况。如果我将pivot、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));
    }
}

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

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

如果选择数组中最大的值作为pivot元素，则data的所有值都将出现在数组l中，而r中没有任何值。因此，将使递归永远不会停止（并使l、r和pivot保持相同的值）。除非这是一项脑力锻炼，否则使用data.sort()应该会做得更好。）

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

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

相关文章：