冒泡排序

原理解析

• 选择第1个和第2个数字，如果第1个>第2个，二者交换位置（假设是升序排列）。之后选择第2个和第3个数字，类似交换处理。一轮下来后，最大的数字会“冒泡”到最后一位。
• 接下来，忽略已经排好的数字，对于剩下的数字再来一轮
• ...
• 直到所有的数字都排列完成。

实现方式

function bubleSort(arr) {
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr.length - i; j++) {
      if(arr[j] > arr[j+1]) {
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ]
      }
    }
  }
}
 
let arr = [10, 34, 21, 47, 3, 28]
bubleSort(arr)
console.log(arr)

效率测试

下面我们测试排序性能。以下的代码中，randomArr 函数会生成一个随机数组， 数组长度默认是100， 最大值默认值是1000。 console.time 和 console.end 用来记录排序时间。

let arr = randomArr(10000, 100)
console.time('bubleSort')
bubleSort(arr)
console.timeEnd('bubleSort')
function randomArr( arrLen = 100, maxValue = 1000 ) {
  let arr = []
  for(let i = 0; i < arrLen; i++) {
    arr[i] = Math.floor((maxValue+1)*Math.random())
  }
  return arr
}
function bubleSort(arr) {
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr.length - i; j++) {
      if(arr[j] > arr[j+1]) {
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ] /*交换元素*/
      }
    }
  }
}

经浏览器测试，数组长度增加10倍，排序时间约增加100倍。

复杂度分析

时间复杂度(可以理解为排序的次数)计算： (n-1) + (n-2) + ... + 1 = n*(1 + (n-1))/2，所以时间复杂度为 O(n^2) ，和上面的测试基本一致。