详解排序几大算法

一、插入排序

基本思想:

  • 直接插入排序是一种简单的插入排序算法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。

步骤:

当插入第n个元素的时候前面的arr[0]到arr[n-1]都已经排序好了,此时我们将arr[n]与前面的相比较,假设我们需要一个升序的数组,那当arr[n]小于所比较的这个数的时候,就跟其交换位置,原来位置上的元素顺序后移。

动图演示:
在这里插入图片描述
代码实现:

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){//记录最后一个元素的下标int end = i ;//待排序的数据int tmp = a[end + 1];while (end >= 0){//比插入的数大就往后if (a[end] > tmp){a[end + 1] = a[end];end--;}//比插入的数小就跳出循环else{break;}}a[end + 1] = tmp;}
}

直接插入排序的特性:

  • 元素集合越接近有序,直接插入排序算法的时间效率就越高
  • 时间复杂度:O(N^2)
  • 空间复杂度:O(1)

二、希尔排序

基本思想:

  • 先选定一个整数(通常是gap = n/3+1),把待排序文件所有记录成各组,所有的距离相等的记录在同一组内,并对每一组内的记录进行排序,然后gap = gap/3+1得到下一个整数,再将数组分成各组,进行插入排序,当gap = 1时,将相当于直接插入排序。
  • 所有我们会发现希尔排序是直接插入算法的基础上进行改进而来,但是它的效率要高于直接插入排序。
    在这里插入图片描述

动图演示:
在这里插入图片描述

希尔排序的特性:

  • 希尔排序是对直接排序的优化
  • 当gap > 1时都时预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了。

代码实现:

void ShellSort(int* a, int n)
{int gap = n;while (gap>1){gap = gap / 3 + 1;//单趟排序for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

希尔排序的时间复杂度:O(n^3/2)
希尔排序的空间复杂度:O(1)

三、选择排序

基本思想:
每次从待排序的数据元素中选最小(或者最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

直接选择排序步骤:

  1. 在元素集合 array[i]–array[n-1] 中选择关键码最⼤(小)的数据元素
  2. 若它不是这组元素中的最后⼀个(第⼀个)元素,则将它与这组元素中的最后⼀个(第⼀个)元素交换
  3. 在剩余的 array[i]–array[n-2](array[i+1]–array[n-1]) 集合中,重复上述步骤,直到集合剩余 1 个元素

动图演示:
在这里插入图片描述
代码实现:

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}if (begin == maxi){maxi = mini;}swap(&a[mini], &a[begin]);swap(&a[maxi], &a[end]);++begin;--end;}
}

直接选择排序的时间复杂度:O(N^2)
直接选择排序的空间复杂度:O(1)

四、堆排序

堆排序是指利用堆积树这种数据结构所设计的一种排序算法,它是选择排序的一种。
我们需要注意的是排升序要建大堆,排降序建小堆。
点这里在二叉树里面实现了堆排序

五、冒泡排序

动图演示:
在这里插入图片描述
代码实现:

//冒泡排序
void BubbleSort(int* arr, int n)
{int end = n;while (end){int flag = 0;for (int i = 1; i < end; ++i){if (arr[i - 1] > arr[i]){int tmp = arr[i];arr[i] = arr[i - 1];arr[i - 1] = tmp;flag = 1;}}if (flag == 0){break;}--end;}
}

冒泡排序的时间复杂度:O(N^2)
冒泡排序的空间复杂度:O(1)

六、快速排序

基本思想:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

hoare版本

算法思想:
1.创建左右指针,确定基准值
2.从右向左找出比基准值小的数据,从左往右找出比基准值大的数据,左右指针数据交换,进入下一次循环

步骤:

我们选定一个key(一般是最右边的数,或者最左边的数)接着我们需要定义一个begin和一个end,begin是从左往右走,end是右往左走。在它们走的过程中,当begin遇到比key大的数据的时候停下来,end继续走,指导遇到一个小于key的数时,两者交换数据,最后直到它们相遇,相遇点的数据和key的数据交换。

动图演示:
在这里插入图片描述

void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int left = begin;int right = end;//选左边为keyint keyi = begin;while (begin < end){while (a[end] >= a[keyi] && begin < end){--end;}//左边选大while (a[begin] <= a[keyi] && begin < end){++begin;}//小的换到右边,大的换到左边swap(&a[begin], &a[end]);}swap(&a[keyi], &a[end]);keyi = end;QuickSort(a, left, keyi - 1);QuickSort(a,keyi + 1,right);
}

挖坑法

基本思路:
创建左右指针,首先从右往左找出比基准值小的数据,后将其放在左边坑中,当前的位置就变为新的坑,然后在从左往右找出比基准值大的数据,找到后将其放进右边坑中,当前位置变为新的坑,当结束循环的时候将最开始储存的分界值放进当前的坑中,返回当前坑的下标。

步骤:

选出一个数据(可以是最左也可以是最右,一般情况下)存放在key变量中,在这个数据位置形成一个坑,紧接着我们定义一个Left和一个Right,Left从左往右走,Right从右往左走。
需要注意的是如果最左边挖坑,则需要Right先走;反之,则Left先走。

动图演示:
在这里插入图片描述
代码实现:

void QuickSort1(int* a, int begin, int end)
{if (begin >= end){return;}int left = begin,right = end;int key = a[begin];while (begin < end){//找小while (a[end] >= key && begin < end){--end;}//小的放到左边的坑里a[begin] = a[end];//找大while (a[begin] <= key && begin < end){++begin;}//大的放到右边的坑里a[end] = a[begin];}a[begin] = key;int keyi = begin;QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);
}

lomuto前后指针

基本思路:
创建前后指针从左往右找比基准值小的进行交换,使得小的都排在基准值的左边。

步骤:

选出一个key,起始时prev指针指向序列开头,cur指针指向prev+1的位置。若cur指向的数据小于key,则prev先向后移动一位,然后将prev和cur指针指向的数据交换,cur++;若cur指向的数据大于key,则cur指向直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的数据交换即可。

在这里插入图片描述
代码实现:

void QuickSort2(int* arr, int begin, int end)
{if (begin >= end){return;}int cur = begin, prev = begin - 1;int keyi = end;while (cur != keyi){if (arr[cur] < arr[keyi] && ++prev != cur){swap(&arr[cur], &arr[prev]);}++cur;}swap(&arr[++prev],&arr[keyi]);keyi = prev;QuickSort2(arr, begin, keyi - 1);QuickSort2(arr, keyi + 1, end);}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/491013.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Unix 和 Windows 的有趣比较

Unix 和 Windows NT 比较 来源于这两本书&#xff0c;把两本书对照来读&#xff0c;发现很多有意思的地方&#xff1a; 《Unix 传奇》 https://book.douban.com/subject/35292726/ 《观止 微软创建NT和未来的夺命狂奔 》 Showstopper!: The Breakneck Race to Create Windows…

Android 系统应用重名install安装失败分析解决

Android 系统应用重名install安装失败分析解决 文章目录 Android 系统应用重名install安装失败分析解决一、前言1、Android Persistent apps 简单介绍 二、系统 persistent 应用直接安装需求分析解决1、系统应用安装报错返回的信息2、分析解决 三、其他1、persistent系统应用in…

【Unity基础】AudioSource 常用方法总结

在 Unity 中&#xff0c;AudioSource 组件用于控制音频的播放和管理。以下是常用的 AudioSource 控制方法及其说明。 1. 播放和暂停音频 Play()&#xff1a;开始播放音频&#xff0c;如果是从暂停的地方继续播放&#xff0c;可以直接调用。Pause()&#xff1a;暂停当前播放的…

【ADS射频电路学习笔记】2.阻抗匹配电路设计

本节课学习smith圆图匹配 1.史密斯圆图各功能介绍 首先调出s参数的控件 并增加两个端口 调出smith chart matching的控件 连接好端口在ADS中&#xff0c;默认是从负载端&#xff08;term2&#xff09;向源端&#xff08;term1&#xff09;做匹配的。 调节s参数控件的的频率扫…

01《Python数据分析》数据分析初探章节总结

目录 1 概述1.1 数据分析定义1.2 数据分析目标1.3 数据分析分类 2 数据分析方法3 数据分析流程4 寻找问题原因5 典型问题参考学习 1 概述 1.1 数据分析定义 数据分析1就是&#xff1a;用适当的统计分析方法对收集来的大量数据进行分析&#xff0c;提取有用信息和形成结论&…

杰理-LVGL-默认隐藏容器

杰理-LVGL-默认隐藏容器 lv_obj_add_flag(ui->screen_music_cont_tip, LV_OBJ_FLAG_HIDDEN)

软件需求概述(尊享版)

软件需求与软件分析 软件需求&#xff1a;用户角度&#xff0c;注重软件外在表现 软件分析&#xff1a;开发者角度&#xff0c;注重软件内部逻辑结构 面向对象分析模型 类/对象模型&#xff08;全部的类和对象&#xff09; 对象-关系模型&#xff08;对象之间的静态关系&…

将PDF流使用 canvas 绘制展示在页面上(一)

将PDF流展示在页面上 使用 pdfjs-dist 库来渲染 PDF 页面到 canvas 上进行绘制展示 安装 pdfjs-dist 依赖 npm install pdfjs-dist 或者 yarn add pdfjs-dist创建一个组件来处理 PDF 流的加载和渲染 该组件中是一个包含 PDF 文件的 Base64。 将 pdf 流传入该组件中使用 /** fo…

web遇到的安全漏洞

最近项目又在做安全漏扫&#xff0c;记录下遇到的常见的web安全问题 越权 漏洞介绍 攻击者可以在授权状态下&#xff0c;通过修改数据包的参数&#xff0c;操作超出现有权限操作的功能点。举例 修改密码时&#xff0c;可以通过修改名称参数&#xff0c;修改任意用户密码。 任…

12.11数据结构-图

无向完全图&#xff1a;在无向图中&#xff0c;如果任意两个顶点之间都存在边&#xff0c;则称该图为无向完全图。 有向完全图&#xff1a;在有向图中&#xff0c;如果任意两个顶点之间都存在方向相反的两条弧&#xff0c;则称该图为有向完全图。 含有n个顶点的无向完全图有…

【Python】【数据分析】深入探索 Python 数据可视化:Matplotlib 绘图库完整教程

目录 引言一、什么是 Matplotlib&#xff1f;1.1 Matplotlib 的安装1.2 Matplotlib 的基本功能 二、Matplotlib 的基础绘图2.1 绘制折线图2.2 绘制柱状图2.3 绘制散点图2.4 绘制饼图 三、高级功能与定制3.1 设置图表样式3.2 使用子图3.3 保存图表 四、Matplotlib 流程图4.1 Mer…

3-机器人视觉-机器人抓取与操作

文章目录 3机器人视觉目录 1. 传感器和标定摄像头模型Intrinsic MatrixExtrinsic Matrix 标定内参标定手眼标定和外参标定 力传感器&其它传感器其它传感器 2. 神经网络和图像处理2D特征处理常见架构 训练流程推理流程部署流程2D 图像任务3D Point Cloud FeaturePointNet Ap…

从源码层级深入探索 Spring AMQP 如何在 Spring Boot 中实现 RabbitMQ 集成——消费者如何进行消费

本章节主要从底层源码探索Spring Boot中RabbitMQ如何进行消费&#xff0c;至于RabbitMQ是如何使用如何生产消息&#xff0c;本章不做过多介绍&#xff0c;感兴趣的小伙伴可以参考&#xff1a;从源码层级深入探索 Spring AMQP 如何在 Spring Boot 中实现 RabbitMQ 集成——生产者…

修改vscode中emmet中jsx和tsx语法中className的扩展符号从单引号到双引号 - HTML代码补全 - 单引号双引号

效果图 实现步骤 文件 > 首选项 > 设置搜索“”在settings.json中修改&#xff0c;增加 "emmet.syntaxProfiles": {"html": {"attr_quotes": "single"},"jsx": {"attr_quotes": "double","…

【小白51单片机专用教程】protues仿真AT89C51入门

课程特点 无需开发板0基础教学软件硬件双修辅助入门 本课程面对纯小白&#xff0c;因此会对各个新出现的知识点在实例基础上进行详细讲解&#xff0c;有相关知识的可以直接跳过。课程涉及protues基本操作、原理图设计、数电模电、kell使用、C语言基本内容&#xff0c;所有涉及…

ARMS 用户体验监控正式发布原生鸿蒙应用 SDK

作者&#xff1a;羿莉 背景 对企业数据进行敏感数据扫描和保护可以提升企业或组织的数据安全。一方面敏感数据可能包括个人身份信息、财务记录、医疗记录等&#xff0c;定期扫描这些数据可以防止未经授权的访问和泄露。 另一方面&#xff0c;许多国家和地区都有关于数据保护的…

Redis和数据库的一致性(Canal+MQ)

想要保证缓存与数据库的双写一致&#xff0c;一共有4种方式&#xff0c;即4种同步策略&#xff1a; 先更新缓存&#xff0c;再更新数据库&#xff1b;先更新数据库&#xff0c;再更新缓存&#xff1b;先删除缓存&#xff0c;再更新数据库&#xff1b;先更新数据库&#xff0c;再…

spring学习(spring-bean实例化(无参构造与有参构造方法实现)详解)

目录 一、spring容器之bean的实例化。 &#xff08;1&#xff09;"bean"基本概念。 &#xff08;2&#xff09;spring-bean实例化的几种方式。 二、spring容器使用"构造方法"的方式实例化bean。 &#xff08;1&#xff09;无参构造方法实例化bean。 &#…

Qt WORD/PDF(二)使用 QtPdfium库实现 PDF操作、打印等

关于QT Widget 其它文章请点击这里: QT Widget GitHub 源码: QWidgetLearningPro &#xff08;暂未更新&#xff09; 姊妹篇: Qt WORD/PDF&#xff08;一&#xff09;使用 QtPdfium库实现 PDF 预览 一、简介 QtPdfium 是基于Pdfium库的一个Qt绑定。Pdfium是一个…

【Leecode】Leecode刷题之路第82天之删除排序链表中的重复元素II

题目出处 82-删除排序链表中的重复元素 II-题目出处 题目描述 个人解法 思路&#xff1a; todo代码示例&#xff1a;&#xff08;Java&#xff09; todo复杂度分析 todo官方解法 82-删除排序链表中的重复元素 II-官方解法 方法1&#xff1a;一次遍历 思路&#xff1a; 代码…