英语流利说：介绍一下冒泡排序原理以及时间复杂度，并手写一个冒泡排序

[sisterAn]

原理：

从左到右，相邻元素进行比较，如果前一个元素值大于后一个元素值（正序），则交换，这样一轮下来，将最大的数在最右边冒泡出来。这样一轮一轮下来，最后实现从小到大排序。

动图演示：

代码实现：

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

// 改进冒泡排序
function bubbleSort1(arr) {
    for (let i = 0; i < arr.length; i++) {
        // 提前退出冒泡循环的标识位
        let flag = false;
        for (let j = 0; j < arr.length - 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
    }
}

// 测试
let arr = [1, 3, 2, 5, 4]
bubbleSort(arr)
console.log(arr) // [1, 2, 3, 4, 5]

let arr1 = [1, 3, 2, 5, 4]
bubbleSort1(arr1)
console.log(arr1) // [1, 2, 3, 4, 5]

复杂度分析：

• 时间复杂度： 最好时间复杂度 O(n)，平均时间复杂度 O(n²)
• 空间复杂度：O(1)

[BinksGao]

执行一次外层循环，将最小数或最大数放到数组最后，然后寻找剩余部分的最小数放在这一部分的最后 时间复杂度为O(n^2) 空间复杂度为O(1)

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let flag = true
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = false

                    [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
            }
        }
        if (flag) break;
    }
    return arr
}

[xyj626553989]

我们要把相邻的元素两两比较，当一个元素大于右侧相邻元 素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。时间复杂度为O(n^2)

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let isSorted = true
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        ;[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
        isSorted = false
      }
    }
    if (isSorted) break
  }
}

[dinjufen]

function bubbleSort(arr) {
  for (let i = 0;i < arr.length;i ++) {
    let min = i;
    for(let j = i;j < arr.length;j ++) {
      if (arr[min] > arr[j])
        min = j;
    }
    let tmp = arr[min];
    arr[min] = arr[i];
    arr[i] = tmp;
  }
  return arr;
}