JS-实现冒泡排序

发表于 | 分类于

对数组进行 冒泡排序，冒泡排序是容易理解的一种排序算法。

实现原理

数组中有 n 个数，比较每相邻两个数，如果前者大于后者，就把两个数交换位置；这样一来，第一轮就可以选出一个最大的数放在最后面；那么经过 n-1（数组的 length - 1） 轮，就完成了所有数的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var arr = [3, 1, 9, 6]
function bubbleSort(arr) {
  var max = arr.length - 1
  for (var i = 0; i < max; i++) {
    // 声明一个变量，作为标志位
    var done = true;
    // 根据外层for循环的i，逐渐减少内层for循环的次数
    for (var j = 0; j < max - i; j++) {
      if (arr[j]>arr[j + 1]) {
        var temp = arr[j + 1]
        arr[j + 1] = arr[j]
        arr[j] = temp
        done = false
      }
    }
    if (done) {
      break
    }
  }
  return arr
}
bubbleSort(arr)

性能

时间复杂度： 平均时间复杂度O(n*n) 、最好情况O(n)、最差情况O(n*n)
空间复杂度： O(1)
稳定性：稳定

时间复杂度指的是一个算法执行所耗费的时间
空间复杂度指运行完一个程序所需内存的大小
稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面
不稳定指，如果a=b，a在b的前面，排序后可能会交换位置

总结

1、外层 for 循环控制循环次数
2、内层 for 循环进行两数交换，找每次的最大数，排到最后
3、设置一个标志位，减少不必要的循环
参考文献