冒泡排序算法
对数组进行 冒泡排序 ,是算法当中比较简单易理解的。
原理
数组中有 n 个数，比较每相邻两个数，如果前者大于后者，就把两个数交换位置；这样一来，第一轮就可以选出一个最大的数放在最后面；那么经过 n-1（数组的 length - 1） 轮，就完成了所有数的排序。
首先，通过一次循环，从而找到最大数放于数组队尾
1
2
3
4
5
6
7
8
9
| let arr = [3,4,1,2];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i],arr[i + 1]] = [arr[i + 1], arr[i]];
}
}
console.log(arr)
|
总计，重复 arr.length - 1 次，便可以实现数组按从小到大的顺序
1
2
3
4
5
6
7
8
9
10
11
| let arr = [3,4,1,2];
for (let j = 0; j < arr.length - 1; j++) {
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i],arr[i + 1]] = [arr[i + 1], arr[i]];
}
}
}
console.log(arr)
|
虽然上面的代码已经实现冒泡排序了，但就像注释中提到的，内层 for 循环的次数写成，i < arr.length - 1 ，是不是合适呢？
我们想一下，当第一次，找到最大数，放到最后，那么下一次，遍历的时候，是不是就不能把最后一个数算上了呢？因为他就是最大的了，不会出现，前一个数比后一个数大，要交换位置的情况，所以内层 for 循环的次数，改成 i < arr.length - 1 -j ，才合适，看下面的代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
| let arr = [3, 4, 1, 2];
function bubbleSort (arr) {
for (let j = 0; j < arr.length - 1; j++) {
// 这里要根据外层for循环的 j，逐渐减少内层 for循环的次数
for (let i = 0; i < arr.length - 1 - j; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i],arr[i + 1]] = [arr[i + 1], arr[i]];
}
}
}
return arr;
}
bubbleSort(arr);
|
此外，假如提前排序完成，但还会继续执行排序，因此需要一个标志位来判断是否提前结束排序，从而优化算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| let arr = [3, 4, 1, 2];
function bubbleSort (arr) {
let max = arr.length - 1;
for (let j = 0; j < max; j++) {
// 声明一个变量，作为标志位
let done = true;
for (let i = 0; i < max - j; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i],arr[i + 1]] = [arr[i + 1], arr[i]];
done = false;
}
}
if (done) {
break;
}
}
return arr;
}
bubbleSort(arr);
|
性能
时间复杂度： 平均时间复杂度O(n*n)、最好情况O(n)、最差情况O(n*n)
空间复杂度： O(1)
稳定性： 稳定
时间复杂度指的是一个算法执行所耗费的时间
空间复杂度指运行完一个程序所需内存的大小
稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面
不稳定指，如果a=b，a在b的前面，排序后可能会交换位置
总结
- 外层 for 循环控制循环次数
- 内层 for 循环进行两数交换，找每次的最大数，排到最后
- 设置一个标志位，减少不必要的循环
