我1.3 插入排序
插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理类似于整理扑克牌。
插入排序通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
1. 算法步骤
初始化：将列表分为已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，未排序部分包含剩余元素。
选择元素：从未排序部分中取出第一个元素。
插入到已排序部分：将该元素与已排序部分的元素从后向前依次比较，找到合适的位置插入。
重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。
2. 动图演示
假设有一个待排序的列表 [5, 2, 4, 6, 1, 3]，插入排序的过程如下：
初始状态：
已排序部分：[5]。
未排序部分：[2, 4, 6, 1, 3]。
第一轮：
取出未排序部分的第一个元素 2。
将 2 与已排序部分的 5 比较，2 < 5，插入到 5 前面。
列表变为 [2, 5, 4, 6, 1, 3]。
已排序部分：[2, 5]，未排序部分：[4, 6, 1, 3]。
第二轮：
取出未排序部分的第一个元素 4。
将 4 与已排序部分的 5 比较，4 < 5，继续与 2 比较，4 > 2，插入到 2 和 5 之间。
列表变为 [2, 4, 5, 6, 1, 3]。
已排序部分：[2, 4, 5]，未排序部分：[6, 1, 3]。
第三轮：
取出未排序部分的第一个元素 6。
将 6 与已排序部分的 5 比较，6 > 5，直接插入到末尾。
列表变为 [2, 4, 5, 6, 1, 3]。
已排序部分：[2, 4, 5, 6]，未排序部分：[1, 3]。
第四轮：
取出未排序部分的第一个元素 1。
将 1 与已排序部分的 6 比较，1 < 6，继续与 5、4、2 比较，1 是最小的，插入到最前面。
列表变为 [1, 2, 4, 5, 6, 3]。
已排序部分：[1, 2, 4, 5, 6]，未排序部分：[3]。
第五轮：
取出未排序部分的第一个元素 3。
将 3 与已排序部分的 6 比较，3 < 6，继续与 5、4、2 比较，3 > 2，插入到 2 和 4 之间。
列表变为 [1, 2, 3, 4, 5, 6]。
已排序部分：[1, 2, 3, 4, 5, 6]，未排序部分为空。
实例
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i] # 取出未排序部分的第一个元素
j = i - 1
# 将 key 插入到已排序部分的正确位置
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j] # 向后移动元素
j -= 1
arr[j + 1] = key # 插入 key
return arr
# 示例
arr = [5, 2, 4, 6, 1, 3]
sorted_arr = insertion_sort(arr)
print(sorted_arr) # 输出: [1, 2, 3, 4, 5, 6]
时间复杂度
最坏情况：O(n²)，当列表是逆序时，每次插入都需要移动所有已排序元素。
最好情况：O(n)，当列表已经有序时，只需遍历一次列表。
平均情况：O(n²)。
空间复杂度
O(1)，插入排序是原地排序算法，不需要额外的存储空间。
优缺点
优点：
实现简单，代码易于理解。
对小规模数据或基本有序的数据效率较高。
原地排序，不需要额外的存储空间。
稳定排序算法（相同元素的相对顺序不会改变）。
缺点：
时间复杂度较高，不适合大规模数据集。
适用场景
数据量较小或基本有序的场景。
需要稳定排序算法的场景。
作为更复杂排序算法（如快速排序、归并排序）的辅助算法。
代码实现
JavaScript
实例
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
Python
实例
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
Go
实例
func insertionSort(arr []int) []int {
for i := range arr {
preIndex := i - 1
current := arr[i]
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex -= 1
}
arr[preIndex+1] = current
}
return arr
}
Java
实例
public class InsertSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for (int i = 1; i < arr.length; i++) {
// 记录要插入的数据
int tmp = arr[i];
// 从已经排序的序列最右边的开始比较，找到比其小的数
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// 存在比其小的数，插入
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
}
PHP
实例
function insertionSort($arr)
{
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
$preIndex = $i - 1;
$current = $arr[$i];
while($preIndex >= 0 && $arr[$preIndex] > $current) {
$arr[$preIndex+1] = $arr[$preIndex];
$preIndex--;
}
$arr[$preIndex+1] = $current;
}
return $arr;
}
C
实例
void insertion_sort(int arr[], int len){
int i,j,key;
for (i=1;i key = arr[i]; j=i-1; while((j>=0) && (arr[j]>key)) { arr[j+1] = arr[j]; j--; } arr[j+1] = key; } } C++ 实例 void insertion_sort(int arr[],int len){ for(int i=1;i int key=arr[i]; int j=i-1; while((j>=0) && (key arr[j+1]=arr[j]; j--; } arr[j+1]=key; } } C# 实例 public static void InsertSort(int[] array) { for(int i = 1;i < array.length;i++) { int temp = array[i]; for(int j = i - 1;j >= 0;j--) { if(array[j] > temp) { array[j + 1] = array[j]; array[j] = temp; } else break; } } } Swift 实例 for i in 1.. let temp = arr[i] for j in (0.. if arr[j] > temp { arr.swapAt(j, j+1) } } } 原文地址：https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/3.insertionSort.md 参考地址：https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
