排序算法 —— 直接插入排序

目录

1.直接插入排序的思想

2.直接插入排序的实现

实现分析

实现代码 

3.直接插入排序的分析

时间复杂度分析

空间复杂度分析 

稳定性


1.直接插入排序的思想

直接插入排序的思想就是把待排序的元素按其关键码值的大小依次插入到一个已经排好序的有序序列中,直到所有的元素插入完为止,得到一个新的有序序列。

在我们日常生活中,玩扑克牌时,其实就是运用了直接插入排序的思想。

2.直接插入排序的实现

实现分析

当只有一个元素的时候,这一个元素肯定是有序的,所以,从第二个元素开始,直到后面的所有元素都是待排序的元素。

因此,我们只需要从左到右依次枚举待排序的元素,将待排序的元素插入到有序序列中即可。

比如:当我们要排升序的时候,枚举到4的时候,4就是待排序元素,4大于它的前一个元素,说明4所在位置值正确的,不需要做其他操作。当我们枚举到2的时候,2就是待排序的元素,对于这种情况,下面的图中,很详细的讲解了这种情况下如何实现一个元素的插入逻辑。

 需要注意的是:

  • 枚举待排序元素的时候是从左到右枚举,并且是从第二个元素开始枚举,直到最后一个元素。(因为第一个元素本来就是有序的)
  •  寻找插入位置是从右往左开始寻找的,最后插入的时候,是赋值给end+1的位置。(因为,我们每次都去和end位置的值作比较,当end位置的值小于tmp中保存的值的时候,end+1就是要插入的值)

实现代码 

#include <stdio.h>void InsertSort(int* nums, int n)
{// [0,end]有序,把end+1位置的插入到前序序列// 控制[0,end+1]有序int i = 0;for (i = 1; i < n; i++)      // 枚举待排序的元素 {int tmp = nums[i];       // 保存待排序的值// 依次和前一个位置比较,寻找插入位置 int end = i-1;while (end >= 0)         {if (tmp < nums[end]) // 当tmp小于end位置的值的时候,需要继续寻找插入位置 {nums[end + 1] = nums[end];--end;}else                 // 当tmp大于or等于end位置的值的时候,说明找到了插入位置 {break;}}// 将tmp中保存的值插入到正确的位置 nums[end + 1] = tmp;}
}int main()
{int nums[] = { 3,4,2,1,7,8,5,6 };InsertSort(nums, 8);int i = 0;while(i < sizeof(nums)/sizeof(int)){printf("%d ",nums[i]);i++;}return 0;
}

代码运行结果如下:

 

3.直接插入排序的分析

时间复杂度分析

假如在最坏情况下:

我们需要枚举n-1个元素,从左到右依次需要比较1、2、3 …… n-1次,这不就是妥妥的等差数列吗?根据等差数列公式并结合大O表示法,最后的时间复杂度为O(N^2)

空间复杂度分析 

在整个排序中的实现中,我们并没有开辟其他的空间,只是使用了常数个的空间,所以空间复杂度是O(1)。

稳定性

在排序的过程中,由于我们是从右往左依次比较,当出现两个相同的元素的时候,后面的元素不会插入到前面那个相同元素的前面。只会插入在相同元素的后面,元素的相对顺序位置不会变,所以直接插入排序是稳定的。

比如:i位置的2并没有小于end位置的2,直接就跳出循环了,元素的相对顺序位置不变。

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

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

相关文章

一种基于OCR图像识别技术的发票采集管理系统及方法

一种基于OCR图像识别技术的发票采集管理系统及方法 摘要 本发明涉及了一种基于OCR图像识别技术的发票采集管理系统及方法&#xff0c;该系统的发票信息采集单元采集发票图片信息数据&#xff0c;OCR图像识别单元基于OCR图像识别技术并结合人工智能深度学习算法对发票图片信息数…

vscode默认添加python项目的源目录路径到执行环境(解决ModuleNotFoundError: No module named问题)

0. 问题描述 vscode中编写python脚本&#xff0c;导入工程目录下的其他模块&#xff0c;出现ModuleNotFoundError: No module named 错误 在test2的ccc.py文件中执行print(sys.path) 查看路径 返回结果发现并无’/home/xxx/first_demo’的路径&#xff0c;所以test2下面的文…

Vue-router 路由守卫执行流程图

vue-router 路由守卫执行的流程图&#xff08;个人理解&#xff09; 图1 - 图2

【MR开发】在Pico设备上接入MRTK3(一)——在Unity工程中导入MRTK3依赖

写在前面的话 在Pico上接入MRTK3&#xff0c;目前已有大佬开源。 https://github.com/Phantomxm2021/PicoMRTK3 也有值得推荐的文章。 MRTK3在PICO4上的使用小结 但由于在MacOS上使用MRTK3&#xff0c;无法通过Mixed Reality Feature Tool工具管理MRTK3安装包。 故记录一下…

jmeter使用文档

文章目录 一、安装使用1、下载2、bin/jmeter.properties介绍 二、windows使用1、微调&#xff08;1&#xff09;界面样式&#xff08;2&#xff09;修改语言 2、简单使用3、各组件详解&#xff08;1&#xff09;CSV 数据文件配置&#xff08;2&#xff09;BeanShell取样器 三、…

Pair的基本概念

概述 当一个方法需返回两个值、并且两个值都有重要意义时&#xff0c;我们一般会用Map的key、value来表达。 但是如果仅返回两个值&#xff0c;就用管理一堆key/value键值对的HashMap等结构&#xff0c;有点大材小用&#xff0c;增加了数据结构的复杂度。所以便出现了pair这个…

RAG流程的实现与改进

一、 RAG流程图 数据入库&#xff1a;读取本地数据并切成小块&#xff0c;并把这些小块经过编码embedding后&#xff0c;存储在一个向量数据库中&#xff08;下图1——6步&#xff09;&#xff1b;相关性检索&#xff1a;用户提出问题&#xff0c;问题经过编码&#xff0c;再在…

探索Python中的多线程与多进程

在Python编程中&#xff0c;多线程和多进程是两个重要的概念&#xff0c;它们被用来提高程序的执行效率。本文将深入探讨这两个概念&#xff0c;并对比它们在Python中的实现方式。 一、多线程 多线程是一种并发执行的程序设计方法。在Python中&#xff0c;我们可以使用thread…

【C++_string类练习】仅仅反转字母

题目链接&#xff1a;仅仅反转字母 解题思路&#xff1a; 这种反转字符的题目我第一个想到的方法就是&#xff1a;双指针 一个指针在前start&#xff0c;一个指针在后back&#xff0c; 如果指针所指向的位置的值是字母&#xff0c;那么两个指针位置的值就进行交换&#xff0…

Leetcode 反转字符串中的单词

这个Java代码解决了“反转字符串中的单词顺序”的问题&#xff0c;具体思想如下&#xff1a; 1. 去除字符串首尾的空格 s.trim() 方法用于去除输入字符串 s 中的前导和尾随空格。这样做是为了防止在后续步骤中多余的空格对结果产生影响。 2. 按空格分割字符串 s.split(&quo…

Ingress-nginx中HTTPS的强制转发

文章目录 在使用aws 的NLB转发流量到ingress时&#xff0c;发现NLP上生成的转发配置不符合正常预期&#xff0c;如下图&#xff1a; ingress-nginx service 配置如下&#xff1a; apiVersion: v1 kind: Service metadata:annotations:service.beta.kubernetes.io/aws-load-b…

智能去毛刺:2D视觉引导机器人如何重塑制造业未来

机器人技术已经深入到各个工业领域中&#xff0c;为制造业带来了前所未有的变革。其中&#xff0c;2D视觉引导机器人技术以其精准、高效的特点&#xff0c;在去毛刺工艺中发挥着越来越重要的作用。本文将为您介绍2D视觉引导机器人技术的基本原理及其在去毛刺工艺中的应用&#…

Node.js学习笔记

回顾&#xff1a; javascript 可以在浏览器运行 &#xff08;js代码会JavaScript的解析引擎执行&#xff09;chrome 》V8 &#xff08;性能最好&#xff09;FireFox 》 奥丁猴safri 》JSCoreIE浏览器 》查克拉JavaScript可以在浏览器端操作DOM 和BOM每一个浏览器都内置了B…

php生成PDF文件(FPDF)

FPDF即“Free PDF”&#xff0c;FPDF类库提供了基本的PDF创建功能&#xff0c;其源代码和使用权是免费的。 PDF格式文档优势 通用&#xff1a;PDF文档在UNIX和Windows系统均可正常使用。 安全&#xff1a;PDF文档可设置为只读模式&#xff0c;并且可以添加密码等保护措施。 美…

JavaScript:闭包、防抖与节流

一&#xff0c;闭包 1&#xff0c;什么是闭包 闭包是指一个函数和其周围的词法环境(lexical environment)的组合。 换句话说&#xff0c;闭包允许一个函数访问并操作函数外部的变量。 闭包的核心特性: 函数内部可以访问外部函数的变量即使外部函数已经返回&#xff0c;内部…

ApacheShiro反序列化 550 721漏洞

Apache Shiro是一个强大且易用的Java安全框架,执行身份验证、授权、密码和会话管理个漏洞被称为 Shiro550 是因为在Apache Shiro的GitHub问题跟踪器中&#xff0c;该漏洞最初被标记为第550个问题,721漏洞名称也是由此而来 Shiro-550 CVE-2016-4437 Shiro反序列化Docker复现 …

Pytest参数详解 — 基于命令行模式!

1、--collect-only 查看在给定的配置下哪些测试用例会被执行 2、-k 使用表达式来指定希望运行的测试用例。如果测试名是唯一的或者多个测试名的前缀或者后缀相同&#xff0c;可以使用表达式来快速定位&#xff0c;例如&#xff1a; 命令行-k参数.png 3、-m 标记&#xff08;…

在wsl2下将Ubuntu从一个盘移动到其他盘

参考文章&#xff1a; wsl下将Ubuntu从c盘移动到其他盘 WSL数据迁移(迁移ext4.vhdx) WSL 系统迁移&#xff08;2&#xff09;&#xff0c;导入虚拟机磁盘映像 .vhdx ext4/fs WSL2迁移后默认登陆用户为root的解决方案 操作过程&#xff1a; 1.查看当前系统中wsl分发版本 …

系统托盘图标+快捷启动(Python)

QkStart 我把这个程序命名为QkStart 代码 # -*- coding: utf-8 -*- # Environment PyCharm # File_name QkStart |User Pfolg # 2024/10/19 22:06 import threading import time import pystray from PIL import Image from pystray import MenuItem, Menu import o…