10大经典算法之 - 2冒泡排序

算法思想

• 基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
• 直观表达，每一趟遍历，将一个最大的数移到序列末尾。

算法描述

• 比较相邻的元素，如果前一个比后一个大，交换之。
• 第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
• 接下来第二趟，忽略已经拍好的数字，对于剩下的数字再来一轮
  ......
  动画实现

image

第一轮：

1. 选择 10 和 34， 进行比较， 其中 10 < 34， 二者不需要交换
2. 选择 34 和 21， 进行比较， 其中 34 > 21, 二者需要交换
3. 选择 34 和 47， 进行比较， 其中 34 < 47, 二者需不要交换
4. 选择 47 和 3， 进行比较， 其中 47 > 3, 二者需要交换
5. ...
6. 最后 47 交换到末尾

第二轮：

忽略已经排列好的47, 按照刚刚的逻辑再次排序

...

[图片上传失败...(image-e38d47-1609230829454)]

复杂度

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] ] /*交换元素*/
      }
    }
  }
}

1w长度数组发现平均时间: image.png

以下是10-10万数组长度排序所花时间

image.png

发时间复杂度: [图片上传失败...(image-c3282c-1609230829454)]

空间复杂度: [图片上传失败...(image-39bce5-1609230829454)]

稳定性：稳定

代码实现（JavaScript）

image.png

function bubleSort(arr) {
  for(let i = 0; i < arr.length /*i代表轮数*/; i++) {
    for(let j = 0; j < arr.length - i /*j代表当前轮选中的元素下标*/; j++) {
      if(arr[j] > arr[j+1]) {
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ] /*交换元素*/
      }
      //console.log(arr)
    }
  }
}

var arr = [10, 34, 21, 47, 3, 28]
bubleSort(arr)
console.log(arr)