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

直接插入排序在数据量大且无序时效率低。希尔排序先设定一个较大的步长（gap），把相距 gap 的元素分成一组进行插入排序，让数组整体变得'基本有序'。然后逐步缩小 gap，重复上述过程，直到 gap=1 时再做最后一次插入排序。

这就像先把乱序的牌按花色分组整理，再按点数细分，最后整体微调。大增量能快速移动远距离元素，小增量则在近乎有序的数据上发挥插入排序的高效率。

代码实现

void ShellSort(int* a, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1; // 常用增量序列
        
        // 多组并排，每组内部进行插入排序
        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(N^1.3)。
• 空间复杂度：O(1)。
• 稳定性：不稳定。跳跃交换可能破坏相同值元素的原始顺序。

选择排序

核心思想

选择排序的思路很简单：每次从未排序部分选出最小（或最大）的元素，放到已排序部分的末尾。

虽然它也是分'已排序'和'未排序'，但它不像插入排序那样逐个插入，而是通过交换位置直接把极值归位。这个过程就像从一堆打乱的牌里，每次挑出最小的一张，放到整理好的牌堆后面。

代码实现

这里展示一种双向优化的版本，同时找最大值和最小值，减少遍历次数。

void SelectSort(int* a, int n) {
    int left = 0;
    int right = n - 1;
    
    while (left < right) {
        int max = left;
        int min = left;
        
        // 在 [left, right] 范围内寻找最大和最小值的下标
        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 位置，交换后它跑到了 min 的位置
        if (left == max) {
            max = min;
        }
        
        swap(&a[right], &a[max]);
        left++;
        right--;
    }
}

效率分析

• 时间复杂度：无论数据是否有序，都需要遍历 N 次，总比较次数为等差数列，固定为 O(N^2)。
• 空间复杂度：O(1)。
• 稳定性：不稳定。交换操作可能改变相等元素的相对顺序。

堆排序

核心思想

堆排序利用了**堆（Heap）**这种数据结构。通常使用大顶堆来实现升序排序。

1. 建堆：将无序数组构建成一个大顶堆，堆顶就是当前最大值。
2. 排序：将堆顶元素（最大值）与末尾元素交换，使最大值归位。然后调整剩余元素重新成为大顶堆。
3. 重复步骤 2，直到整个数组有序。

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

代码实现

堆排序的关键在于向下调整算法 AdjustDown。

// 向下调整算法
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. 向下调整建堆，时间复杂度 O(N)
    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-1 次调整，每次 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. 效率最高：希尔排序和堆排序通常在大数据量下表现更好，属于 O(NlogN) 量级。
2. 小规模数据：对于少量数据，插入排序往往比快速排序还快，因为常数项小且缓存友好。
3. 特殊场景：如果数据接近有序，插入排序和冒泡排序（带优化）效率极高。
4. 稳定性要求：如果需要保持相等元素的原始顺序（如多级排序），只能选插入、冒泡或归并（本文未展开）。
5. 选择排序坑点：虽然简单，但因为交换次数多且不稳定，实际工程中很少单独使用。

理解这些底层原理，有助于你在面对复杂业务需求时，做出更合适的算法选型。