JS 中的冒泡排序

记录一下使用 JavaScript 实现的冒泡排序算法，实际操作可查看 https://my-vue.liuxianyu.cn/bubble。

¶一、算法原理

1、比较两个相邻的元素，将值较大的元素交换到后面
2、每一对相邻元素都进行相同操作
3、针对所有的元素重复上述两步，除了最后一个元素
4、持续每次对越来越少的元素重复上述步骤，直到没有任何一对相邻元素需要比较

¶二、算法思路

依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面

第一次比较：首先比较第一个数和第二个数，将较小的数放在前面，较大的数放在后面；
第二次比较：比较第二个数和第三个数，将较小的数放在前面，较大的数放在后面；
…
如此继续，直到比较到最后两个数，将较小的数放在前面，较大的数放在后面；
在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在第二趟比较时，最后一个数不参与比较；
在第二趟比较完成后，倒数第二个数也一定是数组倒数第二大数，所以在第三趟比较时，倒数第二个数不参与比较；
依次类推，每一趟比较次数依次减少

n 个数进行冒泡排序，总共要进行 n - 1 次排序，每趟进行 n - 1 次比较

¶三、算法描述

  // 冒泡排序
  bubbleSort (list) {
    // 需要进行 list.length 次比较
    for (let i = 0; i < list.length - 1; i++) {
      // 第 i 趟比较
      for (let j = 0; j < list.length - i - 1; j++) {
        // 开始进行比较，如果 list[i] > list[i + 1]，则交换位置
        if (list[j] > list[j + 1]) {
          let temp = list[j]
          list[j] = list[j + 1]
          list[j + 1] = temp
        }
      }
    }

    return list
  }
}

¶四、算法比较：

排序算法	平均时间复杂度
冒泡排序	O(n2)
选择排序	O(n2)
插入排序	O(n2)
希尔排序	O(n1.5)
快速排序	O(N*logN)
归并排序	O(N*logN)
堆排序	O(N*logN)
基数排序	O(d(n+r))