javascript算法排序之插入排序

​
​

活动地址：CSDN21天学习挑战赛

前言

经典的排序算法，很多人都听过，很多人也许用过，但是也有很多人，听过没见过。为什么呢？现在我们有了越来越多的框架、依赖包，我们将能用到排序的实际场景，作为业务将其封装成了函数，所以，一些人只知函数而不知其运行逻辑。

基于以上，为了让自己更好的理解函数运行逻辑，整理了一些基本排序的方法的运行规则，以及部分个人理解，希望能给大家一些帮助。

本文将讲述插入排序。

插入排序

插入排序（InsertionSort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序可以理解为日常打牌或打麻将，将摸到的无序的牌整理为有序的牌。

插入排序实现原理

1. 默认第一个元素为有序序列，而第二个元素到末尾的元素为无序序列；
2. 以有序序列的下一个元素为目标值，使目标值和有序序列进行遍历比较；
3. 目标值和有序序列元素进行比较；
4. 当目标值大于有序序列元素，则和下一个元素比较；
5. 当目标值小于等于有序序列元素，则将目标值插入至此此位置；
6. 重复步骤2-5；

代码

function insertionSort(array) {
  let length = array.length;
  let preIndex, current;
  // 从第二个数开始循环
  for (let i = 1; i < length; i++) {
    // 当前数的前一个index开始对比
    preIndex = i - 1;
    // 当前需要插入的数据，用current空间参数存起来
    current = array[i];
    // 进入二次循环，该循环用来对比排序完成的数与当前需要插入的数据
    while (preIndex >= 0 && current < array[preIndex]) {
      // 因为当前值已经被抽出，它的序号比需要对比的数的最大序列大1，所以当满足条件，可以把preIndex + 1的序列的值赋值为 // preIndex
      array[preIndex + 1] = array[preIndex];
      // 继续循环
      preIndex--;
    }
    array[preIndex + 1] = current; // 外层完成一次循环后，把找到的当前小于current 的前一位数替换成插入元素
  }
  console.log('insertionSort result:', array);
}

insertionSort([9, 1, 0, 2, 3, 8, 6, 3]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

输出值

双for循环写法

function insertionSort2(array) {
  let length = array.length;
  let preIndex, current;
  // 从第二个数开始循环
  for (let i = 1; i < length; i++) {
    // 当前数的前一个index开始对比
    preIndex = i;
    // 当前需要插入的数据，用current空间参数存起来
    current = array[i];
    let twoCurrent;
    // 进入二次循环，该循环用来对比排序完成的数与当前需要插入的数据
    for (let j = i - 1; j >= 0; j--) {
      if (array[j] > current) {
        let temp = array[preIndex];
        array[preIndex] = array[j];
        array[j] = temp;
        preIndex = j;
      } else {
        break;
      }
    }
  }
  console.log('insertionSort2 result:', array);
}

insertionSort2([9, 1, 0, 2, 3, 8, 6, 3]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

输出值

无论是while写法还是双for循环写法，都可以实现最终的结果；但是双for循环写法相比之下，更容易让人理解；当然，在写复杂逻辑代码的同时，记得增加必要的注释，否则将会让阅读的人十分苦恼；

复杂度

时间复杂度：O(n^2)
空间复杂度：O(1)

寄语

插入排序的应用场景很多，变种包括二分法排序，基础牢固才能更好的进行优化，加油吧，各位！

思考是进步的阶梯