数据结构与算法之排序: 冒泡排序 (Javascript版)

排序

• 排序：把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例)

冒泡排序

• 该排序属于 贪心 策略
• 关注的是局部，是一种苟且的东西
• 冒泡排序最简单，性能不好，工作中用不到
• 思路
  • 比较所有相邻元素，如果第一个比第二个大，则交换他们
  • 一轮下来，可以保证最后一个数是最大的
  • 执行n-1轮就可以完成排序了
  • 我们可以看到每一轮循环是不一样的，执行区间越来越短
  • 冒泡排序是一种贪心策略
• 动画示例：visualgo.net/zh/sorting

算法实现

1 ）version 1 初始版本

function bubbleSort(nums: number[]) {
  const len :number = nums.length;
  for(let i: number = 0; i < len; i++) {
      for(let j: number = 0; j < len - 1 - i; j++) {
          if(nums[j] > nums[j + 1]) {
              const tmp = nums[j];
              nums[j] = nums[j + 1];
              nums[j + 1] = tmp;
          }
      }
  }
}

const list: number[] = [5, 4, 3, 2, 1];
bubbleSort(list);
console.log(list); // [1, 2, 3, 4, 5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2 ） version 2 ES6 做两数交换 优化版

function bubbleSort(nums: number[]) {
  const len :number = nums.length;
  for(let i: number = 0; i < len; i++) {
      for(let j: number = 0; j < len - 1 - i; j++) {
          if(nums[j] > nums[j + 1]) {
            [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
          }
      }
  }
}

const list: number[] = [5, 4, 3, 2, 1];
bubbleSort(list);
console.log(list); // [1, 2, 3, 4, 5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3 ） version 3 冒泡排序，提前终止版

function bubbleSort(nums: number[]) {
    let len: number = nums.length;
    let sorted: boolean = false; // 哨兵变量
    while(!sorted) {
        sorted = true; // 提前终止标识
        for(let i: number = 0; i < len - 1; i++) {
            if(nums[i] > nums[i + 1]) {
                [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
                sorted = false;
            }
        }
        // 如果经过上面一轮 sorted仍为true，没有变为false, 说明已经整体已经有序，可以提前终止了
        len --;
    }
}

const list: number[] = [5, 4, 3, 2, 1];
bubbleSort(list);
console.log(list); // [1, 2, 3, 4, 5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4 ）version 4 冒泡排序，跳跃版

function bubbleSort(nums: number[]) {
    const len: number = nums.length;
    let k: number = len - 1; // 跳跃标识
    let last: number = 0; // 内层循环标识
    let i: number = 0;

    // 第一层循环表示经过n-1趟扫描即可，每比较一趟，问题规模缩小1级，第一层循环次数必须不变 n-1 次
    while(i < len - 1) {
        // 第二层循环表示每一趟进行两两逐个比较，找到最大的元素
        for(let j: number = 0; j < k; ++j) {
            // 当前元素和后一个元素进行比较，若逆序
            if(nums[j] > nums[j+1]) {
                // 则交换
                [nums[j], nums[j + 1]] = [nums[j  +1], nums[j]];
                // 更新交换的位置
                last = j;
            }
        }
        // 在一层循环之后跳跃到最后交换的那个地方，这样的话，在k的位置，后面如果是有序，就可以直接跳过了
        k = last;
        ++i;
    }
}

const list: number[] = [5, 4, 3, 2, 1];
bubbleSort(list);
console.log(list); // [1, 2, 3, 4, 5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

5 ）version 5 冒泡排序，提前终止+跳跃版

function bubbleSort(nums: number[]) {
    const len: number = nums.length;
    let k: number = len - 1; // 跳跃标识
    let last: number = 0; // 内层循环标识
    let i: number = 0; // 最外层循环标识
    let sorted: boolean = false; // 哨兵变量

    // 第一层循环表示经过n-1趟扫描即可，每比较一趟，问题规模缩小1级，第一层循环次数必须不变 n-1 次
    while(i < len - 1 && !sorted) {
        sorted = true;
        // 第二层循环表示每一趟进行两两逐个比较，找到最大的元素
        for(let j: number = 0; j < k; ++ j) {
            // 当前元素和后一个元素进行比较，若逆序
            if(nums[j] > nums[j + 1]) {
                // 则交换
                [nums[j], nums[j+1]] = [nums[j+1], nums[j]];
                // 更新交换的位置
                last = j;
                sorted = false;
            }
        }
        // 在一层循环之后跳跃到最后交换的那个地方，这样的话，在k的位置，后面如果是有序，就可以直接跳过了
        k = last;
        ++i;
    }
}

const list: number[] = [5, 4, 3, 2, 1];
bubbleSort(list);
console.log(list); // [1, 2, 3, 4, 5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

总结

• 时间复杂度：O($n^2$)
  • 两个嵌套循环
• 该算法通过两两比较盯住当前最大的元素，逐渐将其移动到最后，继而一次有序，逐次比较达到整个序列完全有序
• 不变性：经k趟扫描交换后，最大的k个元素必然就位
• 单调性：经k趟扫描交换后，问题规模缩减至n-k
• 正确性：经至多n趟扫描后，算法必然终止，且能给出正确解答
• 它的核心思想是自左至右，逐一检查各对相邻元素，若有逆序，则交换
• 这个算法其实只需要经过n-1趟比较就足够了, 有改进的空间
• 如果某一趟比较后整体已经有序了，就没有必要继续比较到n-1趟了，即提前终止版
• 也许一个算法的思想在一开始是基于很low的策略，比如greedy
• 当基于这个greedy的算法不断做优化, 也能表现的非常好
• 一共有4个版本的写法(上面 1,2是一种，所以是4种)