当前位置: 首页 > 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初…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...