当前位置: 首页 > news >正文

【数据结构】插入排序,希尔排序,选择排序,堆排序,冒泡排序

1.插入排序

思路:插入排序将一个数插入一个有序的数组里面,将这个数和数组元素挨着比较,直到他插入到合适的位置。
动画演示:
在这里插入图片描述

步骤:1.定义一个变量tmp保存要插入的数据
2.在循环中用tmp和有序数组中的元素比较(比方说要和a[end]比较,如果tmp<a[end]的话,就将a[end]右移动到a[end+1],如果tmp>a[end]的话就直接结束循环,因为已经找到了自己的位置,就是a[end+1].
3.当循环结束则表明已经找到了tmp的位置,下标为end+1,将tmp赋值给a[end+1]即可。
代码实现

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 (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}}

直接插入排序的特性总结:

  1. 元素集合越接近有序,直接插入排序算法的时间效率越高
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1),它是一种稳定的排序算法
  4. 稳定性:稳定

2.希尔排序

希尔排序( 缩小增量排序 )
希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。相当于分组的插入排序。

步骤:
1.将要排列的数据分为几组
2.每一组内进行插入排序。
3.缩小组数,当组数为1时,相当于直接插入排序。
在这里插入图片描述

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

上面代码为单组的排序,只有一组。

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

加了循环,将每组都排好序,但是整体没有有序。当gap!=1时,属于预排序。每次循环减小gap的值。说明分组在变,然后在每一组里面继续排序,当gap等于1时,相当于插入排序。

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

上面这种是一组排,会多套一层循环。如果使用下面的代码是一组没排完,就进行排下一组,一组中先把前两个元素排好,在排第二组的前两个元素,当排完每一组的前两个元素,又回到第一组,排第一组的前三个元素,排好前三个元素,接着排第二组的前三个元素,依次类推。

时间复杂度平均:O(N^1.3)
空间复杂度:O(1)

3.选择排序

基本思想:
每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的
数据元素排完 。
步骤:1.定义两个变量maxi,mini分别记录要排序数据的最大值和最小值的下标。初始将·maxi,mini等于起始下标。
2.循环遍历要排序的数据,更新下标,如果有数据大于a[maxi],maxi更新为当前的i;如果有数据小于a[mini],mini更新为当前的i;
3.交换此时最小值和第一个数据的位置,最大值和最后一个数据的位置,已经保证了两个数据到他该有的位置。起始位置下标++,结束位置下标–;
4.然后就要排除已经排好的两个元素,现在maxi与mini起始下标就为第二个元素下标了。
5.循环条件起始位置下标小于结束位置下标。

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

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

如果你要排序的数据里面最大的数据不是第一个的话,上面的代码你会觉得是正确的,如果第一个数据是最大的,排序就不对了,到底是为什么呢?我们可以调试调试
在这里插入图片描述
修改代码为:

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

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

4.堆排序

堆排序是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。

void AdjustDwon(int* a, int n, int root)//向下调整建立大堆。
{int child = root * 2 + 1;while (child < n){if (child+1<n &&a[child] < a[child + 1]){child = child + 1;}if (a[child] > a[root]){swap(&a[child], &a[root]);root = child;child = root * 2 + 1;}else{break;}}}

在这里插入图片描述
上图为建立的大堆。

堆排序演示

5.冒泡排序

思路:
左边大于右边交换一趟排下来最大的在右边
在这里插入图片描述
代码实现:

void BubbleSort(int* a, int n)
{for (int i = 0; i < n-1; i++){for (int j = 0; j < n - i-1; j++){if (a[j + 1] < a[j]){swap(&a[j], &a[j + 1]);}}}}

时间复杂度:O(N^2)
空间复杂度:O(1)

相关文章:

【数据结构】插入排序,希尔排序,选择排序,堆排序,冒泡排序

1.插入排序 思路&#xff1a;插入排序将一个数插入一个有序的数组里面&#xff0c;将这个数和数组元素挨着比较&#xff0c;直到他插入到合适的位置。 动画演示&#xff1a; 步骤&#xff1a;1.定义一个变量tmp保存要插入的数据 2.在循环中用tmp和有序数组中的元素比较&#…...

MyBatis--07--启动过程分析、SqlSession安全问题、拦截器

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 谈谈MyBatis的启动过程具体的操作过程如下&#xff1a;实现测试类,并测试SqlSessionFactorySqlSession SqlSession有数据安全问题?在MyBatis中&#xff0c;SqlSess…...

Qt基础之四十二:QMap、QHash的实现原理和性能对比

一.红黑树与哈希表 1.红黑树 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 红黑树为了保证其最长…...

虚幻学习笔记12—C++类的实例化

一、前言 本系列如无特殊说明使用的虚幻版本都是5.2.1&#xff0c;VS为2022版本。在Unity中通常创建的脚本都默认继承了MonoBehavior&#xff0c;都是不能再用代码New而实例化的&#xff0c;虚幻也是一样不能直接New来实例化。在Unity中是通过Instantiate方法来实例化一个游戏对…...

【《漫画算法》笔记】快速排序

非递归实现 使用集合栈代替递归的函数栈 public static void main(String[] args) {int[] arrnew int[]{4,4,6,4,3,2,8,1}; // int[] arrnew int[]{3,2}; // quickSort1(arr,0,arr.length-1); // recursive, double sides // quickSort2(arr,0,arr.lengt…...

C++如何通过调用ffmpeg接口对H265文件进行编码和解码

要对H265文件进行编码和解码&#xff0c;需要使用FFmpeg库提供的相关API。以下是一个简单的C程序&#xff0c;演示如何使用FFmpeg进行H265文件的编码和解码&#xff1a; 编码&#xff1a; #include <cstdlib> #include <cstdio> #include <cstring> #inclu…...

8位LED流水灯设计

一、实验目的 本实验为设计性实验,要求理解和掌握触发器、译码器、时序脉冲、LED显示单元的工作原理与功能,通过设计和制作8位的LED流水灯电路,综合运用触发器和译码器等逻辑器件及显示单元进行功能性时序逻辑电路的设计和制作,掌握时序逻辑电路的基本设计和调试方法。 二、…...

eclipse连接mysql数据库(下载eclipse,下载安装mysql,下载mysql驱动)

前言&#xff1a; 使用版本&#xff1a;eclipse2017&#xff0c;mysql5.7.0&#xff0c;MySQL的jar建议使用最新的&#xff0c;可以避免警告&#xff01; 1&#xff1a;下载安装&#xff1a;eclipse&#xff0c;mysql在我之前博客中有 http://t.csdnimg.cn/UW5fshttp://t.csdn…...

【信息学奥赛】拼在起跑线上,想入道就别落下自己!

编程无难事&#xff0c;只怕有心人&#xff0c;学就是了&#xff01; 文章目录 1 信息学奥赛简介2 信息学竞赛的经验回顾3 优秀参考图书推荐《信息学奥赛一本通关》4 高质量技术圈开放 1 信息学奥赛简介 信息学奥赛&#xff0c;作为全国中学生学科奥林匹克“五大学科竞赛”之一…...

Python 进程池Pool Queue,运行不出来结果!

文章目录 代码及结论 代码及结论 import os from multiprocessing import Pool, Queue from collections import Counterdef func(q):q.put(1)queue Queue()with Pool(4) as pool:for i in range(10):pool.apply_async(func, args(queue,),)print(queue.qsize())上边的代码qu…...

yolov8实战第二天——yolov8训练结果分析(保姆式解读)

yolov8实战第一天——yolov8部署并训练自己的数据集&#xff08;保姆式教程&#xff09;-CSDN博客 我们在上一篇文章训练了一个老鼠的yolov8检测模型&#xff0c;训练结果如下图&#xff0c;接下来我们就详细解析下面几张图。 一、混淆矩阵 正确挑选&#xff08;正确&#…...

​urllib.request --- 用于打开 URL 的可扩展库​

源码&#xff1a; Lib/urllib/request.py urllib.request 模块定义了适用于在各种复杂情况下打开 URL&#xff08;主要为 HTTP&#xff09;的函数和类 --- 例如基本认证、摘要认证、重定向、cookies 及其它。 参见 对于更高级别的 HTTP 客户端接口&#xff0c;建议使用 Reques…...

【Docker】进阶之路:(十二)Docker Composer

【Docker】进阶之路&#xff1a;&#xff08;十二&#xff09;Docker Composer Docker Compose 简介安装 Docker Compose模板文件语法docker-compose.yml 语法说明imagecommandlinksexternal_linksportsexposevolumesvolunes_fromenvironmentenv_fileextendsnetpiddnscap_add,c…...

MES安灯管理:优化生产监控的重要工具

一、MES安灯管理的概念 MES安灯管理是一种基于物理安灯和数字化管理的生产异常管理工具。它通过物理安灯和数字化系统的结合&#xff0c;实现对生产异常的实时监控和及时反馈&#xff0c;从而帮助企业快速响应和解决生产异常&#xff0c;提高生产效率和产品质量。 二、MES系统…...

Unity中URP Shader 的 SRP Batcher

文章目录 前言一、SRP Batcher是什么二、SRP Batcher的使用条件1、可编程渲染管线2、我们用URP作为例子3、URP 设置中 Use SRP Batcher开启4、使 SRP Batcher 代码路径能够渲染对象5、使着色器与 SRP Batcher 兼容&#xff1a; 三、不同合批之间的区别BuildIn Render Pipeline下…...

十四 动手学深度学习v2计算机视觉 ——转置矩阵

文章目录 基本操作填充、步幅和多通道再谈转置卷积不填充&#xff0c;步幅为1填充为p&#xff0c;步幅为1填充为p&#xff0c;步幅为s 基本操作 填充、步幅和多通道 填充&#xff1a; 与常规卷积不同&#xff0c;在转置卷积中&#xff0c;填充被应用于的输出&#xff08;常规卷…...

Spark-Streaming+Kafka+mysql实战示例

文章目录 前言一、简介1. Spark-Streaming简介2. Kafka简介二、实战演练1. MySQL数据库部分2. 导入依赖3. 编写实体类代码4. 编写kafka主题管理代码5. 编写kafka生产者代码6. 编写Spark-Streaming代码7. 查看数据库8. 代码下载总结前言 本文将介绍一个使用Spark Streaming和Ka…...

C++改写为C

stm使用中&#xff0c;经常能见到CPP的示例&#xff0c;这些是给arduino&#xff0c;esp32用的&#xff0c;stm32 也支持cpp但是你就想用c怎么办呢&#xff0c;比如我在新手的时候&#xff1a;&#xff1a; 这个双冒号就难住了英雄好汉 比如这是个cpp的 如果类不多的情况下 改写…...

抖去推--短视频剪辑、矩阵无人直播saas营销工具一站式开发

抖去推是一款短视频剪辑和矩阵无人直播SAAS营销工具一站式开发平台。它提供了以下功能和特点&#xff1a; 1. 短视频剪辑&#xff1a;抖去推提供了一系列的剪辑工具&#xff0c;包括自动剪辑、特效制作、配音配乐等&#xff0c;可以帮助用户轻松制作出高质量的短视频。 2. 矩阵…...

HBase 详细图文介绍

目录 一、HBase 定义 二、HBase 数据模型 2.1 HBase 逻辑结构 2.2 HBase 物理存储结构 ​2.3 数据模型 2.3.1 Name Space 2.3.2 Table 2.3.3 Row 2.3.4 Column 2.3.5 Time Stamp 2.3.6 Cell 三、HBase 基本架构 架构角色 3.1 Master 3.2 Region Server 3.3 Zo…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...