基本思想

插入排序的核心逻辑是将未排序的元素逐一插入到已排序的序列中，直至所有元素有序。这种思想类似于整理手中的扑克牌：从无序区域取出一张牌，与有序区中的牌比较，找到合适位置插入。直接插入排序是这一思路的简单实现，而希尔排序通过分组预排序提升效率。

1. 直接插入排序

对于第i个元素（i≥1），假设前i个元素已经排序，将第i+1个元素（即当前待插入元素）与前面已排序部分从后往前依次比较，找到正确位置后插入，并将后续元素后移一位。

void insertionSort(int data[], int len) {
    for (int idx = 0; idx < len - 1; idx++) {
        int curPos = idx;
        int tempVal = data[curPos + 1];
        while (curPos >= 0) {
            if (data[curPos] > tempVal) {
                data[curPos + 1] = data[curPos];
                curPos--;
            } else {
                break;
            }
        }
        data[curPos + 1] = tempVal;
    }
}

特性总结：

• 数据越接近有序，直接插入排序表现越好。
• 时间复杂度：最好情况O(N)（已有序），最坏情况O(N²)。
• 空间复杂度：O(1)，仅使用常数级额外空间。

2. 希尔排序

希尔排序又称缩小增量排序。它通过选择一个增量gap（通常初始为n/3+1），将数组按间隔gap分成多个子序列，分别对每个子序列进行插入排序。然后逐步减小gap，重复过程，直到gap=1时做最后一次直接插入排序。相比直接插入排序，它能更快地将较小元素移动至前端。

void shellSort(int data[], int len) {
    int gap = len;
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int idx = 0; idx < len - gap; idx++) {
            int curPos = idx;
            int tempVal = data[curPos + gap];
            while (curPos >= 0) {
                if (data[curPos] > tempVal) {
                    data[curPos + gap] = data[curPos];
                    curPos -= gap;
                } else {
                    break;
                }
            }
            data[curPos + gap] = tempVal;
        }
    }
}

特性总结：

• 希尔排序是对直接插入排序的改进，尤其适合中等规模数据。
• 当gap>1时进行预排序，使数组逐步接近有序；当gap=1时，可直接完成排序。
• 时间复杂度难以精确计算，受gap选择影响。经典教材《数据结构（C语言版）》（严蔚敏）中指出，希尔排序的时间复杂度大约在O(N^1.2)到O(N^1.5)之间，外层循环次数约为O(log N)。