数据结构基础：直接插入、希尔与选择排序详解

完整函数实现如下：

#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）是对直接插入排序的优化。核心思想是通过设定增量序列，将数组分组进行预排序，使数据在整体上逐步趋向有序，最后再进行直接插入排序。这大大减少了元素的交换次数。

实现步骤

1. 选择一个初始间隔 interval（通常为 size / 2）。
2. 按间隔将数组分成若干子序列，分别进行直接插入排序。
3. 缩小间隔（如 interval /= 2），重复上述过程。
4. 当间隔为 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 时，直接衔接插入排序逻辑，无需额外调用接口。

优缺点总结

• 优点：相比直接插入排序，显著提升了中等规模数据的排序效率。
• 缺点：时间复杂度仍受增量序列影响，不如归并或快排稳定高效。

选择排序

算法原理

选择排序的基本思想是：每一轮从未排序部分选出最小值，与未排序部分的第一个元素交换位置。每轮确定一个元素的最终位置。

实现步骤

1. 遍历无序区间，记录最小值的索引。
2. 将最小值与无序区间的起始位置交换。
3. 更新无序区间起始位置，重复直至结束。

复杂度分析

• 时间复杂度：无论数据是否有序，均需遍历查找，始终为 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 次）。
• 缺点：效率低，不稳定，不适合对性能有要求的大规模场景。

以上三种算法构成了排序学习的基础。理解它们的原理与局限，有助于在实际开发中根据数据特征选择合适的策略。后续我们将继续探讨更高效的排序算法。