var arr = [111,2,311,'a',20,90,445];
var quickSort = function(arr) {
if (arr.length <= 1) {
return arr;
} else {
//split for center
var pivotIndex = Math.floor(arr.length / 2);
//get center value
var pivot = arr.splice(pivotIndex, 1)[0];
console.log(pivot)
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
}
//call me loop
return quickSort(left).concat([pivot], quickSort(right));
};
console.log(quickSort(arr));
这样是可以运行的,但是删掉判断数组长度那一段就报错
var arr = [111, 2, 311, 'a', 20, 90, 445];
var quickSort = function(arr) {
//split for center
var pivotIndex = Math.floor(arr.length / 2);
//get center value
var pivot = arr.splice(pivotIndex, 1)[0];
console.log(pivot)
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
//call me loop
return quickSort(left).concat([pivot], quickSort(right));
};
console.log(quickSort(arr));
这样就报错了。为嘛?
报错信息发出来看看
递归调用你没有返回,就会一直不停的调用下去,成了死循环(递归)了
因为quickSort
函数并不是调用一次,而是会不断的调用自己,注意看函数的最后一句。
每次递归调用的时候,数组长度都不同,而递归必须最终能够返回,快速排序才能出结果,否则就会一直递归下去,直到内存耗尽出现栈溢出错误,程序奔溃。
如果对递归不熟悉,可能不太容易理解整个过程。你可以试着运行下面的简单程序,体会一下递归的过程,你的这个快速排序的思想跟这个是类似的(仅就递归而言)。
var calcSum = function(n) {
if (n == 1) return 1;
return n + calcSum(n-1);
};
var sum = calcSum(5); // 计算1~5的和
确实是这样的,递归结束之后是要有返回的,不然函数永远都结束不掉了!
这是递归函数啊,没有判断会一直执行,当arr.length=1时不添加判断继续执行的话var pivotIndex = Math.floor(arr.length / 2); pivotIndex=0 然后下次执行该函数是 有一个数组长度为0自然就报错了