菜鸟学算法-2-冒泡排序

我想知道这是为什么 –费曼

冒泡排序我想是大部分人接触的第一个排序算法，原理也很形象，
每一次轮询都会将这一轮里能找到的最大（小）的数字通过一个个相邻比较和交换位置，最后归到数组的后面

先来看一次轮询的操作，把最大值放到最后

1
2
3
4
5
6


let array = [5, 4, 3, 2, 1]
for (let i = 0; i < array.length - 1; i++) {
  if (array[i] > array[i + 1]) {
    ;[array[i + 1], array[i]] = [array[i], array[i + 1]] //swap
  }
}

array 有 n 个元素，就要做 n 次轮询的操作

1
2
3
4
5
6
7
8


let array = [5, 4, 3, 2, 1]
for (let j = 0; j < array.length; j++) {
  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] > array[i + 1]) {
      ;[array[i + 1], array[i]] = [array[i], array[i + 1]] //swap
    }
  }
}

这里还能优化一下，我们可以发现：

第一次 j==0 时
i==3 时就把最大值交换到最后了

第二次 j==1 时
i==2 时就把最大值交换到最后了

第三次 j==2 时
i==1 时就把最大值交换到最后了

第四次 j==3 时
i==0 时就把最大值交换到最后了

也就是每次开始新的轮询时，length 都比上一次少 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


let array = [5, 4, 3, 2, 1]

function bubbleSort(array) {
  for (let j = 0; j < array.length; j++) {
    for (let i = 0; i < array.length - 1 - j; i++) {
      if (array[i] > array[i + 1]) {
        ;[array[i + 1], array[i]] = [array[i], array[i + 1]] //swap
      }
    }
  }
  return array
}

console.log(bubbleSort(array))

总结：
冒泡排序不需要额外空间，是本地排序，相等元素是不会交换前后顺序，因而也是稳定排序，时间复杂度为 O(n^2)，适用于少量数据排序，但实际中用得不多

非常感谢老姚的文章：
手写算法并记住它：冒泡排序

菜鸟学算法-2-冒泡排序

相关内容