一. 冒泡排序
1. 外循环控制轮数: 数组长度 - 1
- -1: 比较中的总个数 -1 (如: 两个数只需要比较1轮; 5个数需要比较4轮)
2. 内循环控制每轮比较数: 数组长度 - 当前轮数 - 1
- -1: 防止下标越界
- -当前轮数: 每比较一轮根据前一轮,依次少比较一个数
var arr = [3, 2, 5, 1, 4];
for (var i = 0; i < arr.length - 1; i++) {
for (var j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
console.log(arr); // [1, 2, 3, 4, 5]
二. 选择排序(打擂台法)
- 每一轮比较出一个最大数或最小数
- 将这个比较出来的数与当前轮最前面的那个数进行交换
- 每轮仅交换一次
1. 外层循环控制轮数: 数组长度 - 1
- -1: 比较中的总个数 -1 (如: 两个数只需要比较1轮; 5个数需要比较4轮)
2. 内层循环控制每次比较的次数: j = i+1; j < arr.length
- 每轮从j = i+1开始比较, 每比较一轮就往后依次少比较一个数(因为比较出来的那个数已经放到当前轮数的最前面)
- 每次比较都需要比较到数组没比完的每一个数
- 每轮比较完之后才交换一次
var arr = [3, 5, 2, 6, 9];
for (var i = 0; i < arr.length - 1; i++) {
var win = i; // 假设当前i是当前轮遍历出来最大/最小值的下标
for (var j = i + 1; j < arr.length; j++) {
if (arr[win] > arr[j]) {
win = j;
}
}
if (win != i) {
var temp = arr[win];
arr[win] = arr[i];
arr[i] = temp;
}
}
console.log(arr); // [2, 3, 5, 6, 9]
三. 快速排序(递归)
- 判断数组的长度是否大于2, 若不大于, 则返回当前数组
- 找中间下标, 向下取整
- 通过中间下标, 得到中间数; 把中间数从原来的数组中剔取出来
- 准备两个空数组, left[], right[], 循环原来的数组(已经剔取出中间数的那个数组)与中间数进行比较; 如果大于中间数, 放right[], 否则放left[]
function quickSort(arr) {
// (1)判断数组的长度是否大于2 -> 如果小于2,就返回当前数组
if (arr.length < 2) {
return arr;
}
// (2)找中间下标,向下取整
var middleIndex = parseInt(arr.length / 2);
// (3)通过中间下标,得到中间数 -> 把中间数从原来的数组中提取出来
var middleValue = arr[middleIndex];
// 把原数组中的中间数删除
arr.splice(middleIndex, 1);
// (4)准备2个空数组 left[],right[],循环原来的数组(已经提取出中间数的那个数组)与中间数,比较 -> 如果大于中间数,放右边,否则放左边
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] > middleValue) {
right.push(arr[i]);
} else {
left.push(arr[i]);
}
}
// (5) 拼接拆分过后排好序的数组和中间数
return quickSort(left).concat(middleValue, quickSort(right));
}
console.log(quickSort([2, 1, 8, 4, 5, 3, 7])); // [1, 2, 3, 4, 5, 7, 8]
四. 高阶函数
1. arr.forEach(callback)
- 纯粹的遍历方法, 没有返回结果
- 格式: arr.forEach(function(每项元素, 下标, 原数组){})
- 不能被break, return中断, 可以使用抛出异常强制中断
- throw new Error('error') 抛出异常
- throw new Error('error') 常常配合 try...catch...finally
- try...catch...finally 捕获异常,用于有可能出现问题的地方
- finally 不管是否出错都会执行, 可写可不写
try{
arr.forEach(function(item, index, arr){
console.log(item, index, arr);
if(index == 1){
throw new Error("故意的error"); // 中断执行
}
});
} catch (err){
console.log(err);
}
2. arr.map(callback)
- 能做遍历
- 返回的结果是一个数组, 数组里的内容, 根据 return 决定
- 格式: arr.map(function(每项元素, 下标, 原数组){ return })
var arr = [1, 2, 3]
var res = arr.map(function(item, index, arr){
return item*10;
});
console.log(res); // [10, 20, 30]
3. arr.filter(callback)
- 根据条件, 返回一个新的数组
- 格式: arr.filter(function(每项元素, 下标, 原数组){ return })
var arr = [1, 2, 3, 4, 5];
var res = arr.filter(function(item, index, arr) {
return item > 2;
});
console.log(res); // [3, 4, 5]
4. arr.som(callback)
- 只要有一个条件满足, 就返回true
- 格式: arr.some(function(每项元素, 下标, 原数组){ return })
var arr = [11, 22, 33, 44];
var res = arr.some(function(item, index, arr) {
return item > 20;
});
console.log(res); // true
5. arr.every(callback)
- 所有条件都满足, 才返回true
- 格式: arr.every(function(每项元素, 下标, 原数组){ return })
var arr = [11, 22, 33, 44];
var res = arr.every(function(item, index, arr) {
return item > 20;
});
console.log(res); // false
6. arr.reduce(callback, param)
- 数组逐项处理
- reduce可以有一个参数或两个参数
- 一个参数
- 格式: arr.reduce(function(pre, cur, index, arr){})
- pre从第一个下标开始取值, 往后的取值为return的返回值, 若没有return, 则默认取undefined
- cur从第二个下标开始取值, 依次往后推
var arr = [10, 20, 30];
var res = arr.reduce(function(pre, cur, index, arr) {
return pre + cur;
});
console.log(res); // 60
- 两个参数
- 格式: arr.reduce(function(pre, cur, index, arr){}, param)
- pre开始取param为值, 往后的取值为return的返回值, 若没有return, 则默认取undefined
- cur默认从第一个下标开始取值, 依次往后推
var arr = [10, 20, 30];
var res = arr.reduce(function(pre, cur, index, arr) {
return pre + cur;
}, 10);
console.log(res); // 70
// 练习:使用reduce()实现返回一个比原数组大十倍的新数组
var arr = [1, 2, 3, 4, 5];
var res = arr.reduce(function(pre, cur, index, arr) {
pre.push(cur * 10);
return pre;
}, []);
console.log(res); // [10, 20, 30, 40, 50]
