JavaScript 快速排序中的无限递归？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14761032/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Infinite recursion in JavaScript quicksort?
提问by Yujun Wu
Here is the quicksortcode I wrote. The function doesn't work because it can't reach the base case. If I log the pivot, rand lto the console, they remain the same no matter how many times the sort function is called. So I wonder if the argument l, rare not really passed into the function as data. Why did it happen?
这是我写的快速排序代码。该函数不起作用，因为它无法达到基本情况。如果我记录数据透视表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));
}
}
回答by templatetypedef
I think that the issue here is that your partitioning step does not necessarily shrink the input array. For example, let's trace what happens if you try sorting [1, 2]. In this case, your pivot element will be the element 2. Since 1 > 2 is false, 1 is added to the list l. Since 2 > 2 is false, 2 is added to the list l. As a result, your recursive call on the list lwill have exactly the same arguments as your original call, causing infinite recursion.
我认为这里的问题是您的分区步骤不一定缩小输入数组。例如，让我们跟踪如果您尝试对 [1, 2] 进行排序会发生什么。在这种情况下，您的枢轴元素将是元素 2。由于 1 > 2 为假，因此将 1 添加到列表中l。由于 2 > 2 为假，因此将 2 添加到列表中l。因此，您对列表的递归调用l将与原始调用具有完全相同的参数，从而导致无限递归。
To fix this, try splitting the input into three lists - one of smaller values, one of equal values, and one of greater values. This code is shown here:
要解决此问题，请尝试将输入拆分为三个列表 - 一个较小的值、一个相等的值和一个较大的值。此代码显示在此处：
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));
}
}
This new version explicitly groups the equal elements into their own list, so they aren't recursively sorted by either of the recursive calls. It also gracefully handles duplicate elements.
这个新版本明确地将相等的元素分组到它们自己的列表中，因此它们不会通过任何一个递归调用进行递归排序。它还可以优雅地处理重复元素。
Hope this helps!
希望这可以帮助！
回答by Clemens Klein-Robbenhaar
If you pick the largest value of the array as the pivot element, then all values of datawill end up in the array land none in r. Thus will make the recursion never stop (and keep l, rand pivotat the same values).
Unless this is a brain excercise, using data.sort()should do a better job. ;)
如果您选择数组的最大值作为枢轴元素，则 的所有值都data将在数组中结束，l而在r. 因此将使递归永不停止（并保持l,r并保持pivot相同的值）。除非这是一个大脑练习，否则使用data.sort()应该会做得更好。;)
回答by Clemens Klein-Robbenhaar
JavaScript passes objects by reference (arrays are objects too). If you want to pass them by value, you need to use the splice function as explained here.
JavaScript 通过引用传递对象（数组也是对象）。如果要按值传递它们，则需要使用此处解释的 splice 函数。
Note that this will create a lot of copies of your data. You probably want to use the native sort() function.
请注意，这将创建大量数据副本。您可能想要使用本机 sort() 函数。
