关于前端:算法可视化用动画的方式讲解插入排序

插入排序（Insertion Sort）

插入排序（Insertion Sort）是一种简略直观的排序算法。它的工作原理是通过构建有序序列，在未排序的局部中从后向前逐渐扫描，找到适合地位并插入元素。插入排序通常采纳原地排序（只应用O(1)的额定空间），因而在扫描过程中须要重复将已排序元素向后挪动，为新元素提供插入空间。

根本思维

插入排序的根本思维是将数组分为已排序和未排序两局部，初始时已排序局部只蕴含第一个元素，而后顺次将未排序局部的元素插入到已排序局部的正确地位，直到所有元素都有序为止。

实现逻辑

1. 从第一个元素开始，将其视为已排序局部。
2. 取出下一个元素，从后向前扫描已排序局部，找到插入地位。
3. 如果以后元素大于被比拟元素，则将被比拟元素向后挪动一位。
4. 反复步骤3，直到找到插入地位。
5. 将以后元素插入到插入地位后。
6. 反复步骤2~5，直到所有元素都插入到已排序局部。

动图演示

性能剖析

• 均匀工夫复杂度：O(n^2)
• 最坏工夫复杂度：O(n^2)
• 空间复杂度：O(1)
• 排序形式：In-place
• 稳定性：稳固排序算法

代码实现

// 插入排序
function insertionSort(arr) {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    let current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
}

起源

原本本人想写一个，可是太费时间了，里面找了一圈，发现有了，就拿来演示一下

算法优化改良

改良办法① – 二分插入排序

二分插入排序是对间接插入排序的改良，应用二分查找来找到插入地位，从而缩小比拟的次数。

改良代码：

// 二分插入排序
function binaryInsertionSort(arr) {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    let current = arr[i];
    let left = 0;
    let right = i - 1;
    while (left <= right) {
      let middle = Math.floor((left + right) / 2);
      if (arr[middle] > current) {
        right = middle - 1;
      } else {
        left = middle + 1;
      }
    }
    for (let j = i - 1; j >= left; j--) {
      arr[j + 1] = arr[j];
    }
    arr[left] = current;
  }
}

改良办法② – 希尔排序

希尔排序是对插入排序的进一步改良，通过将数组分成多个子序列进行插入排序，逐步放大子序列的距离，最终实现全局的排序。

三、总结

插入排序实用于小规模数据的排序。在数据量较小的状况下，插入排序具备较高的效率。特地是对简直有序的数据进行排序时，插入排序的性能优于其余排序算法。在规范库中的排序算法（如STL的sort函数和JavaScript的Array.prototype.sort办法）中，插入排序通常被用作疾速排序的辅助算法，用于排序小规模的子数组。