排序算法全解析：从基础原理到动画可视化实战

在直接插入排序的基础上，利用二分查找确定插入位置，减少了比较次数，但移动元素的次数不变，整体复杂度仍为 O(n²)。适合对比较操作代价较高的场景。

希尔排序

希尔排序是插入排序的改进版。它先将待排序表分割成若干子表，分别进行直接插入排序，随着增量 d 逐渐缩小，最终达到全局有序。虽然效率提升明显，但破坏了稳定性。

void ShellSort(int A[], int n) {
    int d, i, j;
    // A[0] 只是暂存单元，不是哨兵
    for (d = n / 2; d >= 1; d = d / 2) {
        for (i = d + 1; i <= n; ++i)
            if (A[i] < A[i - d]) {
                A[0] = A[i];
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
                    A[j + d] = A[j];
                A[j + d] = A[0];
            }
    }
}

2. 交换类排序

冒泡排序

通过相邻元素两两比较，将较大的元素逐步'浮'到序列末尾。如果某一趟没有发生交换，说明已经有序，可以提前结束。

void BubbleSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;
        for (int j = n - 1; j > i; j--)
            if (A[j - 1] > A[j]) {
                swap(A[j - 1], A[j]);
                flag = true;
            }
        if (!flag) return;
    }
}

快速排序

快速排序是目前内部排序中平均性能最优的算法之一。核心思想是分治：选取一个枢轴（pivot），将序列划分为两部分，左边小于枢轴，右边大于等于枢轴，然后递归处理。

注意：快排是不稳定的。在最坏情况下（如序列本身有序且枢轴选择不当），时间复杂度会退化到 O(n²)。工程实践中常采用'三数取中'或随机选择枢轴来优化。

int Partition(int A[], int low, int high) {
    int pivot = A[low];
    while (low < high) {
        while (low < high && A[high] >= pivot) --high;
        A[low] = A[high];
        while (low < high && A[low] <= pivot) ++low;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

3. 选择类排序

简单选择排序

每一趟从待排序元素中选出最小（或最大）的元素，放到已排序序列的末尾。虽然实现简单，但效率较低，且不保证稳定性。

堆排序

堆排序利用大根堆（或小根堆）的性质，每次取出堆顶元素（最大值），将其与末尾元素交换，并重新调整堆结构。堆排序的时间复杂度稳定在 O(n log n)，且不需要额外的辅助空间。

void BuildMaxHeap(int A[], int len) {
    for (int i = len / 2; i > 0; i--)
        HeadAdjust(A, i, len);
}

void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);
    for (int i = len; i > 1; i--) {
        swap(A[i], A[1]);
        HeadAdjust(A, 1, i - 1);
    }
}

4. 归并与基数排序

归并排序

归并排序也是基于分治策略，将两个有序子序列合并为一个。它的稳定性很好，常用于外部排序，但需要 O(n) 的额外空间。

void MergeSort(int A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(A, low, mid);
        MergeSort(A, mid + 1, high);
        Merge(A, low, mid, high);
    }
}

基数排序

适用于整数或字符串排序。通过按关键字位分配和收集数据，可以达到线性时间复杂度 O(d(n+r))，但受限于数据类型和位数。

高级主题与外部排序

外部排序原理

当数据量超过内存容量时，必须使用外部排序。基本流程是：

1. 读入部分数据到内存，进行内部排序，生成初始归并段。
2. 将这些归并段在内存中进行多路归并，直到得到最终有序文件。

为了减少磁盘 I/O 次数，可以采用败者树加速多路归并的比较过程，或者构建最佳归并树（哈夫曼树）来最小化 WPL（带权路径长度）。

置换 - 选择排序

这是一种生成初始归并段的优化算法。它能让每个初始归并段的长度超过内存工作区的大小限制，从而减少归并段的数量，进而降低后续归并的 I/O 开销。

最佳归并树

在 m 叉归并中，若初始归并段数量无法构成严格的 m 叉树，需要补充若干个长度为 0 的'虚段'，以确保归并树的构造符合哈夫曼树原则，从而实现磁盘 I/O 次数的最小化。

总结与选型建议

实际工程中，往往不会只依赖一种算法。例如 C++ STL 中的 std::sort 通常结合了快速排序、堆排序和插入排序的优势；而大规模数据处理则倾向于使用归并排序配合外部存储。理解这些算法的特性，才能根据具体业务场景做出最优选择。