一、前言插入排序通过将当前元素插入到前面已排序序列的正确位置来逐步构建有序数组。插入排序是一种简单直观的排序算法它的工作原理类似于整理手中的扑克牌——每拿到一张新牌就把它插入到已排好序的牌堆中的正确位置。二、详细步骤设初始数组为[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 88右移继续与5比较4 55右移继续与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²)每次插入可能移动大量元素其实在日常打牌时你在无意识使用这个算法每次摸牌后将其插入手中已排序的牌堆。