五大经典排序算法详解：插入、希尔、冒泡、选择与堆排序

核心思想

希尔排序是插入排序的改进版，核心思想是分组插入排序，逐步缩小增量。将整个数组按某个增量（步长）分割成若干子序列，分别进行插入排序，使数组整体变得'基本有序'。随后逐步缩小增量，直到增量为 1 时完成最后一次插入排序。

想象一下先把乱序的扑克牌按花色分组整理，再按点数细分整理，最后整体微调。大增量时移动跨度大，能快速让数组大致有序；小增量时利用插入排序在近乎有序数据上的高效性。

代码实现

void ShellSort(int* a, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1; /* 增量序列，也可用 gap/2 */
        
        // 多组并排，每组内部进行插入排序
        for (int j = 0; j < gap; j++) {
            for (int i = j; i < n - gap; i += gap) {
                int end = i;
                int tmp = a[i + gap];
                while (end >= 0) {
                    if (tmp > a[end]) { // 降序逻辑
                        a[end + gap] = a[end];
                        end -= gap;
                    } else {
                        break;
                    }
                }
                a[end + gap] = tmp;
            }
        }
    }
}

复杂度与稳定性

• 时间复杂度：取决于增量序列的选择，通常介于 O(NlogN) 和 O(N^2) 之间，常归为 O(NlogN) 量级。
• 空间复杂度：O(1)。
• 稳定性：不稳定。跳跃调整可能改变相同值元素的原始相对顺序。

选择排序：逐步选择最值

核心思想

选择排序的核心是逐步选择最值，构建有序序列。每次从未排序部分中选出最小（或最大）的元素，将其与未排序部分的第一个元素交换位置。

就像从一堆打乱的扑克牌里，每次挑出最小的一张，放到已整理好的牌堆后面。

代码实现

这里展示一种双向优化的选择排序版本，同时寻找最大值和最小值。

void SelectSort(int* a, int n) {
    int left = 0;
    int right = n - 1;
    
    while (left < right) {
        int max = left;
        int min = left;
        
        // 在一趟中寻找最大和最小值的索引
        for (int i = left + 1; i <= right; i++) {
            if (a[max] < a[i]) {
                max = i;
            }
            if (a[min] > a[i]) {
                min = i;
            }
        }
        
        swap(&a[left], &a[min]);
        
        // 修正：如果最大值恰好在 left 位置，交换后 max 指向了原 min 的位置
        if (left == max) {
            max = min;
        }
        
        swap(&a[right], &a[max]);
        left++;
        right--;
    }
}

复杂度与稳定性

• 时间复杂度：无论数据如何，都需要遍历，为 O(N^2)。
• 空间复杂度：O(1)。
• 稳定性：不稳定。交换操作可能破坏相同值元素的相对顺序。

堆排序：利用堆特性

核心思想

堆排序利用堆的特性进行排序。将待排序数组构建成一个大顶堆（或小顶堆），堆顶即为当前未排序部分的最大值。每次将堆顶元素与末尾元素交换，使该值归位，然后重新调整剩余元素为堆结构。

就像从一堆石头里每次挑出最重的一块，放到已排好的序列末尾。

代码实现

堆排序依赖两个关键函数：向下调整 AdjustDown 和向上调整 AdjustUp（建堆常用向下调整）。

// 向下调整算法
void AdjustDown(int* a, int n, int parent) {
    int child = 2 * parent + 1;
    while (child < n) {
        if (child + 1 < n && a[child + 1] > a[child]) {
            child++; // 选较大的子节点
        }
        if (a[child] > a[parent]) {
            swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

// 堆排序主流程
void HeapSort(int* a, int n) {
    // 1. 建堆：从最后一个非叶子节点开始向下调整
    for (int i = (n - 2) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
    
    // 2. 排序：交换堆顶与末尾，调整剩余堆
    int end = n - 1;
    while (end > 0) {
        swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}

复杂度与稳定性

• 时间复杂度：建堆 O(N)，排序阶段 N 次调整每次 O(logN)，整体 O(NlogN)。不受输入数据分布影响。
• 空间复杂度：O(1)。
• 稳定性：不稳定。堆调整过程中的交换会改变相同值节点的相对顺序。

冒泡排序：相邻元素交换

核心思想

冒泡排序通过相邻元素的比较与交换，让较大（或较小）的元素逐步'冒泡'到数组末尾。每一轮遍历后，当前未排序部分的最大值会被推到末尾。

就像水里的气泡，较大的元素慢慢浮到水面（数组末尾）。

代码实现

加入提前终止优化，若一趟无交换则说明已有序。

void BubbleSort(int* a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int flag = 0; // 标记本趟是否发生交换
        for (int j = 1; j < n - i; j++) {
            if (a[j - 1] > a[j]) {
                swap(&a[j - 1], &a[j]);
                flag = 1;
            }
        }
        if (flag == 0) {
            break; // 已有序，提前结束
        }
    }
}

复杂度与稳定性

• 时间复杂度：平均 O(N^2)，最优情况（已有序）为 O(N)。
• 空间复杂度：O(1)。
• 稳定性：稳定。仅在相邻元素前大于后才交换。

性能对比总结

选型建议：

1. 数据量小或基本有序：优先选择插入排序或冒泡排序（带优化）。它们在接近有序时表现优异，且实现简单。
2. 数据量大且要求效率：堆排序和希尔排序是更好的选择，它们都能达到 O(NlogN) 级别，且不需要额外空间。
3. 稳定性要求高：如果业务逻辑要求相等元素顺序不能变，只能在插入排序和冒泡排序中选择。
4. 避免使用：选择排序虽然逻辑简单，但交换次数多且不稳定，实际工程中较少作为首选。

注意：希尔排序的时间复杂度严格来说依赖于增量序列的选择，介于 O(NlogN) 和 O(N^2) 之间，但通常视为 O(NlogN) 量级处理。