数据结构基础：直接插入、希尔与选择排序详解
排序算法是数据结构的基石，不仅关乎代码效率，更体现了对数据组织规律的理解。本文将深入探讨三种经典排序算法：直接插入排序、希尔排序和选择排序，通过原理剖析、复杂度分析及 C 语言实现，帮助读者建立扎实的底层认知。
直接插入排序
算法原理
想象一下打扑克牌的过程：摸到第二张牌时，我们会将其插入到手中已排好序的牌堆中合适的位置。直接插入排序正是模拟这一过程，将数组分为有序区和无序区，每次从无序区取出一个元素，插入到有序区的正确位置。
实现步骤
- 默认第一个元素为有序区。
- 从第二个元素开始，依次与前面的有序元素比较。
- 若当前元素小于前一个元素，则后移前一个元素，继续向前比较。
- 找到合适位置后插入，重复直至所有元素有序。
复杂度分析
- 时间复杂度：
- 最好情况（已有序）：O(n)，只需比较一次。
- 最坏情况（逆序）：O(n^2)，每个元素都需要移动。
- 空间复杂度：O(1)，原地排序，仅需常数级辅助变量。
- 稳定性：稳定排序。
代码实现
为了便于理解，我们先实现单次插入逻辑，再扩展至整体排序。
// tmp 是待插入元素，end 是当前比较元素的下标
int tmp = arr[i];
int end = i - 1;
while (end >= 0) {
if (arr[end] > tmp) {
// 元素后移
arr[end + 1] = arr[end];
end--;
} else {
break;
}
}
// 插入
arr[end + 1] = tmp;
完整函数实现如下：
#include <assert.h>
void InsertSort(int* arr, int size) {
assert(arr);
for (int i = 1; i < size; i++) {
int tmp = arr[i];
int end = i - 1;
while (end >= 0) {
if (arr[end] > tmp) {
arr[end + 1] = arr[end];
end--;
} else {
break;
}
}
arr[end + 1] = tmp;
}
}
注意：传参时直接使用数组名即可，无需取地址符 &。建议动手画图模拟执行过程，有助于理解指针移动细节。
优缺点总结
- 优点：稳定，代码简洁，对小规模或基本有序的数据效率较高。
- 缺点：大规模数据下 O(n^2) 的时间开销较大，效率较低。
希尔排序
算法原理
希尔排序（Shell Sort）是对直接插入排序的优化。核心思想是通过设定增量序列，将数组分组进行预排序，使数据在整体上逐步趋向有序，最后再进行直接插入排序。这大大减少了元素的交换次数。
实现步骤
- 选择一个初始间隔
interval（通常为size / 2）。 - 按间隔将数组分成若干子序列，分别进行直接插入排序。
- 缩小间隔（如
interval /= 2），重复上述过程。 - 当间隔为 1 时，进行最后一次直接插入排序，完成整体有序。
复杂度分析
- 时间复杂度：取决于增量序列的选择。最坏情况 O(n^2)，最佳情况接近 O(n log n)。
- 空间复杂度：O(1)。
- 稳定性：不稳定。
代码实现
我们同样采用分步实现的思路，先处理单组，再扩展到多组。
// interval 是间隔
int interval = size / 2;
while (interval >= 1) {
for (int j = 0; j < interval; j++) {
for (int i = j; i < size - interval; i += interval) {
int tmp = arr[i + interval];
int end = i;
while (end >= 0) {
if (arr[end] > tmp) {
arr[end + interval] = arr[end];
end -= interval;
} else {
break;
}
}
arr[end + interval] = tmp;
}
}
interval /= 2;
}
优化说明：
- 动态调整间隔大小，避免固定间隔导致的低效。
- 当间隔为 1 时，直接衔接插入排序逻辑，无需额外调用接口。
优缺点总结
- 优点：相比直接插入排序，显著提升了中等规模数据的排序效率。
- 缺点：时间复杂度仍受增量序列影响，不如归并或快排稳定高效。
选择排序
算法原理
选择排序的基本思想是：每一轮从未排序部分选出最小值，与未排序部分的第一个元素交换位置。每轮确定一个元素的最终位置。
实现步骤
- 遍历无序区间，记录最小值的索引。
- 将最小值与无序区间的起始位置交换。
- 更新无序区间起始位置，重复直至结束。
复杂度分析
- 时间复杂度：无论数据是否有序，均需遍历查找，始终为 O(n^2)。
- 空间复杂度：O(1)，原地排序。
- 稳定性：不稳定，交换操作可能破坏相同元素的相对顺序。
代码实现
void SelectSort(int* arr, int size) {
assert(arr);
for (int i = 0; i < size - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
}
}
优缺点总结
- 优点：实现简单，交换次数少（最多 n-1 次）。
- 缺点：效率低，不稳定，不适合对性能有要求的大规模场景。
以上三种算法构成了排序学习的基础。理解它们的原理与局限，有助于在实际开发中根据数据特征选择合适的策略。后续我们将继续探讨更高效的排序算法。