数据结构之排序

数据结构之排序

第八章_排序

8.1 排序的基本概念

排序就是将表中的元素重新排列，使其按关键字有序的过程，也方便了后序的查找操作。

算法的稳定性： 算法的稳定性不能用来衡量算法的优劣（不同场景需求不同）。衡量排序算法的性能指标主要是时间复杂度和空间复杂度，其概念如下图所示：

排序算法的分类：

• 内部排序： 所有的元素都能放进内存中。
• 外部排序： 数据太多无法放入内存中，需要频繁在内、外存之间交换数据。

示意图如图所示：

这里推荐 旧金山大学(University of San Francisco) 开发的一个神奇的学习网站（末尾链接），可可视化查看各种算法。

8.2 插入排序

这是一种简单直观的算法，其基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中。

8.2.1 直接插入排序

实现代码如下：

//普通实现方式
void InsertSort(int A[], int n) {
    int i, j;
    for (i = 1; i < n; i++) { 
        if (A[i] < A[i - 1]) {
            int temp = A[i];
            for (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(i=2; i<=n; i++)         //依次将A[2]~A[n]插入到前面已排序序列
        if(A[i]<A[i-1]){        //若A[i]关键码小于其前驱，将A[i]插入有序表
            A[0]=A[i];          //复制为哨兵，A[0]不存放元素
            for(j=i-1; A[0]<A[j]; --j)//从后往前查找待插入位置
                A[j+1]=A[j];    //向后挪位
            A[j+1]=A[0];        //复制到插入位置
        }
}

对于直接插入排序性能分析如下：

• 空间效率： 空间复杂度 O(1)。

• 时间效率：

  • 最坏时间复杂度：时间复杂度为 O(n²)，发生 n (n - 1) / 2 即原始数据全部逆序的情况。
  • 最好时间复杂度：时间复杂度为 O(n)，比较次数为 n - 1 次，即原始数据全部有序的情况。
  • 平均时间复杂度：O(n²)

• 稳定性： 相同关键字的元素的相对顺序不会改变，直接插入排序是稳定的算法。

• 适用性： 该算法适用于顺序存储和线性存储的线性表，采用链式存储时无需移动元素。

8.2.2 折半插入排序

折半插入排序是在插入排序的基础上，先在已排序区间中用二分查找确定插入位置，再将该位置之后的元素整体后移一位，最后把当前元素插入到该位置。

值得注意的是：为了保证该排序算法的稳定性，二分查找过程中找到 mid 元素时，不会停止查找，而是会一直查找到 low > high 的情况，随后将 [low,i - 1] 区间内的元素整体右移，最后将元素插入 A[low] 的位置，实现代码如下：

//折半插入排序
void InsertSort(int A[], int n){
    int i, j, low, high, mid;
    for(i=2; i<=n; i++){                //依次将A[2]~A[n]插入前面的已排序序列
        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];               //插入操作
    }
}

折半插入排序相比直接插入排序只是在查找部分少查找了几个元素，因此其性能分析与直接插入排序并无区别。

8.2.3 希尔排序

希尔排序（Shell Sort）的基本思想是：通过逐步缩小增量的方式，对表中相隔一定距离的元素，构成的子序列进行多次直接插入排序。 注意不是分的连续的块，下面以图示说明： 注意，目前尚未找到理论最优的增量序列，希尔本人建议每次增量取上一次的一半，第一次取 n/2。实现代码如下：

//希尔排序
void ShellSort(int A[], int n){
    int d, i, j;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(d = n/2; d >= 1; d = d/2)      //步长变化
        for(i = d+1; i <= n; ++i)  // 看过来！！注意这里的算法是从 d+1 开始的哦，手算也要这么想哈！！
            if(A[i] < A[i-d]){         //需将A[i]插入有序增量子表           
                A[0] = A[i];           //暂存在A[0]                        
                for(j = i-d; j > 0 && A[0] < A[j]; j -= d)  
                    A[j+d] = A[j];     //记录后移，查找插入的位置
                A[j+d] = A[0];         //插入
            }//if
}

对希尔排序算法性能分析如下：

• 空间效率： 空间复杂度 O(1)。
• 时间效率： 时间复杂度依赖于所选的增量序列，最优增量序列仍是数学上未解难题，所以精确分析较为困难，但是 n 在常见范围时，时间复杂度约为 O(n^1.3) ；最坏情况退变为 O(n²)。
• 稳定性： 不稳定。
• 适用性： 该算法仅适用于顺序存储的线性表。

8.3 交换排序

8.3.1 冒泡排序

这是开始学习 C 语言就会学习的算法之一，在大类上属于“交换”这一类。

冒泡从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。称这样过程为“一趟”冒泡排序。如下图所示为向后（下标大的那端）进行冒泡：

冒泡： 指的是还在移动的元素的方向，不是指不断停下来的元素的方向。

理解之后从上图中代码我们重写一个向前冒泡：

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

//冒泡排序（降序，向前冒泡）
void BubbleSort(int A[], int n) {
    for (int i = n - 1; i > 0; i--) {  //从下表为 0 的位置开始存储
        bool flag = false;          //表示本趟冒泡是否发生交换的标志
        for (int j = 0; 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²)，发生 n (n - 1) / 2 次交换，即原始数据全部逆序的情况。
  • 最好时间复杂度：时间复杂度为 O(n)，比较次数为 n - 1 次，即原始数据全部有序的情况。
  • 平均时间复杂度：O(n²)

• 稳定性： 是稳定的算法。

• 适用性： 该算法适用于顺序存储和链性存储的线性表。

8.3.2 快速排序

算法思想： 在待排序表 L [1…n] 中任取一个元素 pivot 作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分 L [1…k-1] 和 L [k+1…n]，使得 L [1…k-1] 中的所有元素小于 pivot，L [k+1…n] 中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L (k) 上，这个过程称为一次 “划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或为空为止，即所有元素放在了其最终位置上。

其示意图如下，按照函数递归调用栈顺序： 实现代码如下：

//用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[],int low,int high){
    int pivot=A[low];        //第一个元素作为枢轴
    while(low<high){        //用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;             //返回存放枢轴的最终位置
}

//快速排序
void QuickSort(int A[],int low,int high){
    if(low<high){    //递归跳出的条件
        int pivotpos=Partition(A,low,high); //划分
        QuickSort(A,low,pivotpos-1);        //划分左子表
        QuickSort(A,pivotpos+1,high);       //划分右子表
    }
}

快速排序正如其名，确实是在考研数据结构中平均性能最优的内部排序算法。

对快速排序算法性能分析如下：

• 空间效率： 算法采用递归实现，需借助系统栈，栈的容量 = 递归调用的最大层数 = 按照二叉树划分的二叉树高度。

  • 最坏情况：划分极不平衡，空间复杂度为 O(log₂n)。
  • 最好情况：每次划分均分，空间复杂度为 O(n)。
  • 平均情况：空间复杂度为 O(log₂n)。

• 时间效率：

  • 最坏时间复杂度：时间复杂度为 O(n²)，每次划分仅确定一个元素的位置，发生 n (n - 1) / 2 次交换，即原始数据全部逆序的情况。
  • 最好时间复杂度：每次划分都将序列均分为两部分，时间复杂度为 O(nlog₂n)。
  • 平均时间复杂度：接近最快，O(nlog₂n)

• 稳定性： 是不稳定的算法。

• 适用性： 由于需要实现随机访问，该算法仅适用于顺序存储的线性表。

8.4 选择排序

8.4.1 简单选择排序

很简单，在每一次待排序序列中，选择关键字最大或者最小的元素加入有序子序列。 示意图如下： 实现代码如下：

//简单选择排序（升序）
void SelectSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {    //共进行 n-1 趟
        int min = i;      //记录最小元素位置
        for (int j = i + 1; j < n; j++) {   //在A[i...n-1]中选择最小元素
            if (A[j] < A[min]) {
                min = j;
            }
        }
        if (min != i) {
            swap(A[i], A[min]);
        }
    }
}

对简单选择排序算法性能分析如下：

• 空间效率： O(1)
• 时间效率： 恒为 O(n²)
• 稳定性： 是不稳定的算法。
• 适用性： 该算法适用于顺序存储和链式存储的线性表。尤其适合关键字较少的情况。

8.4.2 堆排序

8.4.2.1 堆排序

思想和简单选择排序一样：在每一次待排序序列中，选择关键字最大或者最小的元素加入有序子序列。 首先需要介绍两个概念：

• 大根堆： 任一结点，根 >= 左，右 的完全二叉树。
• 小根堆： 任一结点，根 <= 左，右 的完全二叉树。

在排序开始前，我们需要先使用二叉树的顺序存储将整个待排序序列放入一棵完全二叉树中。

接着，对于有 n 个结点的完全二叉树，最后一个分支结点的编号为 （向下取整）[n / 2] 。因此，我们直接从最后一个结点开始，向前处理至位序为 1 的结点。如图所示： 这个建立大根堆的算法的实现代码如下：

//建立大根堆
void BuildMaxHeap(int A[],int len){  //len 代表序列中的有效记录值，k 代表需要调整的根结点的下标。
    for(int i=len/2;i>0;i--)    //从后往前调整所有非终端结点
        HeadAdjust(A,i,len);
}

//将以 k 为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];                  //A[0]暂存子树的根结点
    for(int i=2*k;i<=len;i*=2){ //沿key较大的子结点向下筛选
        if(i<len&&A[i]<A[i+1])  //取key较大的子结点的下标，有右孩子且有孩子比左孩子大
            i++;
        if(A[0]>=A[i]) break;   //筛选结束
        else{
            A[k]=A[i];          //将A[i]调整到双亲结点上
            k=i;                //修改k值，以便继续向下筛选
        }
    }
    A[k]=A[0];                  //被筛选结点的值放入最终位置
}

由于只是在逻辑抽象为一棵完全二叉树，而且还不是 根>左>右 这种情况，不能想当然的使用先序遍历。

应该反复的执行 “将堆顶元素与末尾元素做交换（加入有序序列），将待排序序列再次调整为大根堆”。堆排序示意图如下： 堆排序实现代码如下：

void HeapSort(ElemType A[],int len){
    BuildMaxHeap(A, len);        //初始建堆
    for(int i=len;i>1;i--){     //执行n-1趟排序
        Swap(A[i],A[1]);         //输出堆顶元素（与堆底元素交换）
        HeapAdjust(A,1,i-1);     //把剩余i-1个元素重新整理为堆
    }
}

对堆排序算法的性能分析如下：

• 空间效率：仅使用了常数个辅助单元，空间复杂度为 O(1)。
• 时间效率：建堆的时间复杂度为 O(n)，随后需进行 $n-1$ 次堆顶输出与调整操作，每次调整的时间复杂度为 $O(\log_2n)$。因此，堆排序在最好、最坏和平均情况下的时间复杂度均为 $O(n\log_2n)$。
• 稳定性：在堆调整过程中，相等关键字的元素可能因交换而改变其原始相对位置，因此堆排序是不稳定的排序算法。例如，表 $L = {1,2,2}$，建堆时可能将2交换到堆顶，此时 $L = {2,1,2}$，最终排序序列为 $L = {1,2,2}$，显然，2与2的相对次序已发生变化。
• 适用性：堆排序依赖完全二叉树的随机访问特性，因此仅适用于顺序存储的线性表。

8.4.2.2 堆的插入和删除

给一个堆，如何进行元素的插入和删除？以小根堆为例。

• 堆的插入： 将新元素置于堆末端（数组末尾），然后自下而上地不停与其父结点比较，若不满足堆的性质，则交换。知道不能向上为止。示意图如下：
• 堆的删除： 将堆底元素放入空余位置，不停的与其最小（大）的孩子结点比较，若不满足堆的性质，则不断下沉，直到不能下沉为止。示意图如下：

8.5 归并排序（Merge Sort）

首先引入归并操作的概念：将两个或多个有序的合并成一个更长的有序序列。这里以 4 路归并为例，示意如下： 那在归并排序中，将每个元素看做一个长度为 1 有序序列，两两归并知道合成一个长度为 n 的有序表，这种排序算法称为 2 路归并排序。 示意图如下： 用代码实现当然需要进行递归操作，代码如下：

//辅助数组B（主要就起到一个复制过去操作的作用，原数组才是每次比对的结果数组）
int *B=(int *)malloc(n*sizeof(int)); 

//A[low...mid]和A[mid+1...high]各自有序，将两个部分归并
void Merge(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++];    //将较小值复制到A中
        else
            A[k]=B[j++];
    }//for
    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);  //归并
    }//if
}

对归并排序算法性能分析如下：

• 空间效率： 主要来自于数组的开销，而递归调用带来的开销是次要的（O(log₂n)）。空间复杂度为 O(n)。
• 时间效率： 每趟归并需要遍历所有 n 个元素，时间复杂度为 O(n)，共需进行（向上取整）[log₂n]趟，所以总时间复杂度为 O(nlog₂n)。
• 稳定性： 当两个元素的关键字相等的时候，你可以在算法中自己定义先取前一段还是后一段，因此是稳定的算法。
• 适用性： 仅需顺序访问，因此适用于链式存储和顺序存储的线性表。

从递归分治角度理解归并排序，在《考研视角下的 C 语言(下)》14.4 小节已有讲述，链接末尾。

8.6 基数排序

这种排序与前面的所有排序都不一样，不需要进行关键字的比对，而是基于关键字的各位大小进行排序。通常有两种办法：

• 最高位优先法（MSD）
• 最低位优先法（LSD）

那么多说无益，以最低位优先法为例，一图胜千言： 基数排序擅长解决的问题：

1. 数据元素的关键字可以方便地拆分为 d 组，且 d 较小。（反例：给 5 个人的身份证号排序）
2. 每组关键字的取值范围不大，即 r 较小。（反例：给中文人名排序）
3. 数据元素个数 n 较大（擅长：给十亿人的身份证号排序）

举例其用法如下图所示：

对基数排序算法性能分析如下： 时间效率： 共需进行 d 趟的分配与收集，每趟分配需遍历 n 个元素，所需时间为 O(n)；每趟收集需处理 r 个队列，所需时间为 O(r)。总时间复杂度为 O(d(n+r))。他与序列的初始状态无关。 空间效率： 一趟需要辅助空间为 r (r 个队列：r 个队头指针，r 个队尾指针)，这些结构可重复使用，空间复杂度为 O(r)。 稳定性： 当然是稳定的。 适用性： 适用于顺序存储和链式存储的线性表，尤其适合链式结构。

8.7 计数排序（Counting Sort）

计数排序并不在统考大纲范围内，但是其排序思想在历年真题中多次提及。 一图胜千言，计数排序思路如下图所示： 注意其待排序元素必须为整数，一定要确定正确的待排序元素范围以构造辅助数组。 实现代码如下：

// 计数排序
void CountSort(int A[], int B[], int n, int k) {
    int i, C[k];          // 辅助数组C的长度取决于待排序元素取值范围[0, k)
    for (i = 0; i < k; i++)  // 初始化计数数组
        C[i] = 0;

    for (i = 0; i < n; i++)  // Step1：遍历待排序数组，统计每个关键字的出现次数
        C[A[i]]++;

    for (i = 1; i < k; i++)  // Step2：再次处理辅助数组，统计不大于 i 的元素个数
        C[i] = C[i] + C[i - 1];  // C[i] 保存的是小于或等于 i 的元素个数

    for (i = n - 1; i >= 0; i--) {  // Step3：利用辅助数组C实现计数排序（从后往前处理）
        C[A[i]] = C[A[i]] - 1;
        B[C[A[i]]] = A[i];  // 将元素 A[i] 放在输出数组 B[] 的正确位置上
    }
}

对计数排序的性能分析如下：

• 空间效率： 计数排序是一种以空间换取时间的算法。输出数组 B 的长度为 n；计数数组 C 的长度为 k，空间复杂度为 O (n+k)。若不将输出数组视为辅助空间，则空间复杂度为 O (k)。算法要求待排序元素为非负整数，取值范围（如 0~k-1）不宜过大，否则会导致辅助空间浪费。
• 时间效率： 上述代码的第 1 和第 3 个 for 循环耗时 O (k)，第 2 和第 4 个 for 循环耗时 O (n)，总时间复杂度为 O (n+k)。因此，当 k=O (n) 时，计数排序可达线性时间 O (n)；但当 k≫n 时，其效率反而不如基于比较的排序算法（如快速排序、归并排序、堆排序等）。
• 稳定性： 上述代码的第 4 个 for 循环从后往前遍历输入数组，相同元素在输出数组中的相对次序得以保持，因此计数排序是稳定的排序算法。
• 适用性： 计数排序适用于顺序存储的线性表。

8.8 外部排序

8.8.1 外部排序的概念

在许多应用中，常需对大规模文件进行排序，无法一次性装入内存，需在内存与外存之间多次交换数据，逐步完成整体排序，这种内外存协同操作的排序算法，称为外部排序。

8.8.2 外部排序的方法

外部排序的时候，常采用的就是归并排序的策略，包含两个阶段：

1. 生成初始归并段： 即将外存上的每个磁盘块都分别放入内存进行内部排序，再放回外存，变成有序的磁盘块。
2. 多路归并： 即对于这些初始归并段进行逐趟的多路归并，每趟将多个有序段合并成更长的有序段，最终得到整个有序文件。

采用 2 路归并的外部排序过程如图所示： 将内存工作区划分为 两个输入缓冲区 + 一个输出缓冲区，大小都等于单个磁盘块。 接下来以上述例子为例分析外部排序的时间开销： 外部排序的时间代价主要取决于访问磁盘的次数，即 I/O 次数。 如图所示： 显然，若想优化时间开销，只需要增大归并路数以有效减少归并趟数，从而显著降低总的磁盘 I / O 次数，（增大归并路数需增加输入缓冲区个数,那在开始的时候也能用来生成更长的初始归并段，以减少初始归并段数量） 如图所示：

8.8.3 败者树

上一小节中提到的归并路数 K 会每挑选一个关键字比对（k-1）次，那么如何减少关键字比对次数？接下来即引出败者树的概念。 有了败者树，对于 k 路归并，后续每个新元素比较次数不超过败者树的高度，即 （向上取整）⌈log₂k⌉ 次。 关于败者树的实现也很简单，使用一个数组就行。如下图所示：

8.8.4 置换-选择排序

置换-选择排序可构造更长的初始归并段，以减少初始归并段数量。 要想增大初始归并段长度，普通生成初始归并段方法需要增加内存开销（增加输入缓冲区个数）。而置换选择排序生成初始段方法不会增大内存开销。

• 普通内部排序生成初始段： 读 N 次 → 排序 → 写 N 次
• 置换-选择排序生成初始段： 读 N 次 → 边读边选 → 写 N 次

示意图如图所示，注意下图省略了输出缓冲区，实际上从磁盘读入输入缓冲区和从输出缓冲区输出到磁盘，都是以磁盘块为单位。

8.8.5 最佳归并树

当采用置换-选择排序使各初始归并段的长度发生了变化，那么不同的归并次序对应的不同读写磁盘的次数。如何确定在归并过程中的最小读写磁盘次数？我们将归并过程画出一棵归并树后发现，读写磁盘次数=树的带权路径长度（WPL）* 2，如图所示： 当然我们自然而然的能想到，要使磁盘 I/O 次数最少，就去求哈夫曼树（又称最优二叉树，对于三路归并，叫做三叉哈夫曼树，以此类推）。 哈夫曼树的求法在《数据结构之树与二叉树》5.6 小节提及，链接末尾。 问题随之而来。求多叉哈夫曼树的时候会出现问题，如下图所示： 对于初始归并段数量无法满足构成严格的 K 叉归并树的情况，我们需要补充虚段。 具体如何补充，补充规则是什么，如下图所示：

附言

一个神奇的学习网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 《考研视角下的 C 语言(下)》： https://editor.csdn.net/md/?articleId=157323908 《数据结构之树与二叉树》: https://editor.csdn.net/md/?articleId=158236398