插入排序 (Insertion Sort)像“打扑克牌时理牌”一样每次从手里还没排好的牌中抽出一张从右往左和已经排好的牌挨个比较找到合适的位置插进去让手里的牌始终保持有序。核心代码#include stdio.h // 插入排序函数 void insertionSort(int arr[], int n) { // 外层循环从第二个元素开始逐个处理未排序部分的元素 for (int i 1; i n; i) { int key arr[i]; // 取出当前需要插入的元素(相当于抽出一张扑克牌) int j i - 1; // j 指向已排序部分的最后一个元素 // 内层循环从后向前扫描已排序部分寻找 key 的正确插入位置 // 如果已排序的元素比 key 大就把它往后挪一位腾出空间 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } // 找到正确位置后将 key 插入(此时 j1 就是空出来的位置) arr[j 1] key; } } // 打印数组的辅助函数 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {64, 34, 25, 12, 22}; int n sizeof(arr) / sizeof(arr[0]); // 计算数组长度 printf(排序前); printArray(arr, n); insertionSort(arr, n); // 调用插入排序 printf(排序后); printArray(arr, n); return 0; }示例演示{64, 34, 25, 12, 22}第 1 轮处理元素 34目标将 34 插入到左侧已排序部分 {64} 的正确位置。抽出 34(key 34)左侧已排序部分为 {64}。比较34 64所以 64 往后挪一位。数组变为[64, 64, 25, 12, 22]左侧已无元素将 34 插入到最前面。第 1 轮结束34 归位。当前数组[34, 64, | 25, 12, 22] (竖线左边为已排好序的部分)第 2 轮处理元素 25目标将 25 插入到左侧已排序部分 {34, 64} 的正确位置。抽出 25(key 25)左侧已排序部分为 {34, 64}。比较25 6464 往后挪。数组变为[34, 64, 64, 12, 22]继续比较25 3434 往后挪。数组变为[34, 34, 64, 12, 22]左侧已无元素将 25 插入到最前面。第 2 轮结束25 归位。当前数组[25, 34, 64, | 12, 22]第 3 轮处理元素 12目标将 12 插入到左侧已排序部分 {25, 34, 64} 的正确位置。抽出 12(key 12)左侧已排序部分为 {25, 34, 64}。比较12 6464 往后挪。数组变为[25, 34, 64, 64, 22]继续比较12 3434 往后挪。数组变为[25, 34, 34, 64, 22]继续比较12 2525 往后挪。数组变为[25, 25, 34, 64, 22]左侧已无元素将 12 插入到最前面。第 3 轮结束12 归位。当前数组[12, 25, 34, 64, | 22]第 4 轮处理元素 22目标将 22 插入到左侧已排序部分 {12, 25, 34, 64} 的正确位置。抽出 22(key 22)左侧已排序部分为 {12, 25, 34, 64}。比较22 6464 往后挪。数组变为[12, 25, 34, 64, 64]继续比较22 3434 往后挪。数组变为[12, 25, 34, 34, 64]继续比较22 25 不成立(22 25)25 往后挪。数组变为[12, 25, 25, 34, 64]继续比较22 12停止挪动。将 22 插入到 12 的后面。第 4 轮结束排序完成。最终结果[12, 22, 25, 34, 64]复杂度时间复杂度是\(O(n^2)\)(最坏和平均情况若数组已有序最好情况可降至\(O(n)\)空间复杂度是\(O(1)\)(只需常数级的额外空间用于保存待插入元素 key)
