【数据结构】第八章 排序

第八章 排序

8.1 排序的基本概念

一、定义

重新排序排列表中的元素，使得表中元素满足按关键字有序的过程。为了查找方便，计算机通常希望元素排列是有序的。

算法的稳定性：假设i和j元素的关键字大小相同，但是i在j前面。如果算法结束后i还在j前面则算法是稳定的；反之则为不稳定的。

排序算法分类

• 内部算法：数据都在内存中，需要关注算法时空复杂度
• 外部排序：数据太多无法全部放入内存，因此还需要关注如何使得读写磁盘次数较少

8.2 插入排序

一、直接插入排序

假设要将一个元素L(i)插入到有序子序列L[1…n]中，则需要执行以下操作：

1. 查找出L(i)在L[]中的位置k
2. 将L[k…n]个元素向后移动一个单位
3. 将L(i)复制到L(k)

为了实现对L[1…n]的排序，可以先将L[1]看作为有序子序列，然后将后续n-1个元素逐次插入到前面的子序列中，因此需要执行n-1次上述的操作。

void insertSort(int a[], int n){
int j,temp;
for (int i = 0; i < n; ++i) {
if (a[i] temp = a[i];
for (j = i-1; j>=0 && a[j]>temp ; --j) { // 检查前面所有已排序的元素
a[j+1]=a[j]; // 所有大于temp的元素都向后移位
}
a[j+1] = tmp;
}
}
}

插入排序可以实现原地排序，因此空间复杂度为O(1)。时间复杂度上，最好的情况是序列已经有序，因此只需要比较各个元素而不需要移动，因此为O(n);最坏的情况则是序列刚好逆序，需要比较的次数和需要移动的元素最多，时间复杂度为O(n²)；平均状态下，直接排序的时间复杂度为O(n²)。算法是稳定的。

二、折半插入排序

在直接插入排序中，总是一边比较一边移动元素。而折半插入排序则是将移动元素和插入元素的操作分离，也就是先使用折半查找找到元素插入位置，然后统一的移动待插入元素后的所有元素。需要注意的是，折半查找在low>high的时候停止，然后将[low, i-1]的元素全部右移一位，并且将A[0]复制到low所指的文职，而当A[mid]==插入元素的时候，为了保证算法的稳定性，应该继续在mid所知的位置右边寻找插入位置。

void insertSort1(int a[], int n){
    int i,j,low,high,mid;
    for (i = 0; i < n; ++) {
        a[0] = a[i];
        low =1;high=i-1;
        // 使用折半查找插入位置
        while (low<=high){
            mid=(low+high)/2;
            if (a[mid]>a[0]) high=mid-1;
            else low=mid+1;
        }
        
        // 将从high+1到i-1的元素整体后移
        for (j=i-1 ; j>=high+1 ; --j) {
            a[j+1]=a[j];
        }
        a[high+1]=a[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

折半插入排序减少了比较元素的次数，约为O(nlog₂n)；但是并没有减少元素移动次数。因此时间复杂度仍然是O(n²)，但是对数据量较小的序列表现出较好的性能。

三、希尔排序

希尔排序的基本思想是：先将排序表分割为若干个$L[i.i+d,i+2d,....i+kd]$的子表。也就是每次排序会设置一个增量d(或者称为步长)，将相聚距离为d的元素视为一个子表。比如d=4的时候，那么a[0],a[4],a[8]为一个子表。一般来说，对于有n个元素的序列，刚开始增量d₀=n/2。

确定好子表后，对每一个子表进行直接插入排序，完成该步操作后，各个子表的元素都有序了。接着进行第二趟处理，此时第二趟会缩小增量d的值，一般d₁=d₀/2，也就是是第一趟增量的一半。然后对各个子表进行排序，使得表中元素的有序度增加，以此类推，每趟排序都会缩小增量d的值并且对子表进行排序，直到d=1。一般来说，第n趟的增量d_n=d_n-1/2

代码：

性能：
不需要额外空间，因此时间复杂度为O(1)
平均时间复杂度目前尚未证明，但是最坏情况下时间复杂度为O(n²)，当n在某个范围的时候，其复杂度为O(n^1.3)
希尔排序是不稳定的，并且只适用于顺序表，不适用于链表

8.3 交换排序

交换排序会比较两个元素的关键字，然后根据比较结果来决定是否交换；两个关键字位置

一、冒泡排序

从后往前两两比较元素的值，每一趟排序都可以将一个元素移动到最终位置，已经确定好位置的元素无需对比。如果在某一趟中没有发生交换，那么证明剩余序列已经有序，可以提前结束了。

// 冒泡排序
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)
            return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

性能：
空间复杂度：O(1)
时间复杂度:
最好情况是有序的，为O(n)；最坏情况为逆序，需要交换$\frac{n(n-1)}{2}$为O(n²)；平均的复杂度也是O(n²)
冒泡排序是稳定的，适用于链表。

二、快速排序

该算法的考察频率较高，请着重理解
基本思想
快速排序的基本思想是分治法。在待排序列L[1…n]中选择任意元素pivot作为枢轴，然后将大于pivot的元素放置在pivot右边，将小于pivot的元素放置在pivot左边，形成L[1…k-1]和L[k+1…n]两个子序列。快速排序算法会递归地对划分出来的两个子序列L[1…k-1]和L[k+1…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; // 当low==high的时候遭到枢轴的位置了
    return low; // 返回枢轴最终位置
}

void quickSort(int a[], int low, int high){
    if (low<high){  // 递归结束条件：如果low>=high，那么本次递归就结束了
        int pivot = partition(a,low,high);  //确定pivot位置
        quickSort(a, low, pivot-1); // 排序pivot左侧
        quickSort(a, pivot+1, high);// 排序pivot右侧
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

快速排序算法性能
空间效率：由于快速排序是递归的，因此需要一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用的最大深度一致。最好的情况下，递归呈现为平衡二叉树状，为O(log₂n)；最坏情况发生在两个区域分别包含0和n-1个元素的时候，这种最大程度的不对称性若发生在每层递归上，则最坏情况深度为O(n)。

时间效率：在快速排序中，产生时间的主要是Partion函数和递归函数QuickSort，对于Partion函数，其需要的时间复杂度为O(n)，而对于QuickSort函数，其执行次数和递归深度有关，根据空间效率可知，最好的情况下，递归呈现为平衡二叉树状，为O(log₂n)；最坏情况栈深度为O(n)，因此，最坏时间复杂度为O(n²)；当刚好平衡划分的时候，最好的时间复杂度为O(nlog₂n)。

为了提高算法效率，应该尽可能的将数据中间值选作枢轴，但是又不值得为此遍历一次序列。因此可以在序列头，序列尾和序列中各选取一个元素，再从这三个元素中取中值，或者直接随机取一个元素，都可以降低最坏情况发生的概率。

在最理想的状态下，快速排序刚好平衡划分，这种情况下快速排序的运行速度将大大上升。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间相近，也是O(nlog₂n)，因此快速排序是所有内部排序算法中平均性能最优的算法。另外，快速排序是不稳定的。

TIPS：一趟排序表示的是一层quickSort的结果，一趟排序可以确定多个元素的位置

8.4 选择排序

选择排序的基本思想是：每一趟在后面n-i+1个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排元素只剩下一个，就不用再选了。

一、简单的选择排序

假设排序表为L[1…n]，第i趟从L[i…n]中选择关键字最小的元素与L(i)交换，每趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表。

空间效率：只使用常数个辅助单元，空间效率为O(1)

时间效率：简单选择排序中，元素移动操作次数很少，不会超过3(n-1)次，最好情况是移动0次。但是元素间比较次数和序列初始状态无关，都是n(n-1)次，因此时间复杂度为O(n²)

该算法不稳定，可用顺序表和链表表示

二、堆排序

堆的定义

在这之前，首先要描述下堆的定义，堆定义了这样一个可以看作为树的一维序列：

可以看到堆在物理上是一种一维的顺序序列，但是在逻辑上可以看作为一颗顺序二叉树。其前$\lfloor n/2\rfloor$个元素是非终端节点

如果根节点的元素值最大，并且任意非根节点值小于等于其双亲节点的值，则称之为大根堆（根大于等于左右紫薯）；反之，则称之为小根堆（根小于等于左右）

大根堆的建立

思路：把所有非终端节点都检查一遍，如果不符合大根堆要求，则将当前的节点和更大的一个孩子进行互换。根据顺序二叉树的规律，一般非叶子结点都在序列前部，因此对非终端节点的处理也比较方便。

而在对第n层节点的堆进行调整时，可能会破坏下一层的堆，那么在对第n层进行调整后，需要继续向下检查并且做出调整，这会使得小元素不断的下坠。

基于上述方式，建立大根堆会首先处理最后一个非终端节点，也就是顺序表中第$\lfloor n/2\rfloor$个元素，然后逐次向上处理直到根节点

代码实现

// 建立大根堆
// k表明本次进行堆排序的子树的根节点
void headAdjust(int a[], int k, int len){
    a[0] = a[k];    // a[0]用于暂存当前非终端节点
    //i=2*k表示节点k的左孩子，每次执行后进行i*=2则会继续继续搜索k节点的子树
    for (int i = 2*k; i < len; i*=2) {
        // a[i]和a[i+1]为兄弟节点，此步为了选中兄弟中较大的一个，并需要保证不越界
        if (i < len && a[i]<a[i+1]) 
            i++;
        if (a[0]>=a[i]) break;  // 如果a[0]>=a[i]，则证明符合大根堆，不需要进行调整
        else{
            a[k]=a[i];
            k=i;    // 修改k值递归向下查找，使得小元素不断下落
        }
    }
    a[k]=a[0];// 将节点放入最终位置
}

void buildMaxHeap(int a[], int len){
    for (int i = len/2 ; i > 0 ; i--) { // 从底层非终端节点向根节点遍历
        headAdjust(a, i, len);    
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

基于大根堆进行排序

堆排序的思路如下：首先将存放在原始序列L[1…n]中的n个元素建成初始堆，就如同上面所示。由于对本身的特点，堆顶元素就是最大值，堆底元素就是堆中最小值。

此时需要如下关键步骤a：将堆顶元素和堆底元素互换，并且将互换后的堆底元素（也就是原来堆中元素的最大值）移除出堆外（通常的处理手法是将堆长度-1，那么此时位于堆底的最大值元素就不在堆内了）。此时队列不满足堆的性质，堆被破坏，将堆顶元素向下调整重新构建大顶堆，再进行关键步骤a，那么堆中的最大元素又被移除出堆。重复这个过程直到还剩最后一个元素。可以看到，每一次构造堆然后移除堆顶元素，都能够确定原堆中一个元素的排序位置，直到还剩最后一个元素时，队序列是有序的

可见堆排序需要解决两个问题：如何将无序序列构造成堆？输出堆顶元素后，如何将剩余元素调整成新的堆？

一些结论：

• 一个节点每下坠一层，最多只需要对比关键字2次，如果节点在i层，则将这个节点向下调整最多只需要下坠h-i层，关键字对比不会超过2(h-i)次
• 第i层最多有2ⁱ⁼¹个节点，而只有1~h-1层需要调整，因此第i层最多会经历2ⁱ⁼¹2(h-i)次关键字对比,将整棵树调整为大根堆最多需要经历$$\sum _1^{i=h-1}{2}^i=1^2(h-i)$$次关键字对比
• n个节点的完全二叉树的树高$h=\lfloor lo{g}_{2}n\rfloor$
• 建立堆堆过程，关键字对比次数不超过4n，时间复杂度为O(n)
• 每一趟排序的时间复杂度不超过O(h)=O(log_2n)
• 算法不具有稳定性

堆的插入和删除

以小根堆为例
插入
对于小根堆，新元素存放在队尾，并且和父节点对比，如果新元素比父节点更小，则将两者互换，新元素就一路上升，直到无法上升。

删除
在小根堆中，被删除元素用堆底元素替代，然后让该元素下坠，直到无法下坠为止

8.5 归并排序

什么是归并：将两个或者多个已经有序的序列合并成一个。比如n个有序序列，只需要不断对比这些序列的头部，选出其中最小元素放入新数组，那么最后将获得一个有序的新数组。将n个有序序列归并成为n路归并

归并排序的基本思路：
在一个n个元素的乱序顺序表中，可以将其中的每一个元素视作一个已经有序的只有一个元素的顺序表，下一趟则将各个有序的顺序表进行二路归并，得到若干个元素个数最多为2的有序顺序表，再进行下一趟二路归并，得到到若干个元素个数最多为4的有序顺序表，循环往复，直到只剩下一个有序的顺序表则排序完成

代码实现

// 归并排序
int *b= (int *)malloc(n*sizeof(int));   // 辅助数组

// 一趟归并
// 每一趟的a[low...mid]和a[mid...high]是有序的
void mergeSort(int a, int low, int mid, int high){
    int i,j,k;
    for (k = low; k <= high; ++k) {
        b[k]=a[k];  // 复制a到b中
    }
    for (i = low, j=mid+1, k=i; i<=mid && j<=high; k++) {
        if (b[i]<=b[j]){    // 如果左指针的值小于右指针的值
            a[k]=b[i];      // 放入左指针的值
            i++;
        }else{
            a[k]=b[j];
            j++;
        }
    }
    while (i<=mid){a[k++]=b[i++];}
    while (j <= high){a[k++]=b[j++];}
}

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);   // 一趟归并
    }
}
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
27
28
29
30
31

算法性能分析
归并排序很像一个倒立的二叉树，称之为归并树

设顺序表中有n个元素的乱序顺序表，如果归并树树高为h，则$n\le 2^{h-1}$。归并树高代表着其归并的趟数，每一趟归并的时间复杂度为O(n)，因为每一趟最多需要进行n-1次比较，最少需要进行n/2次比较，因此，算法时间复杂度为$O(nlo{g}_{2}n)$

空间复杂度为O(n)，主要来自于辅助数组。

该算法是稳定的

8.6 基数排序

算法思想：
不知道怎么描述，日后再补

算法效率分析：
需要r个辅助队列，空间复杂度为O®，因为基数排序中队列是用链式结构存储的，实际上只有两个指针域。

一趟分配为O(n)，一趟收集需要收集r个队列，为O®，因为收集队列中的元素只需要改变其首尾指针。总共d趟分配和收集，总的时间复杂度为O(d(n+r))

基数排序适用于：

• 数据元素关键字可以方便拆分为d组，并且d比较小
• 每组关键字取值范围不大，也就是r比较小
• 数据元素个数n比较大，因为其他排序算法对n的操作的最小时间复杂度为$O(nlo{g}_{2}n)$

8.7 外部排序

外存和内存之间的交换是以块为单位进行交换的，如果内存需要数据则读取对应块，处理后将处理好的块进行写回。

有时候数据元素太多，无法一次全部读入内存进行排序，因此需要外部排序

对于外部排序，一般使用归并排序，因为归并排序要求各个子序列有序，所以可以每次读入两个块的内容，进行内部排序后写回磁盘，那么最少在内存中分配三个块打戏哦啊的缓冲区就可以对任意大小的数据进行排序。其中包括两个输入缓冲区和一个输出缓冲区。

接着就会划分归并段，将两个块读入缓冲区1和缓冲区2中，将其内部排序后通过输出缓冲区输出，那么归并段中是有序的了

接着进行归并排序，将两个归并段进行归并排序后合成为一个更大的归并段，循环往复直到只剩下一个归并段。划分归并段中的排序和归并排序的区别是，划分归并段的时候，两个块是完全放入内存中的，所以采用什么排序方式都行；但是在进行归并的时候，因为每次只能读入一部分归并段，所以只能进行归并排序

在一趟归并中，每次只会取两个归并段中位于头部的块进行归并，因为输入输出缓冲区每次只能容纳一个块，每当缓冲区空，都会读入下一块。

时间开销的分析
在一个有n个块的数据中
生成初始归并段：读写各需要n次，并且需要进行内部排序
第i趟归并：读写各需要n次，并且需要内部归并

外部排序时间开销=读写外存的时间+内部排序所需要的时间+内部归并所需的时间
读写磁盘次数=$文件块数\cdot 2+文件块数\cdot 2\cdot 归并趟数$

一、优化：多路归并

增加输入缓冲区，能够使得趟数减少。
对于r个初始归并段，作k路归并，则归并树可以使用k叉树表示，如果树高为h，则第h层最多有$k^{h-1}$个节点，也就是$r\le k^{h-1}$,推导得归并趟数=h-1=$\lceil lo{g}_{k}r\rceil$

多路归并需要增加输入缓冲区，也会增加内存开销，并且每挑选一个关键字需要对比关键字(k-1)次，内部归并时间会增加

k路平衡归并：

1. 最多只能有k个段归并为1个
2. 每一趟归并中，如果有m个归并段参与归并，则经过这一趟处理达到$\lceil m/k\rceil$个新的归并段

二、优化：减少初始归并段数量

生成初始归并段的内存工作区越大，归并趟数越小

三、优化：败者树

使用多路平衡归并的缺点是：使用k路平衡归并，选出一个最小元素需要对比关键字k-1次

败者树结构
败者树可视作一棵完全二叉树，区别是败者树在完全二叉树的根节点之上还有一个节点，为胜者节点。败者树有很多应用，其中一个是用于优化多路平衡归并。败者树十分类似于平时进行体育竞赛时的晋级机制。

败者树构造
叶子节点会两两对比，其父节点为失败节点，在多路平衡归并中需要选出的是最小的元素，因此其父节点会是两个子节点中较大的那个，而较小的值会继续向上走，和其他的元素对比。最终构造出的败者树如下：（注意⚠️途中非叶子节点记录的是值来自于哪个段，而非值本身）

根据冠军节点，可知道冠军来自于哪个段，此时可以该段的首元素就是这些段中的最小值。此时败者树构造完毕。

败者树在构造时，需要进行对比的次数就是它的非根非叶子节点的个数，实际上就是k-1次对比

败者树的后续对比
上图中可知归并段3的首元素1为最小值，此时将该元素送往输出缓冲，然后将归并段3的下一个元素放置在对应的叶子节点中，进行下一次对比，可以对比出当前序列中的最小值。并且在k路归并中，只需要对比关键字$\lceil lo{g}_{2}k\rceil$次，从而减少了多路归并中内部排序对比关键字的次数。

在代码构造中，为了缩减内存空间开销，叶子节点并不是直接的节点，而是一个指向归并段首元素的指针

三、优化：置换-选择排序

可以构造更长更大初始归并段。以前的初始归并段的大小和内存中的缓冲区相关，而置换选择排序可以克服这种限制

四、优化：最佳归并树

归并树的读写磁盘数量

计算这棵树的带权路径长度，可以得出WPL=2*1+(5+1+6+2)*3，是等于读磁盘次数，也等于写磁盘次数

因此归并过程的磁盘IO次数=归并树的WPL*2
而在第五章 树的内容中，可以知道WPL最小的树为哈夫曼树，因此用哈夫曼树构造归并树可以得到最佳归并树，使得读写磁盘次数最小。

对于k叉归并的时候，如果初始归并段的数量无法构成严格的k叉归并树，则需要补充几个长度为0的虚段，再进行k叉哈夫曼树的构造。

k叉的最佳归并树一定是一棵严格的k叉树，树中只包含度为0或者k的结点，因此归并树的总结点数n=初始归并段数量+虚段段数

1. 如果(初始归并段-1)%(k-1)=0，说明可以构成严格k叉树，此时不需要添加虚段
2. 如果(初始归并段-1)%(k-1)不为0，说明不可以构成严格k叉树，此时需要添加(k-1)-u个虚段

8.8 排序算法的应用

一、各个算法性质

排序趟数和原始序列无关的是：直接插入排序，简单选择排序，基数排序
每趟排序都能至少确认一个元素的最终位置的是：简单选择排序，快速排序，堆排序