实现原理

冒泡排序.png

1、两两比较,把大的往后移

 for (let i = 0; i < arr.length - 1; i++) {
  if (arr[i] > arr[i + 1]) {
    array_swap(arr, i, i + 1) // 交换数组的两个值
  }
}

2、然后循环length次

  for (let k = 0; k < arr.length; k++) {
    for (let i = 0; i < arr.length - 1; i++) {

      if (arr[i] > arr[i + 1]) {
        array_swap(arr, i, i + 1)
      }
     
    }
  }

3、优化代码,但是最好的时间复杂度还是 O(n²),没有达到效果 O(n)

  for (let k = arr.length - 1; k > 0; k--) {
    for (let i = 0; i < k; i++) { // 内部循环时,已经比较过的就不要在比较了
      if (arr[i] > arr[i + 1]) {
        array_swap(arr, i, i + 1)
      }
    }
  }

4、最终优化,加入一个flag标识,用于表示内循环是否有出现交换,如果没有,则代表不需要交换了,已经是最好的方式了
for(let k=

详情

1、能看出它的平均时间复杂度和前面的 选择排序 是一样的 等差数列,O(n²),
2、由于没有用到多余空间,因此空间复杂度为 O(1)
3、由于是两两比较,因此是稳定的,不会导致,明明是后面的8,却排到前面的8去了。

标签: none

添加新评论