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

插入排序(Insertion Sort)

C++自学精简教程 目录(必读)

插入排序

每次选择未排序子数组中的第一个元素,从后往前,插入放到已排序子数组中,保持子数组有序。

打扑克牌,起牌。

输入数据

42 20 17 13 28 14 23 15

执行过程

完整代码

#include <iostream>
#include <cassert>
#include <vector>
using namespace std;void print_array(const char* msg, int* arr, int n)
{cout << msg << " ";for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;
}
//swap two number
void Swap(int& a, int& b)
{int tmp = a; a = b; b = tmp;
}//将newValue插入到子数组arr中,arr的长度为length
void Insert(int* arr, int newValueindex, int newValue)
{// newValueindex=1     {arr[0]}    <== arr[1]           // newValueindex=2     {arr[0], arr[1]}    <== arr[2]// ......// newValueindex=n-1   {arr[0], arr[1],... arr[n-2]}    <== arr[n-1]// [a,   b,   c,   d]    e//  0              j     length   int j = newValueindex - 1;for (; j >= 0; j--){if (arr[j] > newValue){//move arr[j] to the next position,for newVaulearr[j + 1] = arr[j];}else{break;//break 发生时, j 的值可能是 0}}//发生了移动,j会停止在最后一个需要被移动的位置的前面一个位置if (j != newValueindex - 1){arr[j+1] = newValue;}
}void InsertSort(int* arr, int n)
{if (n <= 1){return;}//将下标为1的元素插入到{arr[0]}中//将下标为2的元素插入到{arr[0], arr[1]}中//......//将下标为n-1的元素插入到{arr[0], arr[1], arr[n-2]}中for (int i = 1; i < n; i++) {//将未排序序列中的第一个元素插入到已排序的序列中Insert(arr, i, arr[i]);//insert first element in unsorted list to the sorted listprint_array("one trip", arr, n);}
}void test(vector<int> arr)
{//输出原始序列print_array("original array:", arr.data(), arr.size());//执行排序,并输出排序过程InsertSort(arr.data(), arr.size());//输出排序后的列表print_array("after sorted:",arr.data(), arr.size());cout << endl;
}int main()
{test({ 1 });test({ 1 , 2 });test({ 2 , 1 });test( { 2 , 2 });test({ 42, 20, 17, 13, 28, 14, 23, 15 });test({ 1, 8, 3, 6, 5, 4, 7, 2 , 9 });test( { 8, 8, 6, 6, 7, 5, 5, 7, 9 , 9});return 0;
}

执行结果

original array: 1
after sorted: 1original array: 1 2
one trip 1 2
after sorted: 1 2original array: 2 1
one trip 1 2
after sorted: 1 2original array: 2 2
one trip 2 2
after sorted: 2 2original array: 42 20 17 13 28 14 23 15
one trip 20 42 17 13 28 14 23 15
one trip 17 20 42 13 28 14 23 15
one trip 13 17 20 42 28 14 23 15
one trip 13 17 20 28 42 14 23 15
one trip 13 14 17 20 28 42 23 15
one trip 13 14 17 20 23 28 42 15
one trip 13 14 15 17 20 23 28 42
after sorted: 13 14 15 17 20 23 28 42original array: 1 8 3 6 5 4 7 2 9
one trip 1 8 3 6 5 4 7 2 9
one trip 1 3 8 6 5 4 7 2 9
one trip 1 3 6 8 5 4 7 2 9
one trip 1 3 5 6 8 4 7 2 9
one trip 1 3 4 5 6 8 7 2 9
one trip 1 3 4 5 6 7 8 2 9
one trip 1 2 3 4 5 6 7 8 9
one trip 1 2 3 4 5 6 7 8 9
after sorted: 1 2 3 4 5 6 7 8 9original array: 8 8 6 6 7 5 5 7 9 9
one trip 8 8 6 6 7 5 5 7 9 9
one trip 6 8 8 6 7 5 5 7 9 9
one trip 6 6 8 8 7 5 5 7 9 9
one trip 6 6 7 8 8 5 5 7 9 9
one trip 5 6 6 7 8 8 5 7 9 9
one trip 5 5 6 6 7 8 8 7 9 9
one trip 5 5 6 6 7 7 8 8 9 9
one trip 5 5 6 6 7 7 8 8 9 9
one trip 5 5 6 6 7 7 8 8 9 9
after sorted: 5 5 6 6 7 7 8 8 9 9

相关文章:

插入排序(Insertion Sort)

C自学精简教程 目录(必读) 插入排序 每次选择未排序子数组中的第一个元素&#xff0c;从后往前&#xff0c;插入放到已排序子数组中&#xff0c;保持子数组有序。 打扑克牌&#xff0c;起牌。 输入数据 42 20 17 13 28 14 23 15 执行过程 完整代码 #include <iostream…...

2023蓝帽杯初赛

最近打完蓝帽杯 现在进行复盘 re 签到题 直接查看源代码 输出的内容就是 变量s 变量 number 而这都是已经设定好了的 所以flag就出来了 WhatisYourStory34982733 取证 案件介绍 取证案情介绍&#xff1a; 2021年5月&#xff0c;公安机关侦破了一起投资理财诈骗类案件&a…...

风险评估

风险评估概念 风险评估是一种系统性的方法&#xff0c;用于识别、评估和量化潜在的风险和威胁&#xff0c;以便组织或个人能够采取适当的措施来管理和减轻这些风险。 风险评估的目的 风险评估要素关系 技术评估和管理评估 风险评估分析原理 风险评估服务 风险评估实施流程...

直播软件app开发中的AI应用及前景展望

在当今数字化时代&#xff0c;直播市场蓬勃发展&#xff0c;而直播软件App成为人们获取实时信息和娱乐的重要渠道。随着人工智能&#xff08;AI&#xff09;技术的迅猛发展&#xff0c;直播软件App开发正逐渐融入AI的应用&#xff0c;为用户带来更智能、更个性化的直播体验。 …...

vscode html使用less和快速获取标签less结构

扩展插件里面搜索 css tree 插件 下载 使用方法 选择你要生成的标签结构然后按CTRLshiftp 第一次需要在输入框输入 get 然后选择 Generate CSS tree less结构就出现在这个里面直接复制到自己的less文件里面就可以使用了 在html里面使用less 下载 Easy LESS 插件 自己创建…...

excel中的引用与查找函数篇1

1、COLUMN(reference)&#xff1a;返回与列号对应的数字 2、ROW(reference)&#xff1a;返回与行号对应的数字 参数reference表示引用/参考单元格&#xff0c;输入后引用单元格后colimn()和row()会返回这个单元格对应的列号和行号。若参数reference没有引用单元格&#xff0c;…...

【python】—— 函数详解

前言&#xff1a; 本期&#xff0c;我们将要讲解的是有关python中函数的相关知识&#xff01;&#xff01;&#xff01; 目录 &#xff08;一&#xff09;函数是什么 &#xff08;二&#xff09;语法格式 &#xff08;三&#xff09;函数参数 &#xff08;四&#xff09;函…...

springboot web开发登录拦截器

在SpringBoot中我们可以使用HandlerInterceptorAdapter这个适配器来实现自己的拦截器。这样就可以拦截所有的请求并做相应的处理。 应用场景 日志记录&#xff0c;可以记录请求信息的日志&#xff0c;以便进行信息监控、信息统计等。权限检查&#xff1a;如登陆检测&#xff…...

大数据课程K17——Spark的协同过滤法

文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 了解Spark的协同过滤概念; 一、协同过滤概念 1. 概念 协同过滤是一种借助众包智慧的途径。它利用大量已有的用户偏好来估计用户对其未接触过的物品的喜好程度。其内在思想是相似度的定义…...

【力扣】1588. 所有奇数长度子数组的和 <前缀和>

【力扣】1588. 所有奇数长度子数组的和 给你一个正整数数组 arr &#xff0c;请你计算所有可能的奇数长度子数组的和。子数组 定义为原数组中的一个连续子序列。请你返回 arr 中 所有奇数长度子数组的和 。 示例 1&#xff1a; 输入&#xff1a;arr [1,4,2,5,3] 输出&#x…...

socket,tcp,http三者之间的原理和区别

目录 1、TCP/IP连接 2、HTTP连接 3、SOCKET原理 4、SOCKET连接与TCP/IP连接 5、Socket连接与HTTP连接 socket&#xff0c;tcp&#xff0c;http三者之间的区别和原理 http、TCP/IP协议与socket之间的区别 下面的图表试图显示不同的TCP/IP和其他的协议在最初OSI模型中的位置…...

【FPGA零基础学习之旅#11】数码管动态扫描

&#x1f389;欢迎来到FPGA专栏~数码管动态扫描 ☆* o(≧▽≦)o *☆嗨~我是小夏与酒&#x1f379; ✨博客主页&#xff1a;小夏与酒的博客 &#x1f388;该系列文章专栏&#xff1a;FPGA学习之旅 文章作者技术和水平有限&#xff0c;如果文中出现错误&#xff0c;希望大家能指正…...

JavaExcel:自动生成数据表并插入数据

故事背景 出于好奇&#xff0c;当下扫描excel读取数据进数据库 or 导出数据库数据组成excel的功能层出不穷&#xff0c;代码也是前篇一律&#xff0c;poi或者easy excel两种SDK的二次利用带来了各种封装方法。 那么为何不能直接扫描excel后根据列的属性名与行数据的属性建立S…...

哪吒汽车“三头六臂”之「浩智电驱」

撰文 / 翟悦 编审 / 吴晰 8月21日&#xff0c;在哪吒汽车科技日上&#xff0c;哪吒汽车发布“浩智战略2025”以及浩智技术品牌2.0。根据公开信息&#xff0c;主编梳理了以下几点&#xff1a;◎浩智滑板底盘支持400V/800V双平台◎浩智电驱包括180kW 400V电驱系统和250kW 800…...

补码的反码加1为什么是原码?

搞了半个小时&#xff0c;终于弄懂了。 168421原码10011反码01100补码01101 学到这里了&#xff0c;我们肯定知道&#xff0c;原码补码 0&#xff0c;在这里也就是 19 13 32&#xff0c;溢出来的一位正好舍去了&#xff1b; 所以说&#xff0c;对啊&#xff0c;只要保证…...

光刻机是怎么做出来的

文章目录 一、光刻机的基本原理二、光刻机的制造过程三、光刻机的制造要求四、光刻机的发展趋势 光刻机是半导体工艺制造中非常重要的设备之一&#xff0c;它是用来制作微细结构的关键工具之一。相信大家都知道&#xff0c;半导体工艺中最小的制造单位是晶体管&#xff0c;而制…...

CocosCreator3.8研究笔记(二)windows环境 VS Code 编辑器的配置

一、设置文件显示和搜索过滤步骤 为了提高搜索效率以及文件列表中隐藏不需要显示的文件&#xff0c; VS Code 需要设置排除目录用于过滤。 比如 cocoscreator 中&#xff0c;编辑器运行时会自动生成一些目录&#xff1a;build、temp、library&#xff0c; 所以应该在搜索中排除…...

Rust--流程控制

循环/判断 ref: 流程控制 - Rust语言圣经(Rust Course) 判断 if condition true {// A... } else {// B... }if 语句块是表达式&#xff0c;所以可以为变量赋值&#xff0c;当然要注意的是保证返回的类型相同&#xff1a; fn main() {let condition true;let number if c…...

mate60的麒麟9000s和麒麟9000是一款CPU吗

答案&#xff1a;不是 论证&#xff1a; 1.在核心方便9000是1个高频A77&#xff0c;3个低频A77&#xff0c;4个A55组成的。9000S是2个高频A34核心&#xff0c;6个定制A78AE核心和4个A510核心并搭载超线程技术&#xff08;详见新华网新华网地址&#xff09; 2.GPU截然不同&am…...

查漏补缺 - JS三 WebAPI

目录 BOMhistory DOM操作DOM1&#xff0c;dom.children 和 dom.childNodes 区别2&#xff0c;dom.remove()3&#xff0c;其他常用 API DOM 属性1&#xff0c;标准属性2&#xff0c;自定义属性 DOM 内容DOM样式DOM事件 JavaScript 包括 EcmaScript 和 WebAPI EcmaScript 包括 语…...

如何熟练使用vector?

&#x1f388;个人主页:&#x1f388; :✨✨✨初阶牛✨✨✨ &#x1f43b;推荐专栏1: &#x1f354;&#x1f35f;&#x1f32f;C语言初阶 &#x1f43b;推荐专栏2: &#x1f354;&#x1f35f;&#x1f32f;C语言进阶 &#x1f511;个人信条: &#x1f335;知行合一 &#x1f…...

gitlab-rake gitlab:backup:create 执行报错 Errno::ENOSPC: No space left on device

gitlab仓库备份执行 gitlab-rake gitlab:backup:create报错如下&#xff1a; 问题分析&#xff1a;存储备份的空间满 解决方法&#xff1a; 方法1&#xff1a;清理存放路径&#xff0c;删除不需要文件&#xff0c;释放空间。 方法2&#xff1a;创建一个根目录的挂载点&#x…...

【Nginx】负载均衡当其中一台服务器宕机之后

搭建一个简单的负载均衡&#xff0c;然后关闭其中一台再来访问&#xff0c;会发现我们的浏览器卡住一直转圈圈&#xff0c;过了很久才会显示结果。由此我们可以得出结论Nginx负载的时候如果其中一台服务挂掉了&#xff0c;它会把请求转发到另一个可以提供服务的机器&#xff0c…...

每日一题 2511. 最多可以摧毁的敌人城堡数目

难度&#xff1a;简单 翻译&#xff1a;寻找距离最远的 1 和 -1 的组合&#xff0c;要求它们之间只有0 class Solution:def captureForts(self, forts: List[int]) -> int:res, t 0, -1for i, fort in enumerate(forts):if fort -1 or fort 1:if t > 0 and fort ! f…...

NLP(六十七)BERT模型训练后动态量化(PTDQ)

本文将会介绍BERT模型训练后动态量化&#xff08;Post Training Dynamic Quantization&#xff0c;PTDQ&#xff09;。 量化 在深度学习中&#xff0c;量化&#xff08;Quantization&#xff09;指的是使用更少的bit来存储原本以浮点数存储的tensor&#xff0c;以及使用更少的…...

机器学习和数据挖掘04-PowerTransformer与 MinMaxScaler

概念 PowerTransformer&#xff08;幂变换器&#xff09; PowerTransformer 是用于对数据进行幂变换&#xff08;也称为Box-Cox变换&#xff09;的预处理工具。幂变换可以使数据更接近正态分布&#xff0c;这有助于某些机器学习算法的性能提升。它支持两种常用的幂变换&#x…...

1.15 自实现GetProcAddress

在正常情况下&#xff0c;要想使用GetProcAddress函数&#xff0c;需要首先调用LoadLibraryA函数获取到kernel32.dll动态链接库的内存地址&#xff0c;接着在调用GetProcAddress函数时传入模块基址以及模块中函数名即可动态获取到特定函数的内存地址&#xff0c;但在有时这个函…...

总结ADX指标交易的好处

股神巴菲特从一个穷小子变成世界富豪&#xff0c;而闻名世界。anzo capital昂首资本以为这辈子再也不会和巴菲特产生任何交集&#xff0c;直到我看了巴菲特的发家史&#xff0c;才发现原来我们都使用过ADX指标盈利过&#xff0c;下面anzo capital昂首资本就总结一下使用ADX指…...

ConsoleApplication815项目(直接加载+VEH Hook Load)

上线图 ConsoleApplication815.cpp #include <iostream> #include<Windows.h> #include "detours.h" #include "detver.h" #pragma comment(lib,"detours.lib")#pragma warning(disable:4996)LPVOID Beacon_address; SIZE_T Beacon…...

事务(SQL)

事务概述 事务是一组操作的集合&#xff0c;他是一个不可分割的工作单位&#xff0c;事务会把所有的操作作为一个整体一起向西永提交或撤销操作请求。这组操作&#xff0c;要么全部执行成功&#xff0c;要么全部执行失败。 事务操作 查看/设置事务提交方式 -- 查看/设置事务…...