【排序算法】一、排序概念和直接插入排序(C/C++)

「前言」文章内容是排序算法之直接插入排序的讲解。(所有文章已经分类好,放心食用)

「归属专栏」排序算法

「主页链接」个人主页

「笔者」枫叶先生(fy)

目录

  • 一、排序概念的介绍
  • 二、直接插入排序
    • 2.1 原理
    • 2.2 代码实现(C/C++)
    • 2.3 特性总结

一、排序概念的介绍

排序的概念

  • 排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作
  • 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的
  • 内部排序:数据元素全部放在内存中的排序
  • 外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内存和外存之间移动数据的排序

常见的排序算法

在这里插入图片描述

二、直接插入排序

2.1 原理

直接插入排序是一种简单直观的排序算法,它的基本思想是将一个元素插入到已经排好序的部分数组中,从而使得数组保持有序。[基于数组(顺序表)的结构进行排序)]

例如,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序

具体步骤如下:

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5

例如,对数组[4, 2, 5, 1, 6, 3]进行排序,使用直接插入排序,如下:(升序)
在这里插入图片描述
动图演示:(数据不和上面相同)
在这里插入图片描述

时间、空间复杂度

  • 时间复杂度最好情况下为O(N),此时待排序列为升序,或者说接近升序
  • 时间复杂度最坏情况下为O(N^2),此时待排序列为逆序,或者说接近逆序
  • 总的来说,直接插入排序的时间复杂度为O(N^2)
  • 在原有的数组上操作,空间复杂度为O(1)

2.2 代码实现(C/C++)

C语言代码如下:(升序)

// 直接插入排序
void InsertSort(int* arr, int n) // arr:需要排序的数组; n:数组的大小
{for (int i = 0; i < n-1; ++i) // 达到n-1时,数组已经有序,无需再遍历最后一次,避免多余的循环{// [0, end]有序,把end+1位置的值插入,保持有序int end = i; // 记录有序序列的最后一个下标int tmp = arr[end + 1]; // 保存等待插入的值while (end >= 0) {if (arr[end] > tmp) // arr[end]比要插入的数大,向后移动{arr[end + 1] = arr[end]; // 向后移,进行覆盖,tmp已经保存被覆盖的值--end; // 迭代}else // arr[end]比要插入的数小,已有序,跳出循环{break;}}arr[end + 1] = tmp; // 进行插入}
}

C++代码:(升序)

// 直接插入排序
void InsertSort(vector<int>& arr)
{int n = arr.size();for (int i = 0; i < n - 1; ++i) // 达到n-1时,数组已经有序,无需再遍历最后一次,避免多余的循环{// [0, end]有序,把end+1位置的值插入,保持有序int end = i; // 记录有序序列的最后一个下标int tmp = arr[end + 1]; // 保存等待插入的值while (end >= 0){if (arr[end] > tmp) // arr[end]比要插入的数大,向后移动{arr[end + 1] = arr[end]; // 向后移,进行覆盖,tmp已经保存被覆盖的值--end; // 迭代}else // arr[end]比要插入的数小,已有序,跳出循环{break;}}arr[end + 1] = tmp; // 进行插入}
}

2.3 特性总结

直接插入排序的特性总结

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

--------------------- END ----------------------

「 作者 」 枫叶先生
「 更新 」 2024.1.9
「 声明 」 余之才疏学浅,故所撰文疏漏难免,或有谬误或不准确之处,敬请读者批评指正。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

移除两个双向链表中的重复元素,每个链表中的元素不重复

移除两个双向链表中的重复元素&#xff0c;每个链表中的元素不重复&#xff0c;请给出算法。 ans: 该问题比单向链表要更加复杂一些&#xff0c;必须考虑并更新前向节点的指向情况&#xff0c;具体编码中存在一些难度&#xff0c;加上链表调试相对不容易&#xff0c;因此难度系…

C++标准学习--decltype

decltype / auto 是具有类型推导功能的 类型 描述/占位 符 decltype: 获取对象或表达式的类型auto: 类型自动推导 decltype 可以获取变量类型&#xff0c; &#xff08;并不同于python的type&#xff0c;但python能打印出type获取的名称&#xff0c; C通过typeid实现&#xff…

HTML---JQurey的基本使用

文章目录 目录 文章目录 本章目标 一.JQuery下载安装 二.JQuery概述 JQuery的作用 JQuery的优势 JQUery示例 三.JQuery基础 语法结构 JQuery常用内置函数 总结 本章目标 &#xff08;1&#xff09;能够搭建jQuery开发环境 &#xff08;2&#xff09;使用ready( )方法加…

机器人技能学习-robosuite-0-入门介绍

文章目录 前言模块介绍实战案例1&#xff1a;从 demo 中创建自己的 env案例2&#xff1a;更换属于自己的物体 前言 资料太少、资料太少、资料太少&#xff0c;重要的事说三边&#xff0c;想根据自己实际场景自定义下机器人&#xff0c;结果发现无路可走&#xff0c;鉴于缺少参…

MathType绝对是我数学编辑的首选工具!

去年&#xff0c;微软曾说&#xff0c;要去掉Office里的公式编辑器&#xff0c;建议用户使用MathType编辑公式。目前Office用户可以到微软官网安装MathType的插件&#xff0c;现在免费使用&#xff0c;以后要收费。Word里安装这个插件以后&#xff0c;就会出现MathType的菜单。…

Kafka与RabbitMQ的区别

消息队列介绍 消息队列&#xff08;Message Queue&#xff09;是一种在分布式系统中进行异步通信的机制。它允许一个或多个生产者在发送消息时暂时将消息存储在队列中&#xff0c;然后由一个或多个消费者按顺序读取并处理这些消息。 消息队列具有以下特点&#xff1a; 异步通…

数模学习day11-系统聚类法

本文参考辽宁石油化工大学于晶贤教授的演示文档聚类分析之系统聚类法及其SPSS实现。 目录 1.样品与样品间的距离 2.指标和指标间的“距离” 相关系数 夹角余弦 3.类与类间的距离 &#xff08;1&#xff09;类间距离 &#xff08;2&#xff09;类间距离定义方式 1.最短…

二阶贝塞尔曲线生成弧线

概述 本文分享一个二阶贝塞尔曲线曲线生成弧线的算法。 效果 实现 1. 封装方法 class ArcLine {constructor(from, to, num 100) {this.from from;this.to to;this.num num;return this.getPointList();}getPointList() {const { from, to } thisconst ctrlPoint thi…

我开源了一个 Go 学习仓库

前言 大家好&#xff0c;这里是白泽&#xff0c;我是21年8月接触的 Go 语言&#xff0c;学习 Go 也正好两年半&#xff0c;我决定重启我之前未完成的计划&#xff0c;继续阅读《The Go Programing Language》&#xff0c;一年多前我更新至第五章讲解的时候&#xff0c;工作的忙…

阅读笔记lv.1

阅读笔记 sql中各种 count结论不同存储引擎计算方式区别count() 类型 责任链模式常见场景例子&#xff08;闯关游戏&#xff09; sql中各种 count 结论 innodb count(*) ≈ count(1) > count(主键id) > count(普通索引列) > count(未加索引列)myisam 有专门字段记录…

pytorch学习笔记(十)

一、损失函数 举个例子 比如说根据Loss提供的信息知道&#xff0c;解答题太弱了&#xff0c;需要多训练训练这个模块。 Loss作用&#xff1a;1.算实际输出和目标之间的差距 2.为我们更新输出提供一定的依据&#xff08;反向传播&#xff09; 看官方文档 每个输入输出相减取…

手把手教你学会接口自动化系列九-封装调用之后的代码展示

接上篇: 手把手教你学会接口自动化系列八-将url写在配置文件中,封装调用-CSDN博客 下来把之前写的demo开始改造,将所有的url = http://192.168.0.134:8081的部分,替代了 如下: demo的改造 # !/usr/bin/env python# -*- coding: utf-8 -*-# @Time : 2023/05# @Author …

S1-06 消息队列

消息队列 消息队列是一种在多任务操作系统中广泛使用的通信机制。它可以用于不同任务之间的消息传递&#xff0c;从而实现数据共享和协调处理任务之间的顺序。 消息队列通常具有以下基本特点&#xff1a; 消息队列的大小有限&#xff1a;消息队列被设计为一种缓冲区&#xff…

【软件测试】路径覆盖

题目要求&#xff1a; a) 流程图如下&#xff1a; b) Consider test cases ti (n 3) and t2 ( n 5). Although these tour the same prime paths in printPrime(), they dont necessarily find the same faults. Design a simple fault that t2 would be more lik…

Legion R7000 2021(82JW)原装出厂Win10/WIN11系统预装OEM系统镜像

LENOVO联想拯救者R7000 2021款(82JW)笔记本电脑原厂Windows10/11系统 链接&#xff1a;https://pan.baidu.com/s/1m_Ql5qu6tnw62PbpvXB0hQ?pwd6ek4 提取码&#xff1a;6ek4 原装出厂系统自带所有驱动、出厂主题壁纸、系统属性专属联机支持标志、系统属性专属联想的LOGO标…

js:使用canvas画一个半圆

背景 需求需要画一个半圆&#xff0c;或者多半圆&#xff0c;其实一下子就能想到 canvas 中的圆弧&#xff0c;核心使用 context.arc context.arc(x,y,r,sAngle,eAngle,counterclockwise)接下来我们看看示例 例一 <!DOCTYPE html> <html lang"en"> &…

C++八股学习心得.8

1.const知道吗&#xff1f;解释其作用 const 修饰类的成员变量&#xff0c;表示成员常量&#xff0c;不能被修改。 const修饰函数承诺在本函数内部不会修改类内的数据成员&#xff0c;不会调用其它非 const 成员函数。 如果 const 构成函数重载&#xff0c;const 对象只能调…

Canopen学习笔记——sync同步报文增加数据域(同步计数器)

1.Canfestival同步报文sync的设置 在OD表中的配置如下&#xff1a; 如果0x1006索引的同步报文循环周期时间设置为0则禁用同步报文&#xff0c;这里要注意的就是&#xff0c;上面第一张图也提到了&#xff0c;时间单位是us。第二张图&#xff0c;我的0x1006就设置为0xF4240,也就…

Docker与微服务实战(高级篇)- 【下】

Docker与微服务实战&#xff08;高级篇&#xff09;- 【下】 八、Docker轻量级可视化工具Portainer8.1.可视化工具Portainer简介8.2.安装Portainer8.2.1.官网8.2.2.docker命令安装8.2.2.1.搜索portainer镜像8.2.2.2.拉取portainer镜像8.2.2.3.启动portainer容器 8.2.3.第一次登…

高通平台开发系列讲解(USB篇)adb function代码分析

文章目录 一、FFS相关动态打印二、代码入口三、ffs_alloc_inst四、ep0、ep1&ep2的注册五、读写过程沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本文主要介绍高通平台USB adb function代码f_fs.c。 一、FFS相关动态打印 目录:msm-4.14/drivers/usb/gadget/fun…