C 语言排序算法详解:插入排序与希尔排序
在基础数据结构的学习中,排序算法是绕不开的核心内容。除了冒泡排序,插入排序和它的优化版本——希尔排序,在实际开发中同样有着广泛的应用场景。本文将深入剖析这两种算法的原理、实现细节及代码逻辑。
插入排序
算法思想
插入排序的逻辑非常直观,就像我们在打扑克牌时整理手牌一样。假设手中已经有一组有序的牌,当拿到新的一张牌时,我们会从后往前依次比较,找到合适的位置插入进去。
具体到数组操作中,每次取出一个元素 tmp,将其与前面已排序序列的元素逐一比较。若 tmp 小于前一个元素,则前一个元素向后移动一位;若 tmp 大于或等于前一个元素,则停止比较,将 tmp 插入到该位置之后。
实现思路
- 确定范围:假设下标
0到end之间的区间已经是有序的,tmp为待插入元素(即end + 1位置的元素)。 - 向前比较:将
end位置的元素与tmp比较。如果tmp更小,则将a[end]移动到a[end + 1],并将end减一继续向前查找。 - 循环结束:当
end越界或找到合适位置时,将tmp放入a[end + 1]。 - 整体遍历:重复上述过程,直到整个数组完成排序。
代码实现
// 插入排序
void InsertSort(int* a, int n) {
for (int i = 0; i < n - 1; i++) {
int end = i;
int tmp = a[end + 1];
while (end >= 0) {
if (tmp < a[end]) {
a[end + 1] = a[end];
end--;
} else {
break;
}
}
a[end + 1] = tmp;
}
}
注意这里 end 的初始值设为 i,意味着我们总是尝试将 i+1 位置的元素插入到 0 到 i 的有序区间中。当 end 变为 -1 时,说明 比所有前面的元素都小,需要插入到数组头部。


