Skip to content

冒泡排序

· 3 min

基本概念#

冒泡排序，英语叫做 Bubble Sort，这是所有排序方法中最为简单的排序方法，该排序算法的核心思想如下：

  1. 遍历整个元素序列，每次取出两个 相邻 的元素进行比较
  2. 如果顺序不对（看你具体的排序规则：如从大到小、首字母从 Z 到 A），就进行交换
  3. 一次遍历完成，称之为完成了一次冒泡。每一轮冒泡会确定一个数的正确位置
    • 例如从小到大排序（升序），那么第一轮冒泡就会确定最大的数、第二轮冒泡就会确定倒数第二大的数，依此类推…

Bubble_Sort

代码实现#

function bubbleSort(arr) {
  let n = arr.length
  let swapped = false // 记录是否发生了交换


  // 外层 for 循环控制的是冒泡的次数
  for (let i = 0; i < n - 1; i++) {
    // 内层循环控制的是比较的次数
    // 因为比较是从第一个数字开始
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 进行交换
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
        // 发生了交换，置 swapped 为 true
        swapped = true
      }
    }
    // 出了内层for循环后，判断是否发生了交换
    // 我们就需要判断是否进入过 if，如果没有进入过，说明数组已经有序
    if (!swapped) {
      break
    }
  }
}


let arr = [5, 3, 8, 4, 2]
bubbleSort(arr)
console.log(arr)

复杂度#

稳定性#

所谓稳定性，指的是 相同的元素 在排序后的相对顺序是否保持不变。如果保持不变，那就是稳定的，否则就是不稳定。

举例：

（value、id）

;[(5, 1), (3, 2), (5, 3), (2, 4)]

如果使用稳定排序

;[(2, 4), (3, 2), (5, 1), (5, 3)]

如果使用不稳定排序

;[(2, 4), (3, 2), (5, 3), (5, 1)]

冒泡排序的核心原理是相邻的两个数进行比较，假设我们是升序排序，那么只有右边的数小于左边的时候，才会交换。相等的情况下是不会做操作的。因此冒泡排序是一种 稳定 的排序方式。

-EOF-