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

一、八大排序(sort)

文章目录

  • 一、时间复杂度
    • (一)定义:常数操作
  • 二、空间复杂度
    • (一)定义:
  • 三、排序
    • (一)选择排序
      • 1.定义
      • 2.代码
      • 3.特性
    • (二)冒泡排序
      • 1.定义
      • 2.代码
      • 3.特性
    • (三)插入排序
      • 1.定义
      • 2.代码
      • 3.特性
    • (四)归并排序
      • 1.定义
      • 2.代码
      • 3.特性
    • (五)快速排序
    • (六)堆排序
    • (七)基数排序
    • (八)计数排序

一、时间复杂度

(一)定义:常数操作

与数据量无关,是一个固定的东西。
一个操作如果和样本数量没有关系,每次都是固定时间内完成的操作,就叫做常数操作。

时间复杂度为一个算法流程中,常数操作数量的一个指标。常用o(读作big o)来表示。具体来说,先要对一个算法流程非常熟悉,然后去写出这个算法流程中,发生了多少常数操作,进而总结出常数操作数量的表达式。

评价一个算法流程的好坏,先看时间复杂度的指标,然后再分析不同数据样本下的实际运行时间,也就是“常数项时间”。

二、空间复杂度

(一)定义:

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势。

三、排序

(一)选择排序

1.定义

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
请添加图片描述

2.代码

void process(vector<int> &arr) {if (arr == nullptr || arr.size() < 2) {return ;}for (int i = 0 ; i < arr.size() - 1; i++) { // 当前位置int minIndex = i;for (int j = i + 1; j < arr.size(); j++) {minIndex = arr[j] < arr[minIndex] ? j : minIndex;}swap(arr,i,minIndex);}
}
void swap(vector<int> &arr,int j,int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];
}

3.特性

  • 容易理解,但是效率太低,实际当中不太使用

  • 时间复杂度O(n^2),空间复杂度O(1);请添加图片描述

  • 不稳定

(二)冒泡排序

1.定义

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

2.代码

void bubbleSort(vector<int> &arr) {if (arr == nullptr || arr.size() < 2) {return ;}int n = arr.size();for (int i = 0; i < n; i++) { // //控制交换次数for (int j = 0; j < n - i - 1; j ++) { // //向后冒泡 ,控制边界if(arr[j] > arr[j+1])//如果前一个值大于后一个值,交换{swap(arr[j],arr[j+1]);}		}}
}

3.特性

  • 容易理解
  • 时间复杂度O(n^2),空间复杂度O(1)
  • 稳定

(三)插入排序

1.定义

插入排序的步骤如下:每次从无序部分中取出一个元素,与有序部分中的元素从后向前依次进行比较,并找到合适的位置,将该元素插到有序组当中。

例:对于数组 [3,2,5,4,2,3,3] 进行插入排序的详细过程:
1、0~0位置上做到有序 ——>就一个数 做到了
2、0~1位置上做到有序 ——>2比3小 2 3互换位置——> [2,3,5,4,2,3,3]
3、0~2位置上做到有序 ——>5比3大 位置不动——> [2,3,5,4,2,3,3]
4、0~3位置上做到有序 ——>4比5小 4 5互换位置——> [2,3,4,5,2,3,3]——>4比3大 位置不动
5、0~4位置上做到有序 ——>2比5小 2 5互换位置——> [2,3,4,2,5,3,3]
  ——>2比4小 2 4互换位置——> [2,3,2,4,5,3,3]——>2比3小 2 3互换位置——> [2,2,3,4,5,3,3]
  2比2相等 位置不动
6、0~5位置上做到有序 ——>3比5小 3 5互换位置——> [2,2,3,4,3,5,3]
  ——>3比4小 3 4互换位置——> [2,2,3,3,4,5,3]——>3比3相等 位置不动
7、0~6位置上做到有序 ——>3比5小 3 5互换位置——> [2,2,3,3,4,3,5]
  ——>3比4小 3 4互换位置——> [2,2,3,3,3,4,5]——>3比3相等 位置不动

请添加图片描述

2.代码

void insertSort(vector<int> &arr) {if (arr == nullptr || arr.size() < 2) {return ;}for (int i = 1; i < arr.size(); i++) { // 0 - 0 有序的for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1] ; j--) { // 想有序swap(arr,j, j + 1);}}
}

3.特性

  • 元素集合越接近有序,直接插入排序算法的时间效率越高
  • 时间复杂度:O(n^2)(情况最差时,即逆序转有序,最好为O(n));
  • 空间复杂度:O(1);
  • 稳定

(四)归并排序

1.定义

对于一个数组从中点的位置分开,先让左侧部分排好序,再让右边部分排好序,然后整体整合。

将图中左侧部分和右侧部分分别排好序,然后使用两个指针分别从两部分的最左侧开始,在内存中单独开辟一个空间 ,这时我们比较两个指针指向的数的大小,左侧小于等于右侧的时候,将左侧部分指针指向的值拷贝到辅助空间中,然后左侧指针右移一位。如果右侧部分指针指向的值小于左侧的,则将右侧部分指针指向的值拷贝到辅助空间中,然后右侧指针右移一位。依次循环,如果哪侧越界了,将剩下的部分直接拷贝到辅助空间中。将辅助空间拷贝到原数组。
请添加图片描述

2.代码

3.特性

  • 整体就是简单的递归,左边排好序、右边排好序、让整体有序
  • 让其整体有序的过程里用了排外序的方法
  • 利用master公式来求解时间复杂度
  • 归并排序的实质

(五)快速排序

(六)堆排序

(七)基数排序

(八)计数排序

相关文章:

一、八大排序(sort)

文章目录 一、时间复杂度&#xff08;一&#xff09;定义&#xff1a;常数操作 二、空间复杂度&#xff08;一&#xff09;定义&#xff1a; 三、排序&#xff08;一&#xff09;选择排序1.定义2.代码3.特性 &#xff08;二&#xff09;冒泡排序1.定义2.代码3.特性 &#xff08…...

【AWS】AI 代码生成器—Amazon CodeWhisperer初体验 | 开启开挂编程之旅

使用 AI 编码配套应用程序更快、更安全地构建应用程序 文章目录 1.1 Amazon CodeWhisperper简介1.2 Amazon CodeWhisperer 定价2.1 打开VS Code2.2 安装AWS ToolKit插件 一、前言 1.1 Amazon CodeWhisperper简介 1️⃣更快地完成更多工作 CodeWhisperer 经过数十亿行代码的训…...

【Mysql主从配置方法---单主从】

Mysql主从 主服务器 创建用户 create user “for_rep”“从服务器IP地址” IDENTIFIED by “123456” 授权 grant replication slave on . to “for_rep”“从服务器IP地址” IDENTIFIED by “123456” 查看用户权限 SHOW GRANTS FOR “for_rep”“从服务器IP地址”; 修改M…...

⼀⽂读懂加密资产交易赛道的新锐⼒量Bitdu

交易所&#xff0c;仍然是加密资产赛道的皇冠级赛道。围绕这个领域展开的商业竞争&#xff0c;最能引起⼴⼤⽤⼾的关注。 经历了数轮资产价格涨跌的⽜熊之后&#xff0c;⼀批批创业者也在不断地思考这⼀议题 — 如何在去中⼼化的世界中&#xff0c;最⾼效率地集结流量、资本和…...

万里牛与金蝶云星空对接集成查询调拨单连通调拨单新增(万里牛调拨单-金蝶【直接调拨单】)

万里牛与金蝶云星空对接集成查询调拨单连通调拨单新增(万里牛调拨单-金蝶【直接调拨单】) 源系统:万里牛 万里牛是杭州湖畔网络技术有限公司旗下SaaS软件品牌&#xff0c;主要针对电商、外贸、实体门店等业务群体&#xff0c;帮助企业快速布局新零售&#xff0c;提升订单处理效…...

虚拟DOM与diff算法

虚拟DOM与diff算法 snabbdom虚拟DOMdiff算法 snabbdom 是什么&#xff1a;snabbdom是著名的虚拟DOM库&#xff0c;是diff算法的鼻祖&#xff0c;Vue源码借鉴了snabbdom 虚拟DOM 是什么&#xff1a;本质上是存在内存里的 JavaScript 对象 作用&#xff1a;用来描述真实DOM的层…...

K8S:pod资源限制及探针

文章目录 一.pod资源限制1.pod资源限制方式2.pod资源限制指定时指定的参数&#xff08;1&#xff09;request 资源&#xff08;2&#xff09; limit 资源&#xff08;3&#xff09;两种资源匹配方式 3.资源限制的示例&#xff08;1&#xff09;官网示例&#xff08;2&#xff0…...

CSS中的定位

position 的属性与含义 CSS 中的 position 属性用于控制元素在页面中的定位方式&#xff0c;有四个主要的取值&#xff0c;每个取值都会影响元素的布局方式&#xff0c;它们是&#xff1a; static&#xff08;默认值&#xff09;&#xff1a; 这是所有元素的初始定位方式。在静…...

二、链表(linked-list)

文章目录 一、定义二、经典例题&#xff08;一&#xff09;[21.合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/description/)1.思路2.复杂度分析3.注意4.代码 &#xff08;二&#xff09;[86.分割链表](https://leetcode.cn/problems/partition-list…...

Android EditText筛选+选择功能开发

在日常开发中经常会遇到这种需求&#xff0c;EditText既需要可以筛选&#xff0c;又可以点击选择。这里筛选功能用的是AutoCompleteTextView&#xff0c;选择功能使用的是第三方库https://github.com/kongzue/DialogX。 Android AutoCompleteTextView(自动完成文本框)的基本使用…...

Linux 信号 alarm函数 setitimer函数

/*#include <unistd.h>unsigned int alarm(unsigned int seconds);功能&#xff1a;设置定时器。函数调用&#xff0c;开始倒计时&#xff0c;0的时候给当前的进程发送SIGALARM信号参数&#xff1a;倒计时的时长。。单位&#xff1a;秒 如果参数为0&#xff0c;无效返回…...

自主设计,模拟实现 RabbitMQ - 实现发送方消息确认机制

目录 一、实现发送方消息确认 1.1、需求分析 什么是发送方的消息确认? 如何实现?...

【数据结构】二叉树的·深度优先遍历(前中后序遍历)and·广度优先(层序遍历)

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

优彩云采集器下载-免费优彩云采集器下载地址

免费优彩云采集器。您是否曾为了数据采集而感到头疼不已&#xff1f;是否一直在寻找一种能够轻松、高效地获取所需数据的方法&#xff1f;别着急&#xff0c;让我们一起来了解如何通过优彩云采集器解决这些问题&#xff0c;从而让您产生购买的欲望。 免费全自动采集发布批量管理…...

【Python】OJ 常用函数

这里写目录标题 一. math1. 求阶乘 - factorial()2. 绝对值 - fabs() 二. 容器的方法1. reverse() 三. Python 内置函数1. sort() 一. math 需要引入 math 包&#xff1a;import math 1. 求阶乘 - factorial() import math print(math.factorial(5))--------运行结果-------…...

【Vue】上万个字把事件处理讲解的淋漓尽致

hello&#xff0c;我是小索奇&#xff0c;精心制作的Vue系列教程持续更新哈&#xff0c;想要学习&巩固&避坑就一起学习吧~ 事件处理 事件的基本用法 重点内容 使用v-on:xxx缩写xxx绑定事件&#xff0c;其中 xxx 是事件名&#xff08;回顾&#xff1a;v-bind缩写为冒号…...

Remmina中VNC、SSH和RDP的区别

Remmina 可以在 Linux 系统上对远程进行连接。它支持多种远程连接协议&#xff0c;包括 VNC&#xff08;Virtual Network Computing&#xff09;、SSH&#xff08;Secure Shell&#xff09;和 RDP&#xff08;Remote Desktop Protocol&#xff09;。这些协议用于实现不同类型的…...

Spring Boot实现web.xml功能

Spring Boot实现web.xml功能 1. 基于注解实现1.1 组件注册1.2 WebInitParam注解 2. 基于编码实现2.1 Servlet & Filter2.2 Listener 3. 总结 在Spring Boot中&#xff0c;不再需要使用传统的 web.xml 文件来配置web应用的功能&#xff0c;Spring Boot支持通过注解和基于代码…...

陆拾捌- 如何通过数据影响决策(三)

一、如何正确的引导别人&#xff1f; 引导与误导的区别是什么&#xff1f; 看下面这广告图 单看上面大字的结果&#xff0c;感觉好像真的使用过的人均觉得有好处 可如果我们看下面的细字 对111位连续14天食用&#xff08;本产品&#xff09;的燕麦片非重度使用者所做调研… 从…...

VMware 三种网络连接模式

VMware虚拟机的三种网络连接模式&#xff1a;桥接&#xff0c;NAT&#xff0c;仅主机。 网卡vmnet0,vmnet1,vmnet8区别。 在VMware中&#xff0c;虚拟机的网络连接主要是由VMware创建的虚拟交换机负责实现的&#xff0c;VMware可以根据需要创建多个虚拟网络。 VMware的虚拟网…...

通用汽车IT部门裁员600人,为AI人才腾空间,软件团队变革进行时

通用汽车IT部门裁员600人&#xff0c;AI人才成新宠 通用汽车证实已对其IT部门进行裁员&#xff0c;约600名领薪员工&#xff08;占比10%以上&#xff09;被裁&#xff0c;目的是清除专业知识不再适用的员工&#xff0c;为具有AI背景的人员腾出空间。公司表示这是面向未来做好准…...

构建个人技能库:从代码片段到可复用技能单元的设计与实践

1. 项目概述&#xff1a;当代码遇上魔法&#xff0c;技能库的构建哲学在软件开发的日常里&#xff0c;我们常常会羡慕那些“魔法师”般的同事&#xff1a;他们似乎总能信手拈来一段代码&#xff0c;优雅地解决一个棘手问题&#xff1b;或者拥有一个私人的“百宝箱”&#xff0c…...

保姆级教程:用GATK4从玉米B73参考基因组中提取SNP和Indel(附完整代码)

玉米基因组变异检测实战指南&#xff1a;从测序数据到SNP/Indel分析全流程 在植物遗传学研究领域&#xff0c;玉米作为重要的模式作物和粮食作物&#xff0c;其基因组变异分析对品种改良和功能基因挖掘具有重要意义。本文将带领生物信息学初学者逐步完成从原始测序数据到变异检…...

2026 AI大模型API加速网站推荐

在AI开发领域&#xff0c;一个现实问题始终困扰着开发者&#xff1a;如何接入模型厂商的官方API&#xff1f;在海外&#xff0c;注册、绑卡、调用这三个步骤就能轻松解决。然而&#xff0c;国内开发者面临着跨境网络波动、外币支付门槛、发票合规需求以及多厂商Key碎片化管理等…...

ArcGIS 10.2 保姆级安装与破解教程(含License Manager启动失败解决方案)

ArcGIS 10.2 完整安装指南&#xff1a;从零开始到完美运行 1. 准备工作与环境检查 在开始安装ArcGIS 10.2之前&#xff0c;确保你的系统满足以下基本要求&#xff1a; 操作系统&#xff1a;Windows 7/8/10&#xff08;32位或64位&#xff09;硬件配置&#xff1a;至少4GB RAM&a…...

AI和大模型——拟合

一、拟合 Fitting,中文翻译成拟合&#xff0c;这个翻译还是比较贴切的。怎么理解拟合呢&#xff1f;其实非常好理解&#xff0c;如果接受过九年义务教育&#xff0c;基本都有极限或微积分的概念。有没有想起过积分中用高低不等的小矩形来拼凑出曲线面的面积&#xff0c;那个过程…...

chatgpt.js:纯客户端集成ChatGPT,构建浏览器AI应用实战

1. 项目概述&#xff1a;一个专为浏览器环境打造的ChatGPT交互库如果你是一名前端开发者&#xff0c;或者经常需要在自己的网页项目中集成智能对话功能&#xff0c;那么你一定对调用大型语言模型的API不陌生。传统的做法是&#xff0c;在自己的后端服务器上封装一个接口&#x…...

别再只调分辨率了!手把手教你用VESA时序搞定1080P显示器驱动(附Verilog代码)

从VESA标准到FPGA实战&#xff1a;构建1080P显示驱动的完整逻辑链 在数字显示技术领域&#xff0c;驱动一块19201080分辨率的屏幕远不止是配置几个参数那么简单。当我第一次尝试用FPGA驱动高清显示器时&#xff0c;发现大多数教程都停留在"设置分辨率"的层面&#xf…...

京东数据利器:掌握详情与评论资源

在电商高速发展的今天&#xff0c;数据是了解市场、洞察用户需求、优化产品策略的核心利器。京东作为国内领先的电商平台&#xff0c;其商品详情与用户评论数据承载了大量价值信息。掌握这些资源&#xff0c;不仅可以帮助商家、品牌方优化产品策略&#xff0c;还能辅助内容创作…...

用Python+CCA算法搞定SSVEP脑电信号识别:从理论到代码实战(附GitHub源码)

PythonCCA算法实现SSVEP脑电信号识别实战指南 在脑机接口研究领域&#xff0c;稳态视觉诱发电位&#xff08;SSVEP&#xff09;因其高信噪比和稳定特性成为热门研究方向。典型相关分析&#xff08;CCA&#xff09;作为SSVEP信号处理的经典算法&#xff0c;以其数学优雅和实现简…...