算法-冒泡排序及优化

冒泡算法的原理：

升序冒泡：
两次循环，相邻元素两两比较，如果前面的大于后面的就交换位置

降序冒泡：
两次循环，相邻元素两两比较，如果前面的小于后面的就交换位置

js实现：

// 升序冒泡
function maopao(arr){
  const array = [...arr]
  for(let i = array.length; i > 0; i--){
    for(let j =0; j < i - 1; j++) {
      if (array[j] > array[j + 1]) {
        let temp = array[j]
        array[j] = array[j + 1]
        array[j + 1] = temp
      }
    }
  }
  return array
}

1.png

看起来没问题，不过一般生产环境都不用这个，原因是效率低下，冒泡排序在平均和最坏情况下的时间复杂度都是 O(n^2)，最好情况下都是 O(n)，空间复杂度是 O(1)。因为就算你给一个已经排好序的数组，如[1,2,3,4,5,6] 它也会走一遍流程，白白浪费资源。所以有没有什么好的解决方法呢？

答案是肯定有的：

加个标识，如果已经排好序了就直接跳出循环。

优化版：

function maopao1(arr){
  const array = [...arr]
  for(let i = array.length; i > 0; i--){
    let isOk = true
    for(let j =0; j < i - 1; j++) {
      if (array[j] > array[j + 1]) {
        let temp = array[j]
        array[j] = array[j + 1]
        array[j + 1] = temp
        isOk = false
      }
    }
    if (isOk) {
      break
    }
  }
  return array
}

测试：
数组：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

2.png

从测试结果来看：
普通冒泡排序时间：0.024ms
优化后冒泡排序时间：0.002ms