插入排序C语言版

 📌 插入排序（Insertion Sort）

🔍 核心思想：
将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加 1 的有序表。

🎮 生活比喻：就像我们整理扑克牌一样，每次把一张新牌插到已排序的手牌中合适的位置。

⏱ 时间复杂度：
情况    时间复杂度
最坏情况    O(n²)
最好情况（已有序）    O(n)
平均情况    O(n²)
🧠 稳定性：✅ 稳定排序
💻 实现代码（C语言）：
 

void InsertionSort(SorList *L) {int i, j;keyType k;for (i = 2; i <= L->length; i++) {L->data[0] = L->data[i]; // 保存当前元素到哨兵位置j = i - 1;while (j >= 1 && L->data[j] > L->data[0]) {L->data[j + 1] = L->data[j];j--;}L->data[j + 1] = L->data[0]; // 插入正确位置}
}