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

性能分析

空间复杂度 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]);
        // 修正：max 有可能和 left 重叠
        if (left == max) {
            max = min;
        }
        swap(&a[right], &a[max]);
        left++;
        right--;
    }
}

性能分析

无论数据是否有序，比较次数固定，时间复杂度始终为 O(N^2)。空间复杂度 O(1)，不稳定。效率通常较低，一般不作为首选。

堆排序

核心思想

利用堆（完全二叉树）的特性进行排序。先将数组建成大顶堆，堆顶即为最大值。将堆顶与末尾元素交换，使最大值归位，然后重新调整剩余元素为大顶堆。重复直到有序。

代码实现

包含向上调整和向下调整两个辅助函数，实际排序主要使用向下调整建堆。

// 向下调整算法
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 次调整每次 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)。
• 对稳定性有要求：考虑插入或冒泡（小数据）。
• 内存受限：上述算法均为原地排序，空间开销极小。

实际开发中，C 标准库 qsort 或 C++ STL std::sort 通常基于混合策略（如 IntroSort），综合了多种算法的优势，建议直接调用而非手写底层实现。