冒泡排序.md

冒泡排序

算法思想

从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。

算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大（小）的数据元素放到队尾。

代码实现

function bubbleSort(arr) {
  if (!arr || arr.length <= 2) {
    return;
  }

  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
    console.log(`第${i}趟排序后的顺序: ${arr}`); // 打印一下就知道了
  }
  return arr;
}

let sortArr = [3, 6, 4, 2, 11, 10, 5];

console.log(bubbleSort(sortArr)); // [ 2, 3, 4, 5, 6, 10, 11 ]

改良？

上面的 console.log(�) 打印出来，你会看到 👉

第0趟排序后的顺序: 3,4,2,6,10,5,11
第1趟排序后的顺序: 3,2,4,6,5,10,11
第2趟排序后的顺序: 2,3,4,5,6,10,11
第3趟排序后的顺序: 2,3,4,5,6,10,11
第4趟排序后的顺序: 2,3,4,5,6,10,11
第5趟排序后的顺序: 2,3,4,5,6,10,11

能不能让它比较的次数少点呢？可以，加入一个 flag 变量，我们明显可以看到，上边的第 2、3、4 趟都是一样的，说明做了无用功的比较，这时候通过 flag 来记录冒泡排序是否发生数据元素位置交换。如果没有发生交换，说明序列已经有序了，不必继续进行下去了

function bubbleSort(arr) {
  if (!arr || arr.length <= 2) {
    return;
  }

  let flag = 1; // 有序 = 0 ，无序 = 1

  for (let i = 0; i < arr.length - 1 && flag != 0; i++) {
    flag = 0;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
        flag = 1;
      }
    }
    console.log(`第${i}趟排序后的顺序: ${arr}`);
  }
  return arr;
}

let sortArr = [3, 6, 4, 2, 11, 10, 5];

console.log(bubbleSort(sortArr)); // [ 2, 3, 4, 5, 6, 10, 11 ]

上面的 console.log() 打印出来，你会看到 👉

第0趟排序后的顺序: 3,4,2,6,10,5,11
第1趟排序后的顺序: 3,2,4,6,5,10,11
第2趟排序后的顺序: 2,3,4,5,6,10,11
第3趟排序后的顺序: 2,3,4,5,6,10,11

是不是少比较了两趟，开心 😁

时间复杂度和空间复杂度

冒泡排序在平均和最坏情况下的时间复杂度都是 O(n^2)，最好情况下都是 O(n)，空间复杂度是 O(1)。

• 最坏的情况就是第一种，时间复杂度就是 O(n^2)

• 最好的情况就是第二种，加了一个 flag 标志，时间复杂度 O(n)

对于 n 个元素，相邻元素均要比较，共有(n-1)次。经过第一回合冒泡过程后，最大元素沉淀到最右位置。第二回合， 只剩下(n-1)个元素，只需要比较(n-2)次。依次类推，其他比较次数为(n-3),......,2, 1， 所以总共比较次数为 n(n-1)/2，而且是固定为这个数目(不管序列是否怎样，都是要比较这么多次).

改进后的冒泡排序(也就是加 flag)版本，如果数组是有序的，只需要比较一次即可