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

插入排序

基本思想


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

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

代码实现


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. 稳定性:不稳定

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

中间件模版引擎

文章目录 中间件1.自定义中间件1&#xff09;全局2&#xff09;局部中间件 2.内置中间件(静态资源目录&#xff09; Art-template1.模板语法1&#xff09;输出2&#xff09;原文输出3&#xff09;条件判断4&#xff09;循环5&#xff09;子模版6&#xff09;模版继承7&#xff…

2024四川三支一扶“考生信息表”照着填❗

2024四川三支一扶“考生信息表”照着填❗ ☑️四川三支一扶开始报名&#xff0c;大家要按照提示如实、准确、完整填写《高校毕业生“三支一扶”计划招募考生信息表》哦~ ☑️不知道怎么填写的宝子们&#xff0c;可以参考图1。 ☑️毕业证书编号如实填写&#xff0c;若是应届生&…

vue3 todolist 简单例子

vue3 简单的TodList 地址&#xff1a; https://gitee.com/cheng_yong_xu/vue3-composition-api-todo-app-my 效果 step-1 初始化项项目 我们不采用vue cli 搭建项目 直接将上图文件夹&#xff0c;复制到vscode编辑器&#xff0c;清空App.vue的内容 安装包 # 安装包 npm…

JVM双亲委派模型

在之前的JVM类加载器篇中说过&#xff0c;各个类加载器都有自己加载的范围&#xff0c;比如引导类加载器只加载Java核心库中的class如String&#xff0c;那如果用户自己建一个包名和类名与String相同的类&#xff0c;会不会被引导类加载器加载。可以通过如下代码测试&#xff0…

每周统计-20240531

用于测试程序的稳定性&#xff1a; 龙虎榜&#xff1a; 成交额&#xff1a; 封成比&#xff1a; 收盘前放量&#xff1a; 开盘抢筹&#xff1a; 封单额&#xff1a;

堆排序-java

这次主要讲了堆排序和堆的基本构造&#xff0c;下一期会详细讲述堆的各种基本操作。 文章目录 前言 一、堆排序 1.题目描述 2.堆 二、算法思路 1.堆的存储 2. 结点下移down 3.结点上移up 4.堆的基本操作 5.堆的初始化 三、代码如下 1.代码如下&#xff1a; 2.读入数据&#xff…

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

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

2024拼多多 最新理论+实战干货,从入门到精通全链路多角度学习-7节课

基于最新规则理论结合实际的干货 课程内容&#xff1a; 01 2024年多多防比价新规则破局理论课与实操课.mp4 02 24年多多强付费第二节课基础内功.mp4 03 24年多多强付费第三节课直通车实操 .mp4 04 24年多多强付费第一节课市场定价格段,mp4 05 24年多多自然流第一节课市场…

Java+SVNCloud+Mysql课程设计

文章目录 1、主要内容2、所需准备3、与sql访问的中间类&#xff1a;SqlMessage4、窗口界面5、main方法 1、主要内容 课程设计&#xff0c;主要通过Javas wing创建窗口&#xff0c;jdbc连接云端mysql数据库进行基本操作&#xff0c;支持随机生成数据并用动态展示数据结果。 先…

计算机毕业设计 | springboot+vue会议室管理系统(附源码)

1&#xff0c;绪论 1.1 项目背景 随着企业规模的不断扩大&#xff0c;会议室管理愈加复杂。传统的手工预约会议室的方式已经无法满足现代企业的需求&#xff0c;因此&#xff0c;开发一套会议室系统方案变得尤为重要。会议室系统可以实现会议室的在线预约、会议室资源的有效利…

[SQL-SERVER:数据库安全及维护]:MSSM工具进行附加还原备份等操作

文章目录 目的介绍一、完整备份与还原&#xff08;20分&#xff09;1.将教师提供的TeachingDB数据库附加到个人使用的服务器上&#xff0c;并更名为TeachingDB_***&#xff08;***为个人姓名&#xff09;1.1 操作流程&#xff1a;将docker容器sqlserver数据库已有的mdf镜像文件…

C语言之旅:探索单链表

目录 一、前言 二、实现链表的功能&#xff1a; 打印 创建节点 尾插 尾删 头插 头删 查找 在指定位置之前插入数据 指定位置删除 在指定位置之后插入数据 打印 销毁 三、全部源码&#xff1a; 四、结语 一、前言 链表是一个强大且基础的数据结构。对于很多初…

Mac连接虚拟机(Linux系统)

1.确定虚拟机的IP地址 ifconfig //终端命令&#xff0c;查询ip地址 sudo apt install net-tools 安装完成后再次执行 ifconfig&#xff1a; 2.安装SSH&#xff08;加密远程登录协议&#xff09; (1).安装OpenSSH服务器软件包&#xff1a; sudo apt-get install openssh-ser…

Linux开发

建议大家使用 Linux 做开发 Linux 能用吗&#xff1f; 我身边还有些朋友对 linux 的印象似乎还停留在黑乎乎的命令行界面上。当我告诉他或者建议他使用 linux 时&#xff0c;会一脸惊讶的问我&#xff0c;那个怎么用&#xff08;来开发或者日常使用&#xff09;&#xff1f; …

鸿蒙开发接口资源管理:【@ohos.intl (国际化-Intl)】

国际化-Intl 说明&#xff1a;开发前请熟悉鸿蒙开发指导文档&#xff1a;gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md点击或者复制转到。 本模块首批接口从API version 6开始支持。后续版本的新增接口&#xff0c;采用上角标单独标记接口的起始版本。Intl模块…

LabVIEW如何确保步进电机的长期稳定运行

步进电机因其良好的定位精度和控制性&#xff0c;在自动化设备中得到了广泛应用。然而&#xff0c;长期稳定运行对于任何电机系统都是一个重要的挑战。LabVIEW作为一款强大的图形化编程语言&#xff0c;通过其灵活的控制算法和实时监控能力&#xff0c;为步进电机的稳定运行提供…

慢SQL的治理思路

慢SQL的治理思路 什么是慢SQL慢SQL产生的原因查看慢 SQL 是否开启开启慢 SQL 记录开启慢查询日志分析慢 SQL解决和优化慢SQL的方法 什么是慢SQL 慢 SQL 指的是 MySQL 中执行比较慢的 SQL&#xff0c;排查慢 SQL 最常用的方法是通过慢查询日志来查找慢 SQL。 MySQL 的慢查询日志…

【并发程序设计】14.消息队列

14.消息队列 消息队列&#xff08;Message Queue&#xff09;是一种通信机制&#xff0c;用于在分布式系统中传递和管理消息的队列型数据结构。 消息队列通常是一个先进先出&#xff08;FIFO&#xff09;的数据结构&#xff0c;它允许多个进程或线程之间以异步方式进行通信。…

Google力作 | Infini-attention无限长序列处理Transformer

更多文章&#xff0c;请关注微信公众号&#xff1a;NLP分享汇 原文链接&#xff1a;Google力作 | Infini-attention无限长序列处理Transformerhttps://mp.weixin.qq.com/s?__bizMzU1ODk1NDUzMw&mid2247485000&idx1&sne44a7256bcb178df0d2cc9b33c6882a1&chksm…

OpenCV 的几种查找图像中轮廓边缘的方法

原始图片&#xff1a; 1、Sobel() Sobel 算子结合了高斯平滑和微分&#xff0c;用于计算图像的梯度&#xff0c;从而突出显示边缘。 import cv2# 读取图像 image cv2.imread(image.png, cv2.IMREAD_GRAYSCALE)# 使用 Sobel 算子查找水平和垂直边缘 sobel_x cv2.Sobel(image…