数据结构-排序(8)

8.1 排序的基本概念

排序（sort），就是重新排列表中元素，使得表中的元素满足按关键字有序的过程

具有稳定性：关键字相同的元素在排序之后相对位置不变

不能说稳定的排序比无稳定的排序好

  • 内部排序：数据都在内存中
  • 外部排序：数据太多，无法全部放入内存，还要关注如何使读/写磁盘次数更少

8.2 插入排序

插入排序：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 直接插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(int i=1;i<n;i++){
        if(A[i]<A[i-1]){
            temp=A[i];
            for(int j=i-1;j>=0&&A[j]>temp;--j){
                A[j+1]=A[j]; // 其他元素右移
            }
            A[j+1]=temp; // 复制到插入位置
        }
    }
}
//带哨兵
void InsertSort(int A[],int n){
    int i,j;
    for(int i=2;i<n;i++){
        if(A[i]<A[i-1]){
            temp=A[i];
            for(int j=i-1;A[j]>A[0];--j){
                A[j+1]=A[j]; // 其他元素右移
            }
            A[j+1]=temp; // 复制到插入位置
        }
    }
}

空间复杂度：\(O(1)\)

时间复杂度：\(O(n^2)\)

折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 折半插入排序
void InsertSort(int A[],int n){
    int i,j,temp,low,high,mid;
    for(int i=0;i<n;i++){
        temp = A[i];
        low=0,high=i-1;
        while(low<=high){
            mid = (low+high)/2;
            if(A[mid]>temp) high=mid-1;
            else low=mid+1;
        }
        for(int j=i-1;j>=high+1;--j){
            A[j+1] = A[j];
        }
        A[high+1]=temp;
    }
}

希尔排序

希尔排序：先将待排序表分割成若干形如 \(L[i,i+d,i+2d,...,i+kd]\) 的特殊子表，对各个子表分别进行插入排序。缩小增量 \(d\) （比如除以 \(2\) ），直到 \(d=1\) 为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ShellSort(int A[],int n){
    int d,i,j;
    for(d=n/2;d>=1;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]; //插入
            }
        }
    }
}

空间复杂度：\(O(n)\)

时间复杂度：和增量序列有关，目前无法用数学手段证明。最坏为 \(O(n^2)\) ，当 \(n\) 在某个范围内时，可达 \(O(n^{1.3})\)

8.3 交换排序

交换排序：根据序列中两个元素关键字的比较结果，来交换这两个记录在序列中的位置

冒泡排序

从后往前，两两比较相邻元素的值，若为逆序，则交换位置，直到序列比较完，称这为一趟冒泡排序。算法是稳定的。

顺序表、链表都可使用

1
2
3
4
5
6
7
8
9
10
11
12
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(1)\)

时间复杂度：\(O(n^2)\)

冒泡排序的交换次数是序列中的逆序对数

快速排序

任取一个元素 \(pivot\) 作为枢纽（基准），通过一趟排序使得划分成 \(L[1,k-1]\) 和 \(R[k+1,n]\) ，其中序列 \(L\) 的元素均小于 \(pivot\) ，序列 \(R\) 的元素均大于等于 \(pivot\) 。然后分别对 \(L,R\) 进行如此的递归操作，直到每个部分只有一个元素或为空为止。

image-20260518210031056

一次“划分”，仅指一个部分上的一次处理。一趟排序，则指对所有尚未确定最终位置的所有元素进行一遍处理的

空间复杂度：\(O(递归层数)\)

最好时间复杂度：\(O(n\log n)\)

最坏时间复杂度：\(O(n^2)\)

平均时间复杂度：\(O(n\log n)\)

枢纽元素选取的优化

  1. 选头、中、尾三个位置的元素，取中间值
  2. 随机选一个元素

该算法不稳定

8.4 选择排序

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

简单选择排序

每一趟选取最小（最大）的元素，与对应位置交换。整个排序过程，一定会进行 \(n-1\) 趟，并且不稳定。

顺序表、链表都可使用

堆排序

大顶堆（大根堆）：一颗二叉树中，结点元素关键字大于等于其左右孩子

小顶堆（小根堆）：与之相反

image-20260519154437799

堆排序：每一趟将对顶元素加入有序子序列（与待排序序列中的最后一个元素交换），并将待排序元素序列再次调整为大根堆（小根堆）。大根堆得到递增序列，小根堆得到递减序列。

1
2
3
4
5
6
7
void HeapSort(int A[].int n){
    buildMaxHeap(A,len);
    for(int i=len;i>1;i--){ // 执行n-1趟
        swap(A[i],A[1]); // 堆顶和堆底元素交换位置
        HeadAdjust(A,1,i-1); // 把剩余的待排序元素整理成堆
    }
}

时间复杂度：\(O(n\log n)\)

空间复杂度：\(O(1)\)

稳定性：不稳定

堆的插入与删除

插入到堆底，然后不断上升

删除元素与堆底交换位置，再让原堆底元素下坠。

8.5 归并、基数、计数排序

归并排序

归并（Merge）：把两个或多个已经有序的序列合并成一个

image-20260519160524988

时间复杂度：\(O(n\log n)\)

空间复杂度：\(O(n)\)

稳定性：稳定

基数排序

基数排序擅长解决如下问题：

  • 数据元素的关键字可以方便地拆成 \(d\) 组，且 \(d\) 较小
  • 每组关键字的取值范围不大，即 \(r\) 较小
  • 数据元素个数 \(n\) 较大

image-20260519161105571

image-20260519161241613

时间复杂度：\(O(r)\)

空间复杂度：\(O(d(n+r))\)

稳定性：稳定

计数排序(*)

image-20260519162311524

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 计数排序
#include <cstring>
constexpr int MAXN = 1010;
constexpr int MAXW = 100010;

int cnt[MAXW], b[MAXN];

int* counting_sort(int* a, int n, int w) { // n:|a| w:a[i]的最大值
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i]]; // 记录
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1]; // 计算前缀和
  for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i]; // 将a放入输出数组b
  return b;
}

空间复杂度：\(O(n+k)\)

时间复杂度：\(O(n+k)\)

稳定性：稳定

8.6 外部排序

外部排序的基本方法

使用归并排序的方法，最少只需再内存中分配3块大小的缓冲区即可对任意一个大文件进行排序。每次读入两个块的内容，进行内部排序后写回磁盘。

外部排序时间开销=读写外存的时间+内部排序所需的时间+内部归并所需时间

采用多路归并可以减少归并趟数（需要n个输入缓冲区），从而减少磁盘I/O（读写）次数

image-20260519222538299

\(k\) 路平衡归并：

  1. 最多只有 \(k\) 个段归为一个
  2. 每一趟归并总，若有 \(m\) 个归并段参与归并，则经过这一趟处理得到 \(\lceil m/k \rceil\) 个新的归并段
  3. 但需要对比关键字 \(k-1\) 次

败者树

image-20260519233942143

置换-选择排序

image-20260519235154534

最佳归并树

image-20260520000310925