一、基本思想
-
依次比较相邻两个数的大小，较小的数下沉，较大的数冒起来
冒泡排序.gif
二、算法实质
- 从第一个数开始遍历数组，每一次遍历都找出此次遍历的最大值，放到队伍的末尾
- 第2次遍历，最后一项不必再比较，数组长度减一，最大值放到此次数组的末尾
- 第3次再减一......直到最后，所有数字都按从小到大排列
三、基础算法
- 优先选出大的放右边
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) { // 相邻的比较大小，大的放右边
let temp = arr[j]; // [arr[j], arr[j + 1]] = [arr[j+1], arr[j]]
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
四、复杂度
- 空间上只用了一个辅助单元，所以为 O(1)
- 第1次遍历为n-1次，第2次n-2次......第i次n-i次，总次数=1/2n(n-1)，则时间复杂度为O(n2)
五、算法改进
1、外层减少循环次数
let flag = true; // 表示在一次循环中是否发生了数据交换
for (let i = 0; i < arr.length - 1; i++) {
// flag为false时，上一次循环已经没有发生数据交换，证明顺序已经排完了
if (!flag) {
break;
}
flag = false; // 每次循环都先置为false，即认为不会发生交换
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
flag = true; // 发生数据交换，则要继续比较
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
2、内层减少循环次数
let k = arr.length -1; // 动态k，记录上一次内循环的上界值，因为k以后的数没有再发生数据交换，证明k以后的数顺序正确，则下一次的内循环只需比较截止到位置k的数
for (let i = 0; i < arr.length - 1; i++) {
let lastFlag = 0; // 用于记录内循环交换数据的位置，每次循环初始化为0
for (let j = 0; j < k - i; j++) {
if (arr[j] > arr[j + 1]) {
lastFlag = j; // 记录最后一次交换数据的位置
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if (lastFlag === 0) { // 内循环不再交换，则排序结束，外循环也可break掉
break;
}
k = lastFlag; // 让下一次循环的上界值变成此次循环的最后一次交换的位置
}
六、算法变形
1、优先选出小的放右边
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] < arr[j + 1]) { // 相邻的比较大小，小的放右边
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
2、由大到小排列，但无法引入内循环标志位
- 跟冒泡基础算法的查找次数是一样的，本质上就是一个两层循环（每循环一次找出最大值放到第一个，并下一次循环次数减一）。
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] < arr[j]) { // 优先选出大的放左边
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
