数据结构初阶：常见排序算法详解 (C/C++)

理论部分

以下代码实现均按升序排列。建议先编写单趟逻辑，再构建整体算法。多数排序在元素相等时不进行交换操作。

1. 直接插入排序

核心思想：将当前元素与前面已排序的每个数比较，找到合适位置插入。 时间复杂度：O(n^2)，最好情况 O(n)。 适用场景：小段有序数据。

void InsertSort(int* a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int end = i;
        int tmp = a[i + 1];
        while (end >= 0) {
            if (tmp < a[end]) {
                a[end + 1] = a[end];
                --end;
            } else {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

2. 希尔排序

核心思想：对插入排序的优化。先预排序（以 gap 为间隔分组），再进行直接插入排序。 gap 计算方式有多种，如 gap /= 2 或 gap = gap / 3 + 1。 时间复杂度：约 O(n^1.3)。

void ShellSort(int* a, int n) {
    int gap = n;
    while (gap > 1) {
        gap /= 2;
        for (int i = 0; i < n - gap; i++) {
            int end = i;
            int tmp = a[i + gap];
            while (end >= 0) {
                if (tmp < a[end]) {
                    a[end + gap] = a[end];
                    end -= gap;
                } else {
                    ;
                }
            }
            a[end + gap] = tmp;
        }
    }
}