C语言分析基础排序算法——插入排序

目录

插入排序

直接插入排序

希尔排序

希尔排序基本思路解析

希尔排序优化思路解析

完整希尔排序文件


插入排序

直接插入排序

所谓直接插入排序,即每插入一个数据和之前的数据进行大小比较,如果较大放置在后面,较小放置在前面,具体思路分析如下:

//以下面的数组为例
int data[] = { 23,34,84,99,67,26,21,89 };

参考代码

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>void DirectInsert_sort(int* data, int sz)
{// 遍历数组for (int i = 1; i < sz; i++){int tmp = data[i];//获取数组的当前元素int end = i - 1;//获取数组的当前元素的上一个元素//当遇到比tmp大数值时,挪动数据,直到遇到比当前数据小的数据时跳出循环while (end >= 0){if (data[end] > tmp){data[end + 1] = data[end];end--;}else{break;}}//在end的后一个位置插入数据,插入完毕后直接更新i和end继续比较data[end + 1] = tmp;}
}int main()
{int data[] = { 23,34,84,99,67,26,21,89 };int sz = sizeof(data) / sizeof(int);DirectInsert_sort(data, sz);//打印排序后的数组for (int i = 0; i < sz; i++){printf("%d ", data[i]);}return 0;
}
输出结果:
21 23 26 34 67 84 89 99

通过分析可以得出直接插入排序在最坏的情况下(数据为完全逆序的状态)时间复杂度为O(N2),而在最好的情况下(已经为有序状态,只需要遍历一遍数据即可),时间复杂度为O(N)

希尔排序

希尔排序基本思路解析

希尔排序的基本思路是将一组数据按照间隔值gap分成gap组,对各组进行插入排序,这一步被称作预排序,接着再使用直接插入排序对整体再进行一次排序,具体过程如下

//希尔排序基础思路
void ShellSort(int* data, int sz)
{int gap = 3;//首先进行三组预排序for (int i = 0; i < gap; i++){//每一组的排序for (int j = gap + i; j < sz; j += gap){int end = j - gap;int tmp = data[j];while (end >= 0){if (data[end] > tmp){data[end + gap] = data[end];end -= gap;}else{break;}}data[end + gap] = tmp;}}//最后进行整体插入排序gap = 1;for (int i = gap; i < sz; i += gap){int end = i - 1;int tmp = data[i];while (end >= 0){if (data[end] > tmp){data[end + gap] = data[end];end--;}else{break;}}data[end + gap] = tmp;}
}

希尔排序优化思路解析

以上思路只是简单的分析,接下来对细节进行分析优化,具体思路如下

首先是间隔值gapgap决定了分组的数量,也间接决定了最大值走到最后需要的次数,当gap特别大时,最大值很快就会到数据的最末尾,但是同时整体越不接近需要的升序;相反,当gap特别小时,最大值到数据末尾的次数变多,同时整体越接近有序,所以gap数值不容易确定,但是一般取gap为整体的1/3或者取1/2,即gap = size / 3gap = size / 2 (size是数组长度)

第二个问题,如果将预排序和最后的插入排序分开写,那么需要写五个循环,三层循环解决预排序,两层循环解决最后的插入排序,所以可以考虑将预排序与直接插入排序放在一起,达到在同一个循环中解决问题

可以考虑将每一次循环变量移动的位置改为移动一位,代替原来的一次移动gap位,如下图所示

而改进后的思路与原来的思路对比:原来的思路是先排一组,排完一组后再排第二组,而改进后的思路是遇到i当前位置是哪一组的就排哪一组的数据,但是需要注意的是,当前的tmp所在位置为下一个相差gap的位置,该位置需要有确切的数值可以与end进行比较,所以tmp不能越界,假设当前tmp为3,数组最大下标为7,也就是tmp所在的下标最大只能为7,即i + gap不能超过7,故i最大只能为4,所以i不能超过5

接下来是如何处理预排序和之后的直接排序放在一起的问题,对于这个问题,首先就是gap不能为一个固定值,如果gap为固定的某一个数值,例如3,那么预排序和直接插入排序还是需要两组循环才能解决,鉴于gap最后需要回到1,可以考虑从gap/3分组开始,当预排序完gap为3的一组时,接下来排gap为2的一组,最后着排gap为1的一组,因为第一次gap为3时已经将数据处理了一遍,而gap数值越小,就会使预排序的结果更接近预期的排序结果,所以可以考虑gap = gap / 3,每执行完一次预排序就更换一次gap间隔值,从而达到预排序与最后的直接插入排序放在一起,因为当gap为1时也可以满足预排序的思路,故放在一起也不会有任何冲突,只是间隔值从3变成了1,但是需要注意一个问题,当gap小于3时,gap最后的商为0,导致gap无法取到1,所以需要写成gap = gap / 3 + 1

//希尔排序优化思路
void ShellSort_modified(int* data, int sz)
{int gap = sz;while (gap > 1){gap = gap / 3 + 1;// 此处加1是为了确保最后一个gap一定为1,因为最后的直接插入排序是整体各自比较for (int i = 0; i < sz - gap; i++){int end = i;int tmp = data[i + gap];while (end >= 0){if (data[end] > tmp){data[end + gap] = data[end];end -= gap;}else{break;}}data[end + gap] = tmp;}}    
}

完整希尔排序文件

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>//希尔排序优化思路
void ShellSort_modified(int* data, int sz)
{int gap = sz;while (gap > 1){gap = gap / 3 + 1;// 此处加1是为了确保最后一个gap一定为1,因为最后的直接插入排序是整体各自比较for (int i = 0; i < sz - gap; i++){int end = i;int tmp = data[i + gap];while (end >= 0){if (data[end] > tmp){data[end + gap] = data[end];end -= gap;}else{break;}}data[end + gap] = tmp;}}    
}int main()
{int data[] = { 23,34,84,99,67,26,21,89 };int sz = sizeof(data) / sizeof(int);ShellSort_modified(data, sz);for (int i = 0; i < sz; i++){printf("%d ", data[i]);}return 0;
}
输出结果:
21 23 26 34 67 84 89 99

希尔排序总结:

  1. 希尔排序是对直接插入排序的优化
  2. gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定

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

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

相关文章

LeetCode-102.题: 二叉树的层序遍历(原创)

【题目描述】 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]] 【题目链接…

【ICCV21】Swin Transformer: Hierarchical Vision Transformer using Shifted Windows

文章目录 0. Abstract1. Introduction2. Related Work3. Method3.1 Overall Architecture3.2 Shifted Window based Self-Attention3.3 Architecture Variants 4. Experiments4.1 Image Classification on ImageNet-1K4.2 Object Detection on COCO4.3 Semantic Segmentation o…

文本向量评测MTEB和C-MTEB

文章目录 简介MTEBC-MTEB参考资料 简介 MTEB(Massive Text Embedding Benchmark)是目前评测文本向量很重要的一个参考&#xff0c;其榜单也是各大文本向量模型用来展示与其他向量模型强弱的一个竞技台。 C-MTEB则是专门针对中文文本向量的评测基准。 MTEB MTEB的目的是为了…

OKLink2月安全月报| 2起典型漏洞攻击案例分析

在本月初我们发布的2024年2月安全月报中提到&#xff0c;2月全网累计造成损失约1.03亿美元。其中钓鱼诈骗事件损失占比11.76%。 OKLink提醒大家&#xff0c;在参与Web3项目时&#xff0c;应当仔细调研项目的真实性、可靠性&#xff0c;提升对钓鱼网站和风险项目的甄别能力&…

C语言从入门到熟悉------第二阶段

printf的用法 printf的格式有四种&#xff1a; &#xff08;1&#xff09;printf("字符串\n"); 其中\n表示换行的意思。其中n是“new line”的缩写&#xff0c;即“新的一行”。此外需要注意的是&#xff0c;printf中的双引号和后面的分号必须是在英文输入法下。双引…

portainer管理远程docker和docker-swarm集群

使用前请先安装docker和docker-compose&#xff0c;同时完成docker-swarm集群初始化 一、portainer-ce部署 部署portainer-ce实时管理本机docker&#xff0c;使用docker-compose一键拉起 docker-compose.yml version: 3 services:portainer:container_name: portainer#imag…

[机器视觉]halcon应用实例 找圆

[机器视觉]halcon应用实例 找圆 代码 *清空屏幕&#xff0c;显示控制图像 dev_close_window () dev_update_off () read_image (Image, 形状模板图) dev_open_window_fit_image (Image, 0, 0, -1, -1, WindowHandle) dev_display (Image) *创建测量模型 create_metrology_mod…

AD20新建工程步骤

1 新建工程 2 创建 3 新建原理图 4 新建PCB图 5 对原理图贺PCB都进行保存 6 新建原理图库贺PCB库&#xff0c;以及保存 最后在保存位置上都可以看到 打开的时候直接打开工程&#xff0c;它自己就会把这些链接在一起

UVa11595 Crossing Streets EXTREME

题目链接 UVa11595 - Crossing Streets EXTREME 题意 平面上有 n&#xff08;n≤35&#xff09;条直线&#xff0c;各代表一条街道。街道相互交叉&#xff0c;形成一些路段&#xff08;对应于几何上的线段&#xff09;。你的任务是设计一条从A到B的路线&#xff0c;使得穿过路…

c++: 引用能否替代指针? 详解引用与指针的区别.

文章目录 前言1. 引用和指针的最大区别:引用不能改变指向2. 引用和指针在底层上面是一样的3. 引用和指针在sizeof面前大小不同4. 有多级指针,没有多级引用5.引用是引用的实体,指针会向后偏移同一个类型的大小 总结 前言 新来的小伙伴如果不知道引用是什么?可以看我的上一篇文…

AI新工具(20240312) Midjourney官方发布角色一致性功能;免费且开源的简历制作工具;精确克隆语调、控制声音风格

1: Midjourney角色一致性功能 使人物画像在多方面高度一致成为可能。 Midjourney的角色一致性功能的使用方法如下&#xff1a; ⭐在你的输入指令后面加上 --cref URL&#xff0c;其中URL是你选择的角色图像的链接。 ⭐你可以通过 --cw 参数来调整参照的强度&#xff0c;范围…

spring boot 使用 webservice

spring boot 使用 webservice 使用 java 自带的 jax-ws 依赖 如果是jdk1.8,不需要引入任何依赖&#xff0c;如果大于1.8 <dependency><groupId>javax.jws</groupId><artifactId>javax.jws-api</artifactId><version>1.1</version&g…

【Linux】文件缓冲区|理解文件系统

目录 预备知识 观察现象 第一&#xff1a;携带\n&#xff0c;不使用fork()&#xff0c;打印到显示器 第二&#xff1a;携带\n&#xff0c;使用fork()&#xff0c;打印到显示器 第三&#xff1a;携带\n&#xff0c;使用fork()&#xff0c;打印到文件里 第四&#xff1a;不携…

案例分析篇03:一篇文章搞定软考设计模式考点(2024年软考高级系统架构设计师冲刺知识点总结系列文章)

专栏系列文章推荐: 2024高级系统架构设计师备考资料(高频考点&真题&经验)https://blog.csdn.net/seeker1994/category_12593400.html 【历年案例分析真题考点汇总】与【专栏文章案例分析高频考点目录】(2024年软考高级系统架构设计师冲刺知识点总结-案例分析篇-…

IPSec NAT穿越原理

一、IPSec VPN在NAT场景中存在的问题 当某些组网中&#xff0c;有的分支连动态的公网IP地址也没有&#xff0c;只能由网络中的NAT设备进行地址转换&#xff0c;才能访问互联网&#xff0c;然而IPsec是用来保护报文不被修改的&#xff0c;而NAT需要修改报文的IP地址&#xff0c…

十大排序算法(冒泡排序、插入排序、选择排序、希尔排序、堆排序、快排、归并排序、桶排序、计数排序、基数排序)

目录 一、冒泡排序&#xff1a; 二、插入排序&#xff1a; 三、选择排序&#xff1a; 四、希尔排序&#xff1a; 五、堆排序&#xff1a; 六、快速排序&#xff1a; 6.1挖坑法&#xff1a; 6.2左右指针法 6.3前后指针法&#xff1a; 七、归并排序&#xff1a; 八、桶…

力扣hot100:240.搜索二维矩阵II(脑子)

吉大21级算法分析与设计的一道大题&#xff0c;由于每一行都是排好序的直接逐行二分 可以达到&#xff1a;O(mlogn)。但是这里追求更广的思路可以使用其他方法。 矩阵四分&#xff1a; 在矩阵中用中心点比较&#xff0c;如果target大于中心点的值&#xff0c;则由于升序排列&am…

vue学习笔记23-组件事件⭐

组件事件 在组件的模板表达式中&#xff0c;可以直接使用$emit方法触发自定义事件&#xff1b;触发自定义事件的目的是组件之间传递数据 好好好今天又碰到问题了&#xff0c;来吧来吧 测试发现其他项目都可以 正常的run ,就它不行 搜索发现新建项目并进入以后&#xff0c;用指…

C语言--- 指针运算笔试题详解

目录 题目1&#xff1a; 题目2&#xff1a; 题目3&#xff1a; 题目4&#xff1a; 题目5&#xff1a; 题目6&#xff1a; 题目7&#xff1a; 题目1&#xff1a; #include <stdio.h> int main() {int a[5] { 1, 2, 3, 4, 5 };int *ptr (int *)(&a 1);print…

新书推荐|职业教育赛教一体化课程改革系列教材之spark大数据分析

由武汉唯众智创科技有限公司统一规划并参与编写的“职业教育赛教一体化课程改革系列教材”-《spark大数据分析》正式出版上线&#xff0c;(其它八本为《云计算技术与应用》《大数据技术与应用Ⅰ》《网络综合布线》《物联网.NET开发》《物联网嵌入式开发》《物联网移动应用开发》…