版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
一、数组的常见算法
由于算法的性能要从时间复杂度和空间复杂度两个方面考虑，所以这里不做性能的研究，仅仅为了理解
1、冒泡排序：
假设有数组[54, 68, 46, 75, 36, 20, 65, 11, 79, 45]
var list = [54, 68, 46, 75, 36, 20, 65, 11, 79, 45]; // 要排序的数组
需求：从小到大排列数组
因为我们要把大的数放在后面，所以我们每个数都和右边的数比较，如果左边的数大于右边的数，就将两个数换位置
循环一圈后，就能得到最大的值，放在最右边，每次循环一圈，就能得到相对最大的值放在最右边
第一轮 就得到最大值 j=0
54 68 [54, 68, 46, 75, 36, 20, 65, 11, 79, 45]
68 46 [54, 46, 68, 75, 36, 20, 65, 11, 79, 45]
68 75 [54, 46, 68, 75, 36, 20, 65, 11, 79, 45]
75 36 [54, 46, 68, 36, 75, 20, 65, 11, 79, 45]
75 20 [54, 46, 68, 36, 20, 75, 65, 11, 79, 45]
75 65 [54, 46, 68, 36, 20, 65, 75, 11, 79, 45]
75 11 [54, 46, 68, 36, 20, 65, 11, 75, 79, 45]
75 79 [54, 46, 68, 36, 20, 65, 11, 75, 79, 45]
75 45 [54, 46, 68, 36, 20, 65, 11, 75, 45, 79]
for (var i = 0; i < list.length - 1; i++) { //第一次循环
if (list[i] > list[i + 1]) { // 68 46 //如果左边的值大于右边成立
var temp = list[i]; // 设置一个临时变量，将左边的值先存起来
list[i] = list[i + 1]; // 将右边的值赋给左边
list[i + 1] = temp; // 将临时变量中存的最初的左边的值给右边 完成一次交换位置
}
}
console.log(list);
第二轮 得到 第二大的值 j=1
54 46 [46, 54, 68, 36, 20, 65, 11, 75, 45, 79]
54 68 [46, 54, 68, 36, 20, 65, 11, 75, 45, 79]
68 36 [46, 54, 36, 68, 20, 65, 11, 75, 45, 79]
68 20 [46, 54, 36, 20, 68, 65, 11, 75, 45, 79]
68 65 [46, 54, 36, 20, 65, 68, 11, 75, 45, 79]
68 11 [46, 54, 36, 20, 65, 11, 68, 75, 45, 79]
68 75 [46, 54, 36, 20, 65, 11, 68, 75, 45, 79]
75 45 [46, 54, 36, 20, 65, 11, 68, 45, 75, 79]
75 79 [46, 54, 36, 20, 65, 11, 68, 45, 75, 79] //多余一次 由于第一次已经取到最大的值了，所以最后一次不用比较
for (var i = 0; i < list.length - 1; i++) { //第二次循环
if (list[i] > list[i + 1]) {
var temp = list[i]; // 设置一个临时变量，将左边的值先存起来
list[i] = list[i + 1]; // 将右边的值赋给左边
list[i + 1] = temp; // 将临时变量中存的最初的左边的值给右边 完成一次交换位置
}
}
console.log(list);
第三轮 得到 第三大的值 j=2
45 54 [46, 54, 36, 20, 65, 11, 68, 45, 75, 79]
54 36 [46, 36, 54, 20, 65, 11, 68, 45, 75, 79]
54 20 [46, 36, 20, 54, 65, 11, 68, 45, 75, 79]
54 65 [46, 36, 20, 54, 65, 11, 68, 45, 75, 79]
65 11 [46, 36, 20, 54, 11, 65, 68, 45, 75, 79]
65 68 [46, 36, 20, 54, 11, 65, 68, 45, 75, 79]
65 45 [46, 36, 20, 54, 11, 65, 45, 68, 75, 79]
65 75 [46, 36, 20, 54, 11, 65, 45, 68, 75, 79] //多余
75 79 [46, 36, 20, 54, 11, 65, 45, 68, 75, 79] //多余 //多余两次 由于前两次已经取到最大的值和第二大的值了，所以最后两次不用比较
......
所以完整的冒泡排序
var list = [54, 68, 46, 75, 36, 20, 65, 11, 79, 45]; // 要排序的数组
for (var j = 0; j < list.length - 1; j++) { //外层决定执行多少轮 因为最后一个元素没有下一个元素和他比较，所以 j要小于list.length - 1
for (var i = 0; i < list.length - 1 - j; i++) { // 内层从最左边开始比较，-j是为了性能优化，将多余的比较减掉
if (list[i] > list[i + 1]) {
var temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
}
}
}
console.log(list);
递归写法：
function maoPao(list, j) {
for (var i = 0; i < list.length - 1; i++) {
if (list[i] > list[i + 1]) { // 68 46
var temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
}
}
console.log(list);
if (j == 1) {
return list;
}
return maoPao(list, j - 1);
}
var list = [54, 68, 46, 75, 36, 20, 65, 11, 79, 45]; // 要排序的数组
maoPao(list, list.length); //10
// 这里的能用循环还是最好用循环，这里只是为了练习递归
2、选择排序：
假设我们有数组[54, 68, 46, 75, 36, 20, 65, 11, 79, 45]，我们要求从小到大的排列
var list = [54, 68, 46, 75, 36, 20, 65, 11, 79, 45];
选择排序和冒泡排序不同，冒泡排序每轮循环都要换很多次位置，而选择排序每次循环只换一次位置。
从下标0开始，与其后所有元素相比较，找到后面最小的值，然后与其交换位置
然后再从下标1开始找，找到后面最小的值，然后与其交换位置
var list = [54, 68, 46, 75, 36, 20, 65, 11, 79, 45];
for (var j = 0; j < list.length - 1; j++) {//0
var min = list[j]; // 把每次循环的次数对应的那个值保存下来
var minIndex = j; //把每次循环的次数对应的那个值对应的下标也保存下来
for (var i = j + 1; i < list.length; i++) {
if (min > list[i]) {
min = list[i];
minIndex = i;
}
}
// 内层for循环执行结束后，就一定能得到后面最小的那个值的下标和值
// 将当前的值和后面最小的值交换顺序
var temp = list[j];
list[j] = list[minIndex];
list[minIndex] = temp;
}
console.log(list);
3、快速排序(二分排序)：
这里利用递归来实现快速排序
① 选取待排序数组中其中一个数作为基数（这里选择了位置偏中间的数Math.floor(list.length / 2)），使midIndex等于基数的下标，将基数从数组中裁切下来，建立两个空数组,left数组和right数组
② 将数组中比基数小的数放到left数组中，比基数大的数放到rigth数组中。
③ 将基数左边的数组作为待排序数组，重复①步骤。
④ 将基数右边的数组作为待排序数组，重复①步骤。
⑤ 直到left和right的长度都小于2（数组长度为1或0），代表数组已经划分为最小单位(待排序数组长度小于等于1)，即该部分排序完毕，无需继续分割数组。
function quickSort(list) {
if (list.length < 2) {
return list;
}
var midIndex = Math.floor(list.length / 2);
var mid = list.splice(midIndex, 1)[0]; //返回的是数组
var left = [];
var right = [];
for (var i = 0; i < list.length; i++) {
if (list[i] < mid) {
left.push(list[i]);
} else {
right.push(list[i]);
}
}
// console.log(left, mid, right);
return quickSort(left).concat(mid, quickSort(right));
}
网友评论