JS手撕(十)    冒泡排序、插入排序

冒泡排序

原理

冒泡排序原理就是依次比较相邻元素，如果前面的比后面的大，那就互换位置。从第一对比到最后一对。第一轮比较完最大的数就会浮到最右边，第二轮，第二个大叔浮到倒数第二个位置……

依次针对所有元素执行以上步骤，最后一个不需要，因为已经排好顺序了。

下面的动图来自于菜鸟教程(贴出来主要是为了能更好的理解)

JS实现

实现：

function bubbleSort(arr) {
  const len = arr.length;

  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 如果前面的数比后面的大，那就要互换位置
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

简单讲一下边界的依据：

• i < len - 1：这是因为第一轮排序是轮数，上面也说过需要针对所有元素执行比较相邻元素的步骤，除了最后一个元素。因为已经排完顺序了。所以轮数应该是数组长度-1

• j < len - 1 - i：这里的len - 1和上面的len - 1是不同原因。len - 1是因为我们比较的时候是比较arr[j]和arr[j + 1]，如果是len，最后数组会越界。至于后面的- i就是因为每一轮都会排好一个值，所以就不需要比较已经排好了的。

测试：

小优化

当其中的一趟排序，没有互换过位置的时候，其实就是已经排好序了，但是按上面的程序跑的话，一定要够n-1趟排序。所以可以定义一个flag变量，当排序过程中发现已经排序好了(一趟排序中没有互换过位置)，直接退出循环。

function bubbleSort(arr) {
  const len = arr.length;
  let flag;

  for (let i = 0; i < len - 1; i++) {
    flag = true;

    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 如果前面的数比后面的大，那就要互换位置
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];

        flag = false;
      }
    }

    if (flag) {
      break;
    }
  }

  return arr;
}

性能

时间复杂度：O(n²)        

排序稳定性：稳定

注：排序稳定性指的是大小相同的两个值在排序前和排序后的先后顺序是否不变。如果是不变的，那就是稳定的，否则是不稳定的。

插入排序

原理

插入排序原理就是每一步将一个待插入元素插入到前面的有序序列的适当位置。(如果待插入元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面，这是为了让插入排序是稳定的)

JS实现

function insertSort(arr) {
  const len = arr.length;
  let temp;

  for (let i = 1; i < len; i++) {
    // 从i = 1开始，是因为第一个元素默认是有序的(因为只有一个元素)

    // temp是待插入元素
    temp = arr[i];

    for (let j = i; j >= 0; j--) {
      if (temp < arr[j - 1]) {
        // 从后向前顺序比较，并依次后移
        arr[j] = arr[j - 1];
      } else {
        // 待插入元素大于等于有序序列元素的时候，插入元素后退出循环
        arr[j] = temp;
        break;
      }
    }
  }

  return arr;
}

测试：

const insertionSort = require('./sort.js');

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 26, 4, 19, 50, 48];
console.log(insertSort(arr))

性能

时间复杂度：O(n²)        

排序稳定性：稳定

参考链接

• 1.0 十大经典排序算法 | 菜鸟教程