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

效率分析：

• 空间复杂度：O(1)
• 时间复杂度：最好 O(n)，最坏 O(n²)
• 稳定性：稳定

折半插入排序

思路是用折半查找找到应该插入的位置，再移动元素。当 low>high 时停止，应将 [low, i-1] 内的元素全部右移。为了保证稳定性，当 A[mid]==A[0] 时，应继续在 mid 所指位置右边寻找插入位置。

void InsertSort(int A[], int n) {
    int i, j, low, high, mid;
    for(i=2; i<=n; i++) {
        A[0] = A[i]; // 将 A[i] 暂存到 A[0]
        low=1; high=i-1; // 设置折半查找的范围
        while(low<=high) {
            mid=(low+high)/2;
            if(A[mid]>A[0]) high=mid-1;
            else low=mid+1;
        }
        for(j=i-1; j>=high+1; --j) A[j+1]=A[j]; // 统一后移元素
        A[high+1]=A[0]; // 插入操作
    }
}

虽然比较次数减少了，但移动元素的次数没变，整体时间复杂度依然是 O(n²)。对于链表，不需要依次右移，移动次数变少，但对比次数仍是 O(n²)。

交换与选择类排序

冒泡排序

从后往前（或从前往后）两两比较相邻元素的值，若为逆序则交换它们。第 n 趟结束后，最小的 n 个元素会'冒'到最前边。若某一趟没有发生交换，说明已经整体有序。

void swap(int &a, int &b){
    int temp = a; a = b; b = temp;
}

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==false) return; // 本趟遍历后没有发生交换，说明表已经有序
    }
}

性能：最好 O(n)，最坏 O(n²)，稳定，适用于顺序表和链表。

简单选择排序

每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。

void SelectSort(int A[], int n){
    for(int i=0; i<n-1; i++){
        int min=i;
        for(int j=i+1; j<n; j++)
            if(A[j]<A[min]) min=j;
        if(min!=i) swap(A[i],A[min]);
    }
}

无论有序还是乱序，都需要 n-1 趟处理，总对比次数为 n(n-1)/2。不稳定。

快速排序

分治思想的代表。任取一个元素 pivot 作为枢轴，通过一趟排序将待排序表划分为独立的两部分 L[1…k-1] 和 L[k+1…n]，使得左边小于 pivot，右边大于等于 pivot。然后递归地对两个子表重复上述过程。

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;
}

缺点与优化：若每次选中的枢轴划分很不均匀，会导致递归深度增加。建议采用三数取中法或随机选择枢轴来优化。

性能：平均 O(n log n)，不稳定。

堆排序

基于大根堆或小根堆结构实现动态极值维护。大根堆中任意根≥左、右孩子。建堆过程时间复杂度为 O(n)，排序过程为 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);
    }
}

void HeadAdjust(int A[], int k, int len){
    A[0]=A[k];
    for(int i=2*k; i<=len; i*=2){
        if(i<len&&A[i]<A[i+1]) i++;
        if(A[0]>=A[i]) break;
        else{ A[k]=A[i]; k=i; }
    }
    A[k]=A[0];
}

性能：O(n log n)，稳定空间复杂度 O(1)，不稳定。

归并与基数排序

归并排序

分治策略合并有序子序列。核心操作是把数组内的两个有序序列归并为一个。2 路归并的归并树形态上就是一棵倒立的二叉树。

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);
    }
}

void Merge(int A[], int low, int mid, int high){
    int *B=(int *)malloc((high-low+1)*sizeof(int));
    int i, j, k;
    for(k=low; k<=high; k++) B[k-low]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid&&j<=high; k++){
        if(B[i]<=B[j]) A[k]=B[i++];
        else A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++];
    while(j<=high) A[k++]=B[j++];
    free(B);
}

性能：O(n log n)，稳定，空间复杂度 O(n)。

基数排序

按关键字位分配与收集数据，适用于整数或字符串排序。按照各个关键字位权重递增的次序（个、十、百），对 d 个关键字位分别做'分配'和'收集'。

适用场景：数据元素的关键字可以方便地拆分为 d 组，且 d 较小，每组取值范围不大，数据量 n 较大。

性能：O(d(n+r))，稳定。

外部排序与高级优化

外部排序原理

数据元素太多，无法一次全部读入内存进行排序。通常使用'归并排序'的方法，最少只需在内存分配 3 块大小的缓冲区即可对任意一个大文件进行排序。构造初始'归并段'，然后进行多趟归并。

败者树

在多路平衡归并中，可视为一棵完全二叉树。k 个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的'失败者'，而让胜者往上继续进行比较。这能加速多路归并的比较过程，降低全局排序时间。

置换 - 选择排序

可以让每个初始归并段的长度超过内存工作区大小的限制。从 FI 输入 w 个记录到工作区 WA，选出其中关键字取最小值的记录输出到 FO 中去，若 FI 不空，则从 FI 输入下一个记录到 WA 中，重复此过程直到选不出新的 MINIMAX 记录。

最佳归并树

归并过程中磁盘 I/O 次数=归并树的 WPL*2。因此要让磁盘 I/O 次数最小，就要使归并树的 WPL 最小，即构建一个哈夫曼树。对于 k 叉归并，若初始归并段的数量无法构成严格的 k 叉归并树，则需要补充几个长度为 0 的'虚段'。