算法可视化？用动画的方式讲解插入排序

太过爱你忘了你带给我的痛 2023-10-13 11:08 11阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th><a href="https://www.coding-time.cn" rel="nofollow">点击在线阅读，体验更好</a></th> 
   <th><a href="https://www.coding-time.cn" rel="nofollow">链接</a></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong><a href="https://www.coding-time.cn" rel="nofollow">现代JavaScript高级小册</a></strong></td> 
   <td><a href="https://www.coding-time.cn" rel="nofollow">链接</a></td> 
  </tr> 
  <tr> 
   <td><strong><a href="https://www.coding-time.cn" rel="nofollow">深入浅出Dart</a></strong></td> 
   <td><a href="https://www.coding-time.cn" rel="nofollow">链接</a></td> 
  </tr> 
  <tr> 
   <td><strong><a href="https://www.coding-time.cn" rel="nofollow">现代TypeScript高级小册</a></strong></td> 
   <td><a href="https://www.coding-time.cn" rel="nofollow">链接</a></td> 
  </tr> 
 </tbody> 
</table>

## 插入排序（Insertion Sort） ##

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，在未排序的部分中从后向前逐步扫描，找到合适位置并插入元素。插入排序通常采用原地排序（只使用O(1)的额外空间），因此在扫描过程中需要反复将已排序元素向后移动，为新元素提供插入空间。

### 基本思想 ###

> 插入排序的基本思想是将数组分为已排序和未排序两部分，初始时已排序部分只包含第一个元素，然后依次将未排序部分的元素插入到已排序部分的正确位置，直到所有元素都有序为止。

### 实现逻辑 ###

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

### 动图演示 ###

![Insertion Sort][]

### 性能分析 ###

*  平均时间复杂度：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;
      }
    }

![v2-91b76e8e4dab9b0cad9a017d7dd431e2\_b.gif][v2-91b76e8e4dab9b0cad9a017d7dd431e2_b.gif]

[来源][Link 1]

> 本来自己想写一个，可是太费时间了，外面找了一圈，发现有了，就拿来演示一下

### 算法优化改进 ###

#### 改进方法① - 二分插入排序 ####

二分插入排序是对直接插入排序的改进，使用二分查找来找到插入位置，从而减少比较的次数。

改进代码：

// 二分插入排序
    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方法）中，插入排序通常被用作快速排序的辅助算法，用于排序小规模的子数组。

--------------------

[Insertion Sort]: https://img-blog.csdnimg.cn/img_convert/36342720f2cbf8757f16abe046b01cd0.gif
[v2-91b76e8e4dab9b0cad9a017d7dd431e2_b.gif]: https://img-blog.csdnimg.cn/img_convert/b4f5b5f756d8348ae33a589302fd2e6b.gif
[Link 1]: https://visualgo.net/zh