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

排序-插入排序与选择排序

插入排序

基本思想


把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

打扑克牌整理手牌用的就是插入排序的思想

代码实现


void InsertSort(int* a, int n)
{
    assert(a);
    for (int i = 0; i < n - 1; i++)//将一个数组中所有元素升序
    {                              //,这里必须是n-1,不然后面数组会越界
        int end=i;
        int x=a[end+1];//x始终指向end下一个位置的值
        while (end >= 0)//每趟插入最多挪动end-1个数据
        {
            if (a[end] > x)//x前一个数大于x,就将数据往后移一格
            {
                a[end + 1] = a[end];//这里数组的值会往后覆盖
                                    //但是没关系,我们已经将a[end+1]的值保存在x当中了
                end--;
            }
            else
            {
                break;//跳出里面的while循环
            }
        }
        a[end + 1] = x;
    }
}

 

特性总结

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

选择排序

基本思想

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

就像小学生排队一样,让最矮的那个站到第一排,然后让第二矮的占到第二排,以此类推

代码实现

void SelectSort(int* a, int n)
{
    int begain = 0;
    int end = n - 1;
    while (begain < end)
    {
        int maxi = begain;//初始化最值
        int mini = begain;
        for (int i = begain; i <= end; i++)
        {
            if (a[i] < a[mini])
            {
                mini = i;//记录下标,否则会有数据被覆盖的问题
            }
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
        }
        swap(&a[begain], &a[mini]);//将最大最小值交换
        swap(&a[end], &a[maxi]);
        begain++;//数组范围往中间缩小
        end--;
    }
}

 

代码优化

上述思想是单向的,我们可以让最高的和最矮的同时排序,就可以优化一下,实现双向排序


void SelectSort(int* a, int n)
{
    int begain = 0;
    int end = n - 1;
    while (begain < end)
    {
        int maxi = begain;
        int mini = begain;
        for (int i = begain; i <=end; i++)
        {
            if (a[i] < a[mini])
            {
                mini = i;//记录下标,否则会有数据被覆盖的问题
            }
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
        }
        swap(&a[begain], &a[mini]);
        if (maxi == begain)//当最大值为begain时,交换最小值和开头元素后,maxi指向的值不再是最大值了.
        {
            maxi = mini;
        }
        swap(&a[end], &a[maxi]);
        begain++;
        end--;
    }
}

 

特性总结

1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1)
4. 稳定性:不稳定

相关文章:

排序-插入排序与选择排序

插入排序 基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中&#xff0c;直到所有的记录插入完为止&#xff0c;得到一个新的有序序列 。 打扑克牌整理手牌用的就是插入排序的思想 代码实现 void InsertSort(int* a, int n) { assert(a); …...

【前端每日基础】day33——响应式布局

响应式布局是一种网页设计的方法&#xff0c;它可以使网站在不同的设备上&#xff08;如桌面电脑、平板电脑、手机等&#xff09;以及不同的屏幕尺寸上呈现出最佳的显示效果。响应式布局的目标是使用户在任何设备上都能够方便地访问和浏览网站&#xff0c;而不需要使用不同版本…...

leetcode 2981.找出出现至少三次的最长子特殊字符串(纯哈希表暴力)

leetcode 2981.找出出现至少三次的最长子特殊字符串&#xff08;传送门&#xff09; class Solution { public:int maximumLength(string s) {int hash[30][52] { 0 },len 1,maxn0;char last A;for (char ch : s) {if (ch last) len;else len 1;for (int i len; i > …...

集成算法实验与分析(软投票与硬投票)

概述 目的&#xff1a;让机器学习效果更好&#xff0c;单个不行&#xff0c;集成多个 集成算法 Bagging&#xff1a;训练多个分类器取平均 f ( x ) 1 / M ∑ m 1 M f m ( x ) f(x)1/M\sum^M_{m1}{f_m(x)} f(x)1/M∑m1M​fm​(x) Boosting&#xff1a;从弱学习器开始加强&am…...

网络数据库后端框架相关面试题

面试是工作的第一步&#xff0c;面试中面试官所提出的问题千奇百怪&#xff0c;其中关于网络数据库后端框架面试题汇总如下&#xff1a; 1&#xff0c;关系型数据库和非关系型数据库的区别 关系型数据库主要有 MYsql Iracle SQLSever等 相对于非关系型数据库的优势为查询效率…...

模拟集成电路(6)----单级放大器(共源共栅级 Cascode Stage)

模拟集成电路(6)----单级放大器&#xff08;共源共栅级 Cascode Stage&#xff09; 大信号分析 对M1 V x ≥ V i n − V T H 1 V x V B − V G S 2 V B ≥ V i n − V T H 1 V G S 2 V_{x}\geq V_{in}-V_{TH1}\quad V_{x}V_{B}-V_{GS2}\\V_{B}\geq V_{in}-V_{TH1}V_{GS2} Vx…...

docker以挂载目录启动容器报错问题的解决

拉取镜像&#xff1a; docker pull elasticsearch:7.4.2 docker pull kibana:7.4.2 创建实例&#xff1a; mkdir -p /mydata/elasticsearch/configmkdir -p /mydata/elasticsearch/dataecho "http.host: 0.0.0.0" >> /mydata/elasticsearch/config/elasti…...

MySQL—函数—流程控制函数(基础)

一、引言 接下来&#xff0c;我们就进入函数的最后一个部分&#xff1a;流程函数。而流程控制函数在我们的日常开发过程是很有用的。 流程控制函数在我们 sql 语句当中&#xff0c;经常用来实现条件的筛选&#xff0c;从而提高语句的一个执行效率。 我们主要介绍以下4个流程控…...

2023年全国职业院校技能大赛(高职组)“云计算应用”赛项赛卷7(私有云)

#需要资源&#xff08;软件包及镜像&#xff09;或有问题的&#xff0c;可私聊博主&#xff01;&#xff01;&#xff01; #需要资源&#xff08;软件包及镜像&#xff09;或有问题的&#xff0c;可私聊博主&#xff01;&#xff01;&#xff01; #需要资源&#xff08;软件包…...

Jenkins、GitLab部署项目

1、安装JDK 1.1、下载openJdk11 yum -y install fontconfig java-11-openjdk1.2、查看安装的版本号 java -version1.3、配置环境变量 vim /etc/profile在最底部添加即可 export JAVA_HOME/usr/lib/jvm/java-11-openjdk-11.0.23.0.9-2.el7_9.x86_64 export PATH$JAVA_HOME/…...

21.Redis之分布式锁

1.什么是分布式锁 在⼀个分布式的系统中, 也会涉及到多个节点访问同⼀个公共资源的情况. 此时就需要通过 锁 来做互斥控制, 避免出现类似于 "线程安全" 的问题. ⽽ java 的 synchronized 或者 C 的 std::mutex, 这样的锁都是只能在当前进程中⽣效, 在分布式的这种多…...

Mysql基础学习:mysql8 JSON字段查询操作

文章目录 一、查询JSON中某个属性值为XXX的数据量1、方式一2、方式二 二、查询的JSON中的value并去除双引号 一、查询JSON中某个属性值为XXX的数据量 1、方式一 select count(*)from table_namewhere JSON_CONTAINS(json-> $.filed1, "xxx")or JSON_CONTAINS(jso…...

搭建基于Django的博客系统数据库迁移从Sqlite3到MySQL(四)

上一篇&#xff1a;搭建基于Django的博客系统增加广告轮播图&#xff08;三&#xff09; 下一篇&#xff1a;基于Django的博客系统之用HayStack连接elasticsearch增加搜索功能&#xff08;五&#xff09; Sqlite3数据库迁移到MySQL 数据库 迁移原因 Django 的内置数据库 SQL…...

24年护网工具,今年想参加护网的同学要会用

24年护网工具集 吉祥学安全知识星球&#x1f517;http://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247483727&idx1&sndb05d8c1115a4539716eddd9fde4e5c9&chksmc0e47813f793f105017fb8551c9b996dc7782987e19efb166ab665f44ca6d900210e6c4c0281&scene21…...

解决TrueNas Scale部署immich后人脸识别失败,后台模型下载异常,immich更换支持中文搜索的CLIP大模型

这个问题搞了我几天终于解决了&#xff0c;搜遍网上基本没有详细针对TrueNas Scale部署immich应用后&#xff0c;CLIP模型镜像下载超时导致人脸识别失败&#xff0c;以及更换支持中文识别的CLIP模型的博客。 分析 现象&#xff1a;TrueNas Scale安装immich官方镜像应用后&…...

面试高频问题----2

一、进程、线程、协程有什么区别&#xff1f; 1.进程&#xff1a;进程是操作系统中独立运行的程序实例&#xff0c;每个进程都有自己的内存空间和系统资源&#xff1b;进程之间相互独立&#xff0c;每个进程有自己的内存地址空间&#xff0c;一个进程无法直接访问另一个进程的…...

Nginx的配置文件-详细使用说明

Nginx的配置文件是Nginx服务器运行的核心,它决定了Nginx如何响应和处理各种请求。以下是对Nginx配置文件(通常名为nginx.conf)的详细解析,按照常见的结构和配置项进行分类: 1. 全局块 user:指定Nginx运行的用户和用户组。例如:user nginx;worker_processes:指定工作进…...

YOLOv5改进 | 卷积模块 | 提高网络的灵活性和表征能力的动态卷积【附代码+小白可上手】

&#x1f4a1;&#x1f4a1;&#x1f4a1;本专栏所有程序均经过测试&#xff0c;可成功执行&#x1f4a1;&#x1f4a1;&#x1f4a1; 轻量级卷积神经网络由于其低计算预算限制了CNNs的深度&#xff08;卷积层数&#xff09;和宽度&#xff08;通道数&#xff09;&#xff0c;…...

23、linux系统文件和日志分析

linux文件系统与日志分析 文件时存储在硬盘上的&#xff0c;硬盘上的最小存储单位是扇区&#xff0c;每个扇区大大小是512字节。 inode&#xff1a;元信息&#xff08;文件的属性 权限&#xff0c;创建者&#xff0c;创建日期等&#xff09; block&#xff1a;块&#xff0c…...

安装VS2017后,离线安装Debugging Tools for Windows(QT5.9.2使用MSVC2017 64bit编译器)

1、背景 安装VS2017后&#xff0c;Windows Software Development Kit - Windows 10.0.17763.132的Debugging Tools for Windows默认不会安装&#xff0c;如下图。这时在QT5.9.2无法使用MSVC2017 64bit编译器。 2、在线安装 如果在线安装参考之前的文章&#xff1a; Qt5.9.2初…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...