算法之冒泡排序 - 翁先森的博客

[冒泡排序动画](Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo)

手写冒泡排序#

毋庸置疑，就是把每一项和下一项做对比，从小到大排序，那么最大的肯定放最后面，需要经过两轮循环

从区间0<= i <=arr.length-1的范围中去每一次生成区间 [0, j]
每一次从区间[0, j]中找到这个区间最大的，因此根据“每一项和下一项做对比”来做比对

其中j的范围为0<=j<arr.length-1-i，算上上一层已经排序后的，就不需要比对

1
function bubbleSort(arr) {
2
  for (let i = 0; i < arr.length; i++) {
3
    for (let j = 0; j < arr.length - i - 1; j++) {
4
      const current = arr[j];
5
      const next = arr[j + 1];
6
      if (current > next) {
7
        arr[j] = next;
8
        arr[j + 1] = current;
9
      }
10
    }
11
  }
12
  return arr
13
}

优化#

其实步骤1中，每次都去生成一个区间，如果这个区间[0,j]都是排过序的，那么说明，可以退出了

因此加一个flag用来表示不需要排序

1
function bubbleSort(arr) {
2
  for (let i = 0; i < arr.length; i++) {
3
    let flag = true;
4
    for (let j = 0; j < arr.length - i - 1; j++) {
5
      const current = arr[j];
6
      const next = arr[j + 1];
7
      if (current > next) {
8
        flag = false;
9
        arr[j] = next;
10
        arr[j + 1] = current;
11
      }
12
    }
13
    if (flag) {
14
      break;
15
    }
16
  }
17
  return arr;
18
}