全文共373字，预计耗时112秒。

冒泡排序（Bubble Sort）

是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

简单实现

严格意义上来说，不算标准的冒泡排序算法，因为它不满足：两两比较相邻记录的冒泡排序思想

function bubbleSort(list){
  let i, j, len = list.length;
  for(i = 0; i < len; i++){
    for(j = i + 1; j <= len; j++){
      if(list[i] > list[j]){
        [list[i], list[j]] = [list[j], list[i]];
      }
    }
  }
}

标准实现

function bubbleSort(list){
  let i, j, len = list.length;
  for(i = 0; i < len; i++){
    for(j = len - 1; j >= i; j--){
      if(list[j] > list[j+1]){
        [list[j], list[j+1]] = [list[j+1], list[j]];
      }
    }
  }
}

优化实现

根据有无交换确认是否已经有序，避免不必要的遍历比较。

function bubbleSort(list){
  let i, j, len = list.length;
  let swaped = true;
  for(i = 0; i < len && swaped; i++){
    swaped = false;
    for(j = len - 1; j >= i; j--){
      if(list[j] > list[j+1]){
        [list[j], list[j+1]] = [list[j+1], list[j]];
        swaped = true;
      }
      console.log(list.join(","))
    }
  }
}

更优化实现

针对冒泡端点初始有序情况下，减少不必要的比较次数。

function bubbleSort(list){
  let i, j, len = list.length;
  let swaped = true;
  let sortBorder = 0;
  let lastSwapIndex = len - 1;
  for(i = 0; i < len && swaped; i++){
    swaped = false;
    for(j = len - 1; j >= sortBorder; j--){
      if(list[j] > list[j+1]){
        [list[j], list[j+1]] = [list[j+1], list[j]];
        swaped = true;
        lastSwapIndex = j
        console.log(`${i},${j}:`,list.join(","))
      }
    }
    sortBorder = lastSwapIndex;
  }
}

复杂度

1+2+3+...+(n-1)=n(n-1)/2次，因此时间复杂度为O(n²)