数据结构基础：插入排序与选择排序详解

基本思想： 希尔排序法又称缩小增量法。它的基本思想是：先选定一个整数（通常是 gap = n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序。然后 gap = gap/3+1 得到下一个整数，再将数组分成各组，进行插入排序。当 gap=1 时，就相当于直接插入排序。

它是在直接插入排序算法的基础上改进而来的，综合来说效率肯定是要高于直接插入排序算法的。

核心逻辑： 一组一组来使用直接插入，组的间隙慢慢变小，最后一层就是直接插入排序。这种方式相比于直接插入排序，外层的 ++ 循环变成了 gap 的递减，从 O(N) 到 O(logN)。

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

关于时间复杂度的说明： 外层循环的时间复杂度约为 O(log n)。内层循环的次数取决于 gap 的变化和数据的初始状态。希尔排序的时间复杂度估算较为复杂，通常介于 O(n log n) 到 O(n^2) 之间，最好的情况为 O(n^1.3)，最坏的情况为 O(n^2)。

三、选择排序

3.1 直接选择排序

基本思想： 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

通俗来讲，先遍历一遍，找一个最小的数据放第一个；然后遍历第二个到最后一个数据，找最小放在第二个……这样一直遍历、放置，数据就排好了。

代码实现： 这里采用双向选择的方式，每趟找出当前区域的最大值和最小值，分别放到两端。

void SelectSort(int* a, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        int mini = begin, maxi = begin;
        for (int i = begin; i < end; i++) {
            if (a[i] < a[mini]) {
                mini = i;
            }
            if (a[i] > a[maxi]) {
                maxi = i;
            }
        }
        
        // 注意处理最大值在当前区域第一个位置的情况
        if (maxi == begin) {
            maxi = mini;
        }
        
        swap(a[mini], a[begin]);
        swap(a[maxi], a[end]);
        
        begin++;
        end--;
    }
}

特性总结：

1. 思考非常好理解，但是效率不是很好，实际中很少单独使用。
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)

3.2 堆排序

堆排序在之前的二叉树部分已经讲过，这里主要复习一下核心逻辑。堆排序的关键在于深刻理解向下调整算法和向上调整算法。

向下调整算法（Max-Heap）： 为了得到升序结果，我们构建大顶堆。每次将堆顶元素（最大值）与末尾元素交换，然后对新的堆顶进行向下调整。

void AdjustDown(int* a, int parent, int n) {
    int child = parent * 2 + 1;
    while (child < n) {
        // 选择较大的子节点
        if (child + 1 < n && a[child] < a[child + 1]) {
            child++;
        }
        // 如果父节点小于子节点，则交换
        if (a[child] > a[parent]) {
            swap(a[child], a[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

void HeapSort(int* a, int n) {
    // 建堆
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, i, n);
    }
    
    int end = n - 1;
    while (end > 0) {
        swap(a[0], a[end]); // 将堆顶最大值移到末尾
        AdjustDown(a, 0, end); // 重新调整堆
        end--;
    }
}

四、总结

今天我们学习了插入排序和选择排序两大类算法。

• 插入排序：适合小规模或基本有序的数据，实现简单但效率有限。
• 希尔排序：插入排序的升级版，通过分组缩小增量，显著提升了性能。
• 选择排序：逻辑直观，但交换次数多，效率不高。
• 堆排序：利用堆结构，时间复杂度稳定在 O(N log N)，适合大规模数据。

下一篇我们将探讨快速排序，那将是另一场效率的革命。