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