排序算法-冒泡排序

一、原理解析

选择第1个和第2个数字，如果第1个>第2个二者交换位置（假设是升序排列）。之后选择第2个和第3个数字，类似交换处理。一轮下来后，最大的数字会“冒泡”到最后一位。

接下来，忽略已经拍好的数字，对于剩下的数字再来一轮

...

直到所有的数字都排列完成。

二、范例演示

以下表格里，红色表示选中的待排序的数字，粗体表示本轮刚刚排列过的数字，蓝色表示最终排好的数字。

第一轮：

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

第二轮：

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

...

三、实现方式

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)

复杂度分析

时间复杂度(可以理解为排序的次数)计算： (n-1) + (n-2) + ... + 1 = n*(1 + (n-1))/2，所以时间复杂度为 O(n^2) 。