最为入门必学的排序算法, 冒泡排序可谓是陪伴了每个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;
}