排序算法之插排希尔

算法时间复杂度(最好)时间复杂度(平均)时间复杂度(最差)空间复杂度
插入排序O(n)O(n^2)O(n^2)1
希尔排序O(n)O(n^1.3)O(n^2)

1

1.插入排序

    玩牌时,每得到一张,就要把它插入到之前的牌中,插入排序也是如此,每次都有一个有序的区间,每次都要选取无序区间的第一个元素,把他插入到合适的位置,这时,有序区间的长度+1,直到和序列长度相等为止

代码:

#include<bits/stdc++.h>
using namespace std;
int main() {int n, a[10000];cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {int s = i;while (a[s] < a[s - 1] && (s > 0)) {swap(a[s], a[s - 1]);s --;}}for (int i = 0; i < n; i++) {cout << a[i] << ' ';}return 0;
}

复杂度分析:平均情况:每个元素都要进行插入,要进行n次插入,时间复杂度为O(n*n)

最好情况:近乎有序序列,插入的时间可以忽略不计,时间复杂度:O(n) 

 2.希尔排序

    由他的发明者希尔命名,它会进行多次预排序,使其整体接近有序,每次都是插入排序里的1替换成gap,而gap先从n/2开始,以一定的规律递减,直到一。效率跟增量的序列有关。

时间复杂度:最好,最坏和插入排序一样。

为什么要这么做

        因为gap大时,每一组数据量少,效率高,gap小时,整体接近有序,效率也高。所以整体效率比插入排序高!

#include<bits/stdc++.h>
using namespace std;
int main(){int n,a[10000],gap;cin>>n;gap=n;for(int i=0;i<n;i++){cin>>a[i];}while(gap>=1){gap*=0.6;//找不到其它序列了qwq。。。for(int i=0;i<=n-gap;i++){int s=i;while(a[s]<a[s-gap]&&(s-gap>=0)){a[s]^=a[s-gap];a[s-gap]^=a[s];a[s]^=a[s-gap];s-=gap;}}}for(int i=0;i<n;i++){cout<<a[i]<<' ';}return 0;
}

 

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

babylonjs shader学习之shadertoy案例四

代码 const onSceneReady (scene: Scene) > {(scene.activeCamera as ArcRotateCamera).beta 1.185793134378305;const light new HemisphericLight(light, Vector3.Down(), scene);light.intensity 1;const plane MeshBuilder.CreatePlane(ground, { width: 10, heig…

【机器学习】20. RNN - Recurrent Neural Networks 和 LSTM

1. RNN定义 用于顺序数据 文本数据是序列数据的一个例子 句子是单词的序列——一个单词接另一个单词 每个句子可能有不同数量的单词&#xff08;长度可变&#xff09; 每个句子之间可能有长距离的依赖关系 rnn可以记住序列中较早的相关信息 RNN在每个时间点取序列中的1个…

python-读写Excel:openpyxl-(4)下拉选项设置

使用openpyxl库的DataValidation对象方法可添加下拉选择列表。 DataValidation参数说明&#xff1a; type&#xff1a; 数据类型("whole", "decimal", "list", "date", "time", "textLength", "custom"…

unity发布webGL

1.安装WebGL板块 打开unity&#xff0c;进入该界面&#xff0c;然后选择圈中图标 选择添加模块 选择下载WebGL Build Support 2.配置项目设置 打开一个unity项目&#xff0c;如图进行选择 如图进行操作 根据自己的情况进行配置&#xff08;也可直接点击构建和运行&#xff09…

基于势能的平面运动模拟

运动模拟 接前面递归调用——单向汉诺塔七边形最小分割弦 F m a Fma Fma F m a m d 2 r d t 2 F ma m \frac{{{d^2}\ r}}{{d{t^2}}} Fmamdt2d2 r​ F k Q q r 2 r ^ F k \frac{{Qq}}{{{r^2}}} \hat{r} Fkr2Qq​r^代码电荷的位置和值运动电荷的初始位置和速度计算距离计算…

SpringBoot在线教育系统:数据分析与报告

4系统概要设计 4.1概述 本系统采用B/S结构(Browser/Server,浏览器/服务器结构)和基于Web服务两种模式&#xff0c;是一个适用于Internet环境下的模型结构。只要用户能连上Internet,便可以在任何时间、任何地点使用。系统工作原理图如图4-1所示&#xff1a; 图4-1系统工作原理…

Linux开发工具——make/Makefile

目录 一、什么是makefile&#xff1f; 二、为什么要有makefile&#xff1f; 三、makefile的使用 1.依赖关系与依赖方法 2.伪目标 3.定义变量 4.特殊符号 四、makefile的执行逻辑 一、什么是makefile&#xff1f; Makefile是一种自动化构建工具&#xff0c;make是一条指…

BC146 添加逗号

BC146 添加逗号 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);String str in.next();StringBuilder s new StringBuilder(str);for(int …

【计算机视觉】深入浅出SLAM技术原理

引言 SLAM&#xff08;Simultaneous Localization and Mapping&#xff0c;同步定位与建图&#xff09;是机器人学和计算机视觉中的一个重要技术&#xff0c;它允许机器人在未知环境中自主导航&#xff0c;同时构建环境的地图并确定自身的精确位置。本文将详细介绍SLAM技术的基…

求平面连接线段组成的所有最小闭合区间

这个功能确实非常实用&#xff0c;我在过去开发地面分区编辑器时就曾应用过这一算法。最近&#xff0c;在新产品的开发中再次遇到了类似的需求。尽管之前已经实现过&#xff0c;但由于长时间未接触&#xff0c;对算法的具体细节有所遗忘&#xff0c;导致重新编写时耗费了不少时…

如何才能实时监测Mac的运行状态

实时监测Mac的运行状态&#xff0c;能够让我们更好的了解Mac的情况&#xff0c;因此如何才能监测Mac的运行状态很重要 State&#xff0c;实时监测你的Mac运行状态&#xff0c;能够直观的展示当前Mac的CPU、内存、硬盘、温度、风扇、网络信息以及开机时间等重要信息 除此之外&a…

强化学习介绍

目录标题 一、什么是强化学习二、强化学习的环境三、强化学习的目标四、强化学习中的数据从哪里来五、强化学习的独特性 一、什么是强化学习 强化学习是机器通过与环境交互来实现目标的一种计算方法。 机器和环境的一轮交互是指&#xff0c;机器在环境的一个状态下做一个动作决…

【算法】【优选算法】滑动窗口(上)

目录 一、滑动窗口简介二、209.⻓度最⼩的⼦数组2.1 滑动窗口2.2 暴力枚举 三、3.⽆重复字符的最⻓⼦串3.1 滑动窗口3.2 暴力枚举 四、1004.最⼤连续1的个数III4.1 滑动窗口4.2 暴力枚举 五、1658.将x减到0的最⼩操作数5.1 滑动窗口5.2 暴力枚举 一、滑动窗口简介 其实就是利用…

软考高级之系统架构师系列之构件开发模型

如标题所述&#xff0c;本文面向于软考高级&#xff0c;具体来说是系统架构师。 有些概念&#xff0c;如生命周期&#xff0c;开发的几个阶段&#xff0c;不同的教程有些许出入。 本文偏理论&#xff0c;要在理解的基础上加以记忆&#xff0c;用于应付软考&#xff0c;有些地…

机器人零位、工作空间、坐标系及其变换,以UR5e机器人为例

机器人中的主要坐标系 在机器人中&#xff0c;常用的坐标系包括&#xff1a; 基坐标系&#xff08;Base Frame&#xff09;&#xff1a;固定在机器人基座上的坐标系&#xff0c;用于描述机器人的整体位置和方向&#xff0c;是其他所有坐标系的参考点。 连杆坐标系&#xff08…

VMWARE ESXI VMFS阵列故障 服务器数据恢复

1&#xff1a;河南用户一台DELL R740 3块2.4T硬盘组的RAID5&#xff0c;早期坏了一个盘没有及时更换&#xff0c;这次又坏了一个&#xff0c;导致整组RAID5处于数据丢失的状态&#xff0c; 2&#xff1a;该服务器装的是VMware ESXI 6.7&#xff0c;用户把3块硬盘寄过来进行数据…

程序员开发速查表

作为一名苦逼的程序员&#xff0c;在开发的过程中&#xff0c;我们总是在各种编程语言中来回穿梭&#xff0c;忙完后端整前端&#xff0c;还得做一部分的运维工作&#xff0c;忙的我们有时候忘记语法&#xff0c;忘记编写规则&#xff0c;甚至混淆。这时候我们就希望有一个综合…

「Mac畅玩鸿蒙与硬件30」UI互动应用篇7 - 简易计步器

本篇将带你实现一个简易计步器应用&#xff0c;用户通过点击按钮增加步数并实时查看步数进度&#xff0c;目标步数为 10000 步。该项目示例展示了如何使用 Progress 组件和 Button 组件&#xff0c;并结合状态管理&#xff0c;实现交互式应用。 关键词 UI互动应用计步器Button…

直播系统搭建教程安装说明

需要安装的软件(宝塔【软件商店】中查找安装): 1.PHP7.0 ~ PHP7.3 需要安装的扩展:(宝塔【PHP管理】【安装扩展】中安装) *PDO PHP Extension * MBstring PHP Extension * CURL PHP Extension * Mylsqi PHP Extension * Redis PHP Extension * fileinfo PHP Extension …

@Async注解提升Spring Boot项目中API接口并发能力

文章目录 同步调用异步调用1: 启用异步支持2: 修改 Task 类异步回调基本概念使用 Future<String>使用 CompletableFuture<String>Future<String> 和 CompletableFuture<String>区别1. 基本概念2. 主要区别同步调用 同步调用是最直接的调用方式,调用方…