冒泡算法

“冒泡”的由来

按照气泡在水中上浮的顺序进行模拟的一种算法，一般较大的气泡上浮越快，较小的气泡则在其后。

核心思路：在数组遍历时，当遇到较大的数值时，将较大的数往后交换，直至本轮比较结束。然后进行下一趟比较。

时间复杂度 O(n^2)

遍历一趟需要的时间复杂度为 O(n),一共需要进行 n-1.因此，总的时间复杂度为 O(n^2).

源码实现:

let arr = [20, 40, 30, 10, 60, 50]
let count = 0
for (let i = 0; i < arr.length; i++) {
  // 此时注意: 优化方案 let j = i
  for (let j = i; j < arr.length; j++) {
  	// 交换操作
    if (arr[i] > arr[j]) {
      arr[i] += arr[j]
      arr[j] = arr[i] - arr[j]
      arr[i] = arr[i] - arr[j]
    }
    count++
  }
}

console.log('arr', arr) // arr (6) [10, 20, 30, 40, 50, 60]
console.log('count', count) // count 21 => 前n项求和公式:Sn=n(n+1)/2