本文参考渡一内容以及这篇博客
https://www.cnblogs.com/lvmylife/p/7208541.html
冒泡排序
双重循环
function bubble (arr)
for(var i = 0; i < arr.length - 1;i++){
for(var j = i + 1;j < arr.length;j++){
if(arr[i] > arr[j]){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
return arr;
}
快速排序:版本1.0
var arr = [1, 5, 2, 9, 8, 5, 3, 65, 7, 5, 6, 56, 1];
function quickArr(arr) {
var left = [],
right = [];
if(arr.length <= 1) {
return arr;
}
var pIndex = Math.floor(arr.length / 2);
var p = arr.splice(pIndex,1)[0];
for(var i = 0; i < arr.length; i++) {
if(arr[i] <= p) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickArr(left).concat([p],quickArr(right));
}
这么写是有bug的,返回的数组是正常的,但因为splice会把影响原来的arr.
可以对参数进行处理.
快速排序版本1.1
var arr = [1, 5, 2, 9, 8, 5, 3, 65, 7, 5, 6, 56, 1];
function quickArr(arr) {
var arr = [].concat(arr);//这样就不会对原数组产生影响,似乎也是纯函数的思想.
var left = [],
right = [];
if(arr.length <= 1) {
return arr;
}
var pIndex = Math.floor(arr.length / 2);
var p = arr.splice(pIndex,1)[0];
for(var i = 0; i < arr.length; i++) {
if(arr[i] <= p) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickArr(left).concat([p],quickArr(right));
}
当然问题的根本在于用了splice,我们大可以不用splice
快速排序2.0
var arr = [1, 5, 2, 9, 8, 5, 3, 65, 7, 5, 6, 56, 1];
function quickArr(arr) {
var left = [],
right = [],
key = arr[0],
mid = [key],
len = arr.length;
if(len <= 1) {
return arr
}
for(var i = 1; i < len; i++) {
//其实这种for循环的边界设置,才是最微妙的地方..
if(arr[i] < key) {
left.push(arr[i]);
}else if(arr[i] > key){
right.push(arr[i]);
}else {
mid.push(arr[i]);
}
}
return quickArr(left).concat(mid,quickArr(right));
}
console.log(quickArr(arr));
快速排序2.1 可能的bug
为什么一定要把基准数给剔除来?
var arr = [1, 5, 2, 9, 8, 5, 3, 65, 7, 5, 6, 56, 1];
function quickArr(arr) {
var left = [],
right = [],
key = arr[0],
mid = [key],
len = arr.length;
if(len <= 1) {
return arr
}
for(var i = 0; i < len; i++) {//这里改成0
if(arr[i] < key) {
left.push(arr[i]);
}else if(arr[i] > key){
right.push(arr[i]);
}else {
mid.push(arr[i]);
}
}
return quickArr(left).concat(quickArr(right));//这里去掉mid
}
console.log(quickArr(arr));
这样会报错,会进入死循环,因为最后[1,1]的时候,len等于2,
然后死循环.
