插入排序：小数据高效排序利器
一、前言
插入排序通过将当前元素插入到前面已排序序列的正确位置来逐步构建有序数组。插入排序是一种简单直观的排序算法，它的工作原理类似于整理手中的扑克牌——每拿到一张新牌，就把它插入到已排好序的牌堆中的正确位置。
二、详细步骤
设初始数组为[5,3,8,4,2]
将数组分为两个区域：已排序区和待排序区。
初始时，已排序区只有第一个元素。
之后依次将待排序区的每个元素，插入到已排序区的正确位置，直到所有元素都进入已排序区。
初始：[5, 3, 8, 4, 2]
已排序区：[5]
待排序区：[3, 8, 4, 2]第1步：把3插入到[5]中 → [3, 5]
第2步：把8插入到[3,5]中 → [3, 5, 8]
第3步：把4插入到[3,5,8]中 → [3, 4, 5, 8]
第4步：把2插入到[3,4,5,8]中 → [2, 3, 4, 5, 8]完成排序
第一轮：取第2个元素3，与左边的5比较。3 < 5，将5右移一位，3放入位置0。结果：[3, 5, 8, 4, 2]
第二轮：取第3个元素8，与左边的5比较。8 > 5，位置不变。结果：[3, 5, 8, 4, 2]
第三轮：取第4个元素4，与左边的8比较。4 < 8，8右移；继续与5比较，4 < 5，5右移；继续与3比较，4 > 3，停止。将4放入空位。结果：[3, 4, 5, 8, 2]
第四轮：取第5个元素2，依次与8、5、4、3比较并右移，最后插入到开头。结果：[2, 3, 4, 5, 8]
三、C语言代码演示
void InsertSort(int arr[], int len) { for (int i = 1; i < len; i++) // 控制的是趟数 如果有len个值 则有len-1趟 { // 此时i下标指向的是这一趟的待插入值 int temp = arr[i]; int j = i - 1; for ( ; j >= 0; j--) // 控制的是单独一趟中 对于已排序好的序列，从右至左遍历 { if (arr[j] > temp) arr[j + 1] = arr[j]; else //将值挪回去 break; } arr[j + 1] = temp; } }四、复杂度分析
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
五、优缺点分析
1.优点
实现简单，代码量少
数据基本有序时效率极高（接近O(n)）
稳定排序
原地排序，不占额外空间
适合小规模数据（n < 50 左右）
2.缺点
大规模数据性能差：平均和最坏情况都是O(n²)
每次插入可能移动大量元素
其实在日常打牌时你在无意识使用这个算法：每次摸牌后将其插入手中已排序的牌堆。