最为入门必学的排序算法, 冒泡排序可谓是陪伴了每个programmer的职业生涯

记录


时间复杂度

O(n ^ 2)

空间复杂度

O(1)

思路


思路一

  • 外层循环遍历基数
  • 内层遍历交换
1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(arr) {
const len = arr.length;

for(let i = 0; i < len - 1; i++) {
for(let j = i + 1; j < len; j++) {
arr[i] > arr[j] && (
[arr[i], arr[j]] = [arr[j], arr[i]];
);
}
}

return arr;
}

思路二(改进)

  • 记录最后一次交换的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubbleSort(arr) {
let pos = arr.length - 1;
let i = 0;

while (i <= pos) {
for(let j = i + 1; j < arr.length; j++) {
if(arr[i] > arr[j]) {
pos = j + 1;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
i++;
}

return arr;
}