带你读《图解算法小抄》十四、排序（4）https://developer.aliyun.com/article/1348146?groupCode=tech_library
3.插入排序
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，在未排序的部分中从后向前逐步扫描，找到合适位置并插入元素。插入排序通常采用原地排序（只使用O(1)的额外空间），因此在扫描过程中需要反复将已排序元素向后移动，为新元素提供插入空间。
1）基本思想
插入排序的基本思想是将数组分为已排序和未排序两部分，初始时已排序部分只包含第一个元素，然后依次将未排序部分的元素插入到已排序部分的正确位置，直到所有元素都有序为止。
2）实现逻辑
- 从第一个元素开始，将其视为已排序部分。
- 取出下一个元素，从后向前扫描已排序部分，找到插入位置。
- 如果当前元素大于被比较元素，则将被比较元素向后移动一位。
- 重复步骤3，直到找到插入位置。
- 将当前元素插入到插入位置后。
- 重复步骤2~5，直到所有元素都插入到已排序部分。
- 动图演示
访问 www.coding-time.cn 阅读原文动画效果。
Insertion Sort
4）性能分析
- 平均时间复杂度：O(n^2)
- 最坏时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 排序方式：In-place
- 稳定性：稳定排序算法
5）代码实现
// 插入排序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; }}
insertion_sort
来源
本来自己想写一个，可是太费时间了，外面找了一圈，发现有了，就拿来演示一下
带你读《图解算法小抄》十四、排序（6）https://developer.aliyun.com/article/1348144?groupCode=tech_library
