【数据结构】考研真题攻克与重点知识点剖析 - 第 8 篇:排序

2024-04-09 15:52

本文主要是介绍【数据结构】考研真题攻克与重点知识点剖析 - 第 8 篇:排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

  • 本文基础知识部分来自于b站:分享笔记的好人儿的思维导图与王道考研课程,感谢大佬的开源精神,习题来自老师划的重点以及考研真题。
  • 此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析,本人技术有限,最终数据清洗结果不够理想,相关CSDN文章便没有发出。

(考研真题待更新)

欢迎订阅专栏:408直通车

请注意,本文中的部分内容来自网络搜集和个人实践,如有任何错误,请随时向我们提出批评和指正。本文仅供学习和交流使用,不涉及任何商业目的。如果因本文内容引发版权或侵权问题,请通过私信告知我们,我们将立即予以删除。

文章目录

  • 前言
  • 第八章 排序
    • 概述
      • 排序
      • 算法的稳定性
      • 根据数据是否在内存中进行分类
        • 小结
    • 插入排序
      • 直接插入排序
      • 折半插入排序
        • 小结
      • 希尔排序
        • 小结
    • 交换排序
      • 概述
      • 冒泡排序
        • 小结
      • 快速排序
    • 选择排序
      • 概述
      • 简单选择排序
        • 小结
      • 堆排序
        • 小结
      • 堆的插入删除
        • 插入
        • 删除
    • 二路归并排序
      • 实现过程
    • 基数排序
      • 基本概念
      • 实现过程
      • 性能分析
      • 稳定性
      • 应用
      • 补充
    • 排序算法的分析
      • 结论
    • 外部排序
      • 外部排序基本概念
        • 构造初始“归并段"
        • 第一趟归并
        • 第二趟归并
        • 第三趟归并
      • 外部排序的方法
      • 优化(都减少归并趟数s,减少磁盘读写次数)
      • 多路平衡归并与败者树
      • 置换-选择排序(生成初始归并段)
      • 最佳归并树(k叉哈夫曼树)
    • 代码
      • 快排
      • 归并
      • 二分查找(可用于折半)

第八章 排序

概述

排序

  • 将无序序列排成一个有序序列的运算(如果排序的数据结点包含多个数据域,排序针对一个域)
    在这里插入图片描述

算法的稳定性

  • 能够使任何数值相等的元素,排序以后相对次序不变

  • 稳定性只对结构类型数据排序有意义,例:先按数学成绩排序,再按总分排序
    在这里插入图片描述

根据数据是否在内存中进行分类

  • 内部排序

    • 在排序期间元素全部存放在内存中的排序
  • 外部排序

    • 在排序期间元素无法全部同时存放在内存中,必须在排序的过程中根据要求不断地在内、外存之间移动的排序
      在这里插入图片描述
小结

在这里插入图片描述

插入排序

直接插入排序

  • 概念

    • 首先以一个元素为有序的序列,然后讲后面的元素依次插入到有序的序列中适合的位置直到所有元素都插入有序序列在这里插入图片描述
  • 实现过程

    • 在这里插入图片描述

      • 排序某时刻将待排序表分割为三部分,顺序查出L(i)在L[1…i-1]的插入位置k

      • 将L[k…i-1]中的所有元素依次后移一个位置,将L(i)复制到L(k)

    • 哨兵

      • 在这里插入图片描述
        在这里插入图片描述
  • 性能分析在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    • 时间复杂度(平均):O(n^2)

      • 最好(有序):O(n)

        • 最坏(逆序):O(n^2)
    • 空间复杂度:O(1)

  • 稳定性

    • 稳定
  • 补充提高速度

    • 减少元素比较次数,引入折半插入排序

    • 减少元素的移动次数,引入希尔排序,每次移动步幅增大

折半插入排序

在这里插入图片描述

  • 实现过程

    • 首先确定折半插入排序的范围,利用折半查找找到插入的位置,然后一次性对数据进行移动,最后插入该元素
  • 性能分析

    • 时间复杂度:比较次数减少O(nlogn),移动次数不变,整体O(n^2)

    • 空间复杂度:O(1)

  • 稳定性

    • 稳定

在这里插入图片描述

小结

在这里插入图片描述

希尔排序

在这里插入图片描述

  • 概念

    • 本质上还是插入排序,只是把待排序列分成几个子序列,分别对子序列进行直接插入排序
  • 实现过程

    • 先取一个小于n的步长d,把表中数据分为d组,所有距离为d的倍数记录在同一组,组内进行直接插入排序

    • 缩小步长d,不断重复直到d=1为止

    • 若d=5,跨越6个数在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述

  • 性能分析在这里插入图片描述

    • 时间复杂度(平均):O(n^1.3)

      • 最坏:O(n^2)
    • 空间复杂度:O(1)

  • 稳定性

    • 不稳定
      在这里插入图片描述
小结

在这里插入图片描述

交换排序

概述

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

冒泡排序

在这里插入图片描述

  • 实现过程

    • 从前往后(从后往前)两两比较相邻元素的值,若逆序则交换,直到序列比较完

    • 每一趟会将最大的元素交换到待排序列最后一个位置(将较小的元素交换到待排序列第一个位置)

    • 进行下一趟排序,前一趟确定元素不参与

    • 如果某一趟排序过程中未发生交换,则可以提前结束

  • 性能分析在这里插入图片描述

    • 时间复杂度(平均):O(n^2)

      • 最好:O(n)

        • 最坏:O(n^2)
    • 空间复杂度:O(1)

  • 稳定性

    • 稳定
  • 补充

    • 冒泡排序产生的有序子序列一定全局有序,即每趟会将一个元素放到最终的位置上
      在这里插入图片描述
小结

在这里插入图片描述

快速排序

  • 实现过程

    • 首先选取一个元素作为枢轴,以枢轴为界将排序表分为两个部分,左边小于枢轴,右边大于枢轴

    • 然后对着两部分分别递归重复上述步骤,直到每个部分内只有一个元素或空为止
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述

  • 性能分析

    • 时间复杂度

      • 快速排序的运行时间与划分是否对称有关,应尽量选取可以将数据中分的枢轴元素(想象一颗二叉树)

      • 最好情况:待排序列越无序,算法效率越高:O(nlog2n)

      • 最坏情况:待排序列越有序,算法效率越高:O(n^2)

      • 平均情况:快速排序平均情况下与最优情况下运行时间很接近,是所有内部排序算法中平均时间最优的排序算法
        在这里插入图片描述

    • 空间复杂度(平均):O(log2n)在这里插入图片描述
      在这里插入图片描述

      • 最好:O(log2n)

        • 最坏:O(n)
  • 稳定性

    • 不稳定
  • 优化:划分均匀

    • 选头中尾三个位置的元素,取中间值为枢轴元素

    • 随机选一个元素作为枢轴元素

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述在这里插入图片描述

在这里插入图片描述

选择排序

概述

  • 每一趟(如第i躺)在后面n-i+1(i=1,2,…,n-1)个待排序元素中选取关键字最小的元素,作为有序子序列的第i个元素,直到第n-1趟完成

  • 选择排序的时间性能不随记录序列中关键字的分布而改变

简单选择排序

在这里插入图片描述

  • 实现过程

    • 假设排序表为L[1…n],第i躺排序,即从L[1…n]中选择关键字最小的元素与L(i)交换

    • i每次增加,每趟排序可以确定一个元素的最终位置
      在这里插入图片描述

  • 性能分析

    • 时间复杂度:O(n^2)

    • 空间复杂度:O(1)
      在这里插入图片描述

  • 稳定性

    • 不稳定
      在这里插入图片描述
小结

在这里插入图片描述

堆排序

  • 基本概念
    在这里插入图片描述

      • 堆是一棵完全二叉树,而且满足任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值
    • 大根堆在这里插入图片描述

      • 每个结点的值都不小于它的左右孩子结点的值
    • 小根堆在这里插入图片描述

      • 每个结点的值都不大于它的左右孩子结点的值
        在这里插入图片描述
  • 实现过程

    • 建大(小)根堆:O(n)在这里插入图片描述

      • 从后向前调整所有非终端结点,使其满足堆的性质[0, ⌊n/2⌋]

      • 检查是否根大于(小于)等于左右孩子,小(大)元素不断下坠(下坠过程需不断检查与左右孩子的大小)在这里插入图片描述

    • 调整大(小)根堆:O(nlog2n)

      • 将最大(小)根结点与最后一个结点互换

      • 按建堆过程调整结点在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
        在这里插入图片描述
        在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
        在这里插入图片描述在这里插入图片描述在这里插入图片描述

  • 性能分析在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    • 时间复杂度:O(nlog2n)

    • 空间复杂度:O(1)

  • 稳定性在这里插入图片描述在这里插入图片描述

    • 不稳定
小结

在这里插入图片描述

在这里插入图片描述

堆的插入删除

插入

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

删除

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

在这里插入图片描述在这里插入图片描述
在这里插入图片描述

二路归并排序

在这里插入图片描述在这里插入图片描述

在这里插入图片描述在这里插入图片描述
在这里插入图片描述

实现过程

  • 假定待排序表有n个记录,可以看成n个有序子表,每个子表长度1,两两归并,得到⌈n/2⌉个长度为2或1的有序表,再两两归并,直到合并为长度n的有序表

  • 在这里插入图片描述
    在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    • 性能分析在这里插入图片描述

      • 时间复杂度:O(nlog2n)

      • 空间复杂度:O(n)

    • 稳定性

      • 稳定
    • 特点

      • 比较次数与初始状态无关

      • 只有归并排序O(nlog2n)且稳定
        在这里插入图片描述

基数排序

基本概念

  • 最高位优先(MSD)法:按关键字位权重递减依次逐层划分成若干更小的子序列,最后将所有子序列依次连接成一个有序序列

  • 最低位优先(LSD)法:按关键字位权重递增依次进行排序,最后形成一个有序序列

实现过程

  • 采用多关键字排序思想(即基于关键字各位的大小进行排序的),借助“分配”和“收集”两种操作对单逻辑关键字进行排序,直到所有关键字均已排序完毕
    在这里插入图片描述

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述

性能分析

在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述

  • 时间复杂度

    • 基数排序需要进行k躺分配和收集,一趟分配需要O(n),一趟收集需要O(m),所以时间复杂度为O(k(n+m))
  • 空间复杂度

    • 链式存储(王道):O(m),一趟需要辅助存储空间m(m个桶的头尾指针)

    • 顺序存储:O(n+m),桶+临时存放数组

稳定性

  • 稳定
    在这里插入图片描述

应用

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

  • 关键字便于分k组,即k较小时

  • 每组关键字取值范围不大,即m较少时

  • 元素个数n较大时

补充

  • 对数字排序时,仅能使用最低位优先法,若高位优先,最后排低位时会打乱顺序

排序算法的分析

  • 在这里插入图片描述

  • 王道书中基数排序,d为待排元素的维度,r为基数的个数,空间复杂度王道采用链式存储,故额外空间仅每个桶的头尾指针

结论

  • 若文件初始状态接近有序,则选用直接排序或冒泡排序为宜

  • 要求排序稳定且时间复杂度O(nlog2n),则选用归并排序

  • 若n很大,记录关键字位数较少且可分解时,采用基数排序

  • 当记录信息量较大,为避免消耗大量时间移动记录,可用链表作为存储结构

  • 简单选择排序、堆排序、归并排序的时间性能不随记录序列中关键字的分布而改变

外部排序

在这里插入图片描述

外部排序基本概念

在这里插入图片描述

构造初始“归并段"

在这里插入图片描述在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

第一趟归并

在这里插入图片描述

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

第二趟归并

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

第三趟归并

在这里插入图片描述在这里插入图片描述

  • 对大文件进行排序,因为文件中的记录很多、信息量庞大,无法将整个文件复制到内存进行排序

  • 需要将待排序的记录存储在外存上,排序时再把数据一部分一部分地调入内存进行排序,在排序过程中需要多次进行内存和外存的交换

外部排序的方法

  • 基本概念

    • 文件通常是按块存储在磁盘上的,操作系统也按块读写

    • 外部排序过程中的时间代价主要考虑访存次数(I/O次数)

  • 步骤(采用归并排序)

    • 生成r个初始归并段(内部排序)

      • 根据内存缓冲区大小,将外存文件分为r个子文件,依次读入内存并利用内部排序方法进行排序,并将内部有序的子文件重新写回外存
    • 进行s躺k路归并

      • s = ⌈logk r⌉

      • k路归并

        • 将k个归并段的块读入k个输入缓冲区

        • 用归并排序从k个归并段中选出几个最小记录暂存到输出缓冲区中

        • 当输出缓冲区满时,写出外存

        • 性质

          • 每趟归并中,最多只有k个段归并为一个

          • 若总共有m个归并段参与,s趟归并后,得⌈m/k⌉新归并段

          • 若要进行k路归并排序,内存需要1个输出缓冲区 + k个输入

  • 时间开销

    • 读写外存时间+内部排序所需时间+内部归并所需时间
      在这里插入图片描述

优化(都减少归并趟数s,减少磁盘读写次数)

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述

在这里插入图片描述在这里插入图片描述在这里插入图片描述

  • 增大归并路数k,进行多路平衡归并

    • 代价1:需要增加相应的输入缓冲区

    • 代价2:每次从k个归并段中选一个最小元素需要(k-1)次关键字比较

  • 减少初始归并段个数r

在这里插入图片描述在这里插入图片描述在这里插入图片描述

多路平衡归并与败者树

  • 在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述

    • 引入

      • 为了减少优化1代价2,减少每次k个归并段找最小关键字的比较次数
    • 思想

      • k个叶结点分布存放k个归并段在归并过程中当前参加比较的记录,非叶结点用了记忆左右子树中“失败者”(记录段号),让胜者往上继续进行比较,直到根结点
    • 性能

      • k路归并的败者树深度⌈log2 k⌉

      • 总的比较次数由(n-1)(k-1)减少到(n-1)⌈log2 k⌉

    • 注意:归并路数k过大时,虽然趟数减少,但读写外存次数仍会增加

置换-选择排序(生成初始归并段)

在这里插入图片描述

  • 在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    • 引入

      • 即优化2:减少初始归并段数量r
    • 实现:如图红字

在这里插入图片描述

在这里插入图片描述

最佳归并树(k叉哈夫曼树)

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述

  • 引入

    • 为减少磁盘I/O次数(归并段读入读出,合并先后次序)
  • 结构概述

    • 叶结点表示初始归并段,权值表示该归并段的长度;非叶结点代表归并形成的新归并段

    • 叶结点到根的路径长度表示其参加归并的趟数

    • 归并树的带权路径长度WPL为归并过程中的总读记录数

    • 归并过程中的磁盘I/O次数 = 归并树的WPL * 2

    • 构造

      • 补充虚段

        • 若(初始归并段数量-1) % (k-1) = 0,说明刚好可以构成严格k叉树,此时无需添加虚段

        • 若(初始归并段数量-1) % (k-1) = u != 0,则需要补充(k-1) - u个虚段

      • 构造k叉哈夫曼树

        • 每次选择k个根结点权值最小的树合并,并将k个根结点的权值之和作为新的根结点的权值

代码

快排

  • 思路:基于分治思想
  1. 确定分界点(取左边界,去中间点,随机取)

  2. 调整区间,分<x与>x两部分分别是[l, j]、[j+1, r]

  3. 递归左右

    •   void quick_sort(vector<int>&q, int l, int r){if (l >= r) return;                                        //注意这里是>=int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){while (q[++i] < x);                                  //注意这里无论结果如何i都会+1,故初始化时i=l-1,且才能跳出循环while (q[--j] > x);if (i < j) swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j + 1, r);}
      

归并

  • 思路:基于分治思想
  1. 确定分界点: 中间点 mid=l+r>>1

  2. 递归分界点左右

  3. 归并

    •   void merge_sort(int q[], int l, int r){if (l >= r) return;                                                           //return边界int mid = l + r >> 1;merge_sort(q, l, mid);                                                    //排序左半merge_sort(q, mid + 1, r);                                             //排序右半int k = 0, i = l, j = mid + 1;                                          //将i,j分别指向两数组第一个元素while (i <= mid && j <= r)                                         //若两数组都没结束,选小的进if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else tmp[k ++ ] = q[j ++ ];while (i <= mid) tmp[k ++ ] = q[i ++ ];                     //一数组结束,另外一数组剩下元素依次进while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];}
      

二分查找(可用于折半)

  • 本质:可以划分为满足某种性质与不满足某种性质的两个区间,用二分法可以找到两区间边界的左右两个点。

    •   int bsearch_1(int l, int r)                     //寻找右边界{while (l < r){int mid = l + r + 1 >> 1;           //右边界需+1if (q[mid]>k) r = mid-1;             //mid不满足<=,直接将右边界置mid左边else l = mid;                               //左边界一点点贴近右边界}return l;}int bsearch_2(int l, int r)                   //寻找左边界,同理{while (l < r){int mid = l + r >> 1;if (q[mid]<k) l = mid+1;else r = mid;}return l;}
      

这篇关于【数据结构】考研真题攻克与重点知识点剖析 - 第 8 篇:排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/888577

相关文章

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

前端知识点之Javascript选择输入框confirm用法

《前端知识点之Javascript选择输入框confirm用法》:本文主要介绍JavaScript中的confirm方法的基本用法、功能特点、注意事项及常见用途,文中通过代码介绍的非常详细,对大家... 目录1. 基本用法2. 功能特点①阻塞行为:confirm 对话框会阻塞脚本的执行,直到用户作出选择。②

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

基本知识点

1、c++的输入加上ios::sync_with_stdio(false);  等价于 c的输入,读取速度会加快(但是在字符串的题里面和容易出现问题) 2、lower_bound()和upper_bound() iterator lower_bound( const key_type &key ): 返回一个迭代器,指向键值>= key的第一个元素。 iterator upper_bou

三国地理揭秘:为何北伐之路如此艰难,为何诸葛亮无法攻克陇右小城?

俗话说:天时不如地利,不是随便说说,诸葛亮六出祁山,连关中陇右的几座小城都攻不下来,行军山高路险,无法携带和建造攻城器械,是最难的,所以在汉中,无论从哪一方进攻,防守方都是一夫当关,万夫莫开;再加上千里运粮,根本不需要打,司马懿只需要坚守城池拼消耗就能不战而屈人之兵。 另一边,洛阳的虎牢关,一旦突破,洛阳就无险可守,这样的进军路线,才是顺势而为的用兵之道。 读历史的时候我们常常看到某一方势