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

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

代码实现

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 = 0; 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) 量级。外层控制 gap 迭代，内层处理插入，由于数组逐渐有序，实际效率远高于普通插入排序。
• 空间复杂度：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 指向了原 left 的值
        if (left == max) {
            max = min;
        }
        
        swap(&a[right], &a[max]);
        left++;
        right--;
    }
}

性能分析

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

堆排序

堆排序利用堆数据结构的特性。首先将数组构建成一个大顶堆（或小顶堆），堆顶即为当前最大值。每次将堆顶元素与末尾元素交换，使最大值归位，然后重新调整剩余元素为堆。重复此过程直至有序。

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

代码实现

// 向上调整算法 - 建大堆
void AdjustUp(int* a, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[child] > a[parent]) {
            swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

// 向下调整算法
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) {
    // 向下调整建堆 -- O(N)
    for (int i = (n - 2) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
    
    // 排序阶段
    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)。
• 稳定性：稳定。仅在相邻元素前大于后才交换，相等元素不移动。

性能对比总结

• 高效梯队：希尔排序和堆排序的时间复杂度约为 O(NlogN)，适合大规模数据。需注意希尔排序的实际表现依赖于增量序列的选择。
• 中等梯队：插入排序和冒泡排序在最坏情况下为 O(N^2)，但在数据接近有序时表现优异（接近 O(N)）。对于小规模或部分有序数据，插入排序往往比冒泡更实用。
• 基础梯队：选择排序无论数据状态如何，始终维持 O(N^2)，效率相对较低，一般不作为首选。

稳定性补充：冒泡、插入排序是稳定的；希尔、堆、选择排序是不稳定的。在实际工程中，若需保持相等元素的原始顺序，应优先选择稳定排序算法。