冒泡排序

[Geekhyt]

冒泡排序可视化视频

冒泡排序，简单粗暴，一句话解释:

冒泡排序在每次冒泡操作时会比较相邻的两个元素，看是否满足大小关系要求，不满足就将它俩互换。一直迭代到不再需要交换，也就是排序完成。

const bubbleSort = function(arr) {
  const len = arr.length
  if (len < 2) return arr
  for (let i = 0; i < len; i++) {
      for (let j = 0; j < len - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
              const temp = arr[j]
              arr[j] = arr[j + 1]
              arr[j + 1] = temp
          }
      }
  }
  return arr
}

• 时间复杂度: O(n^2)
• 空间复杂度: O(1)
• 稳定

注意：这里的稳定是指，冒泡排序是稳定的排序算法。

什么是稳定的排序算法呢？

排序算法的稳定性

仅仅用执行效率和内存消耗来判断排序算法的优劣是不够的，针对排序算法，还有一个重要的度量指标，稳定性。

意思是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

举个🌰：

比如我们有一组数据：1，9，2，5，8，9。按照大小排序之后就是 1，2，5，8，9，9。

这组数据中有两个 9，经过某种排序算法排序后，如果两个 9 的前后顺序没有改变，我们就把这种排序算法称为 稳定的排序算法。
否则，就是不稳定的排序算法。

冒泡排序优化

上面的代码还可以进行优化，当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不需要再继续执行后续的冒泡操作了。

const bubbleSort = function(arr) {
  const len = arr.length
  let flag = false
  if (len < 2) return arr
  for (let i = 0; i < len; i++) {
      flag = false // 提前退出冒泡循环的标志
      for (let j = 0; j < len - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
              const temp = arr[j]
              arr[j] = arr[j + 1]
              arr[j + 1] = temp
              flag = true // 表示有数据交换
          }
      }
      if (!flag) break // 没有数据交换，提前退出
  }
  return arr
}