软考学习 数据结构 排序

2024-09-07 10:12

本文主要是介绍软考学习 数据结构 排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 冒泡排序(Bubble Sort)

基本原理:
  • 冒泡排序是一种简单的交换排序算法,它通过重复地遍历要排序的数列,依次比较相邻的两个元素,并在顺序错误时交换它们的位置。每一轮遍历后,最大的元素会“冒泡”到数列的末尾,因此称为冒泡排序。这个过程不断重复,直到整个序列有序为止
  • 初始状态:从序列的第一个元素开始,依次比较相邻的两个元素。
  • 元素比较与交换
    • 如果前一个元素大于后一个元素,则交换它们的位置。
    • 否则,保持原位,不做交换。
  • 冒泡
    • 每一轮比较结束后,当前轮次最大的元素会被交换到数列的末尾,这个元素不再参与下一轮的比较。
  • 重复
    • 不断缩小比较的范围(不包含已经冒泡到末尾的元素),重复上述过程,直到整个序列有序。
时间复杂度:
  • 最坏情况:O(n2)
  • 平均情况:O(n2)
  • 最优情况:当输入已经有序时,时间复杂度为 O(n)
优缺点:
  • 优点:实现简单,代码容易理解。
  • 缺点:效率低,尤其对于大规模数据集不适用。

2. 选择排序(Selection Sort)

基本原理:
  • 选择排序每次从未排序部分中选出最小(或最大)的元素,放到已排序部分的末尾。这个过程不断进行,直到所有元素都已排序。
时间复杂度:
  • 最坏情况:O(n2)
  • 平均情况:O(n2)
  • 最优情况:O(n2)(即使输入有序,选择排序仍需要遍历整个序列)
优缺点:
  • 优点:交换次数较少,相对适合交换代价高的情况。
  • 缺点:整体效率较低,不适用于大规模数据集。

3. 插入排序(Insertion Sort)

基本原理:
  • 插入排序通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到合适位置并插入。
时间复杂度:
  • 最坏情况:O(n2)
  • 平均情况:O(n2)
  • 最优情况:当输入有序时,时间复杂度为 O(n)
优缺点:
  • 优点:对于几乎有序的数据非常高效,且是一种稳定的排序算法。
  • 缺点:对于大规模数据,效率较低。

4. 希尔排序(Shell Sort)

基本原理:
  • 希尔排序,也称递减增量排序,是插入排序的一种改进版本。它通过将整个序列按一定的“增量”分组,对每组内的元素进行插入排序,然后逐步减小增量,最后当增量为1时,对整个序列进行一次标准的插入排序。这种分组的过程使得数据在初期的插入排序时可以大幅度移动,从而减少了后期插入排序的总移动次数,提高了整体效率。

    希尔排序的核心思想是通过多次插入排序的过程,使数据逐步接近有序状态,从而在最后一轮增量为1的插入排序中发挥出最佳性能。

具体步骤
  1. 选择增量序列:选择一个初始的增量 ddd,通常从序列长度的一半开始,如 d=⌊n/2⌋d = \lfloor n/2 \rfloord=⌊n/2⌋。
  2. 分组排序:将序列中的元素根据增量 ddd 进行分组,每组元素按位置间隔为 ddd 进行插入排序。
  3. 缩小增量:将增量缩小(通常为之前的一半,如 d=⌊d/2⌋d = \lfloor d/2 \rfloord=⌊d/2⌋),重复步骤2,直到增量为1时进行最后一轮插入排序。
时间复杂度
  • 最坏情况:最坏情况下时间复杂度与增量序列的选择有关,但通常认为接近 O(n2)O(n^2)O(n2)。
  • 平均情况:希尔排序的平均时间复杂度较为复杂,通常介于 O(n1.3)O(n^{1.3})O(n1.3) 和 O(n1.5)O(n^{1.5})O(n1.5) 之间,具体取决于增量序列的选择。
  • 最优情况:当数据初始接近有序时,希尔排序的时间复杂度可以接近 O(nlog⁡n)O(n \log n)O(nlogn)。
增量序列的选择

增量序列的选择对希尔排序的性能有很大影响。常见的增量序列有:

  • 简单的二分法:如 d=⌊n/2⌋,⌊n/4⌋,…,1d ,⌊n/4⌋,…,1。
  • Hibbard增量
  • Sedgewick增量

增量序列的选择是影响希尔排序性能的关键因素。理论上,Sedgewick增量被认为是较好的选择,因为它能够在更广泛的情况下提供优良的性能。

优点

  • 高效性:比直接插入排序效率高,特别是对于较大规模的数据集合,希尔排序的性能显著优于插入排序。
  • 灵活性:通过选择不同的增量序列,希尔排序可以适应不同的应用场景。
  • 空间效率高:希尔排序是一种原地排序算法,所需的额外空间非常少,空间复杂度为 O(1)。

缺点

  • 不稳定:希尔排序并不是稳定的排序算法,因为同样大小的元素可能会因为间隔分组被放置到不同的位置,从而改变它们的相对顺序。
  • 复杂性:增量序列的选择对排序效率影响很大,不同的增量序列可能导致不同的性能表现,因此算法实现和优化较为复杂。

5. 归并排序(Merge Sort)

基本原理:
  • 归并排序是一种基于分治法(Divide and Conquer)的排序算法。它将一个大的问题分解成若干个小问题,分别解决这些小问题,然后合并解决结果。具体到排序问题上,归并排序将序列递归地分成两半,直到每部分的长度为1,然后再将这些部分逐层合并,最终形成一个有序的序列。
时间复杂度:
  • 最坏情况:O(nlog⁡n)
  • 平均情况:O(nlog⁡n)
  • 最优情况:O(nlog⁡n)
优缺点:
  • 优点:稳定的排序算法,适用于处理大规模数据,尤其是数据量较大的链表排序。
  • 缺点:需要额外的 O(n)空间来存储中间结果。

6. 快速排序(Quick Sort)

基本原理:
  • 快速排序也是一种分治算法。它通过选择一个基准元素,将数据分为两部分,使得左边部分所有元素都小于基准元素,右边部分所有元素都大于基准元素,然后递归地对两部分进行排序。
时间复杂度:
  • 最坏情况:O(n2)(当每次选到的基准都是当前最小或最大元素时)
  • 平均情况:O(nlog⁡n)
  • 最优情况:O(nlog⁡n)
优缺点:
  • 优点:平均性能非常好,常常比其他 O(nlog⁡n)的算法更快,且就地排序无需额外空间。
  • 缺点:不稳定,最坏情况下效率较低。

7. 堆排序(Heap Sort)

基本原理:

具体步骤

  • 堆排序是一种基于这种数据结构的比较排序算法。堆是一棵完全二叉树,其中每个节点的值都大于或等于(大顶堆)或小于或等于(小顶堆)其子节点的值。堆排序通过将数组构造成一个堆,并反复将堆顶元素(最大或最小值)与堆的最后一个元素交换,逐步缩小堆的范围来完成排序。

    堆排序主要分为两个步骤:

  • 构建初始堆:将无序数组构造成一个堆。
  • 排序:反复将堆顶元素(最大或最小值)与堆的最后一个元素交换,然后将剩下的元素重新调整为堆,直到所有元素都被排序。
  • 构建堆

    • 对于一个长度为 n 的数组,初始堆的构建是从最后一个非叶子节点开始,向前遍历并调整各个子树为堆。
    • 具体做法是从下到上、从右到左调整每个节点为根的子树为堆。
  • 堆排序

    • 每次将堆顶元素(即堆中的最大值或最小值)与最后一个元素交换,缩小堆的范围,并调整剩下的元素重新成为堆。
    • 重复此过程,直到整个数组有序。
时间复杂度:
  • 最坏情况:O(nlog⁡n)
  • 平均情况:O(nlog⁡n)
  • 最优情况:O(nlog⁡n)
优缺点:
  • 优点:性能良好,不受输入数据特性影响,且不需要额外的存储空间(与归并排序相比)。
  • 缺点:不稳定,且相比快速排序,实际应用中的常数因子稍大。

8. 计数排序(Counting Sort)

基本原理:
  • 计数排序是一种非比较排序算法。它适用于数据范围有限的情况,通过统计每个元素出现的次数来确定它们在排序后的序列中的位置。
时间复杂度:
  • 最坏情况:O(n+k),其中 k是数据范围
  • 平均情况:O(n+k)
  • 最优情况:O(n+k)
优缺点:
  • 优点:效率高,适用于范围有限的整数排序。
  • 缺点:受限于数据范围,且需要额外空间存储计数结果,空间复杂度为 O(k)O(k)O(k)。

9. 桶排序(Bucket Sort)

基本原理:
  • 桶排序将数据分配到有限数量的桶中,分别对每个桶内的数据进行排序(通常使用插入排序或其他排序算法),然后依次合并桶中的数据得到最终排序结果。
时间复杂度:
  • 最坏情况:O(n2)
  • 平均情况:O(n+k),其中 k 是桶的数量
  • 最优情况:O(n+k)
优缺点:
  • 优点:在数据均匀分布的情况下非常高效,特别适用于外部排序和浮点数排序。
  • 缺点:需要对数据的分布有所了解,且需要额外的空间来存储桶。

9. 基数排序(Radix Sort)

基本原理:
  • 基数排序是一种非比较排序算法,按位对数据进行排序,通常从最低位到最高位(或相反顺序),通过稳定的排序算法(如计数排序)依次对各位排序,最终得到有序序列。
时间复杂度:
  • 最坏情况:O(n⋅d),其中 d 是位数
  • 平均情况:O(n⋅d)
  • 最优情况:O(n⋅d)
优缺点:
  • 优点:适用于整数排序,效率较高,尤其是在位数较小的情况下。
  • 缺点:受限于数据的位数,且需要额外的空间来进行多轮排序。
排序方法时间复杂度辅助空间稳定性
直接插入O(n^2)O(1)稳定
简单选择O(n^2)O(1)不稳定
冒泡排序O(n^2)O(1)稳定
希尔排序O(n^1.3)O(1)不稳定
快速排序O(nlogn)O(nlogn)不稳定
堆排序O(nlogn)O(1)不稳定
归并排序O(nlogn)O(n)稳定
基数排序O(d(n+rd))O(rd)稳定

这篇关于软考学习 数据结构 排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同