[数据结构]插入排序(全)

ops/2024/10/31 7:24:54/

插入排序分为直接插入排序和希尔排序,希尔排序是在直接插入排序的基础上做出的优化版本(原因后面解释)。

代码如下:

//直接插入排序
void InsertSort(int arr[], int sz)
{for (int i = 0; i < sz - 1; i++){int mark = i;int tmp = arr[mark + 1];while (mark >= 0){if (tmp < arr[mark]){arr[mark + 1] = arr[mark--];}else{break;}arr[mark + 1] = tmp;}}
}
//希尔排序
void ShellSort(int arr[], int sz)
{int gap = sz;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < sz - gap; i++){int mark = i;int tmp = arr[mark + gap];while (mark >= 0){if (tmp < arr[mark]){arr[mark + gap] = arr[mark];mark -= gap;}else{break;}arr[mark + gap] = tmp;}}}
}
//打印数组
void Print(int arr[], int sz)
{for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}

头文件:

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void InsertSort(int arr[], int sz);
void ShellSort(int arr[], int sz);
void Print(int arr[], int sz);

测试:

a6c57051fffc4a78ac1b87260fe6a2f6.png

因为直接插入排序时间复杂度最好是O(n),最坏是O(n^2),最坏情况是排序对象是降序排列的,希尔通过把排列对象划分成若干部分,这些部分内部进行直接插入排序,粗略把排序对象排列成升序,从而优化排序过程,也即是希尔把直接插入排序的最坏情况避免了。

谢谢观看!

 


http://www.ppmy.cn/ops/129805.html

相关文章

无人机避障——4D毫米波雷达从PCD点云到二维栅格地图

本文旨在以 4D 毫米波雷达的 PCD 点云格式文件为基础&#xff0c;直接生成可用于后续无人机路径规划、能提供雷达感知环境的 2D 导航地图文件PGM&#xff0c;从而为无人机在相关环境中的飞行路径规划等操作提供有力的基于雷达感知的环境信息支撑。 安装PCD转PGM代码 代码来自…

重生之我在Java世界------学工厂设计模式

文章目录 为什么需要工厂模式&#xff1f;简单工厂模式&#xff1a;第一步改进实际应用场景(常见场景)1. 数据库连接的创建2. 支付方式的处理 工厂模式的优势注意事项总结 在日常开发工作中&#xff0c;我们经常需要创建对象。随着项目的发展&#xff0c;对象创建的逻辑可能变得…

redis详细教程(5.AOP和RDB持久化)

AOF&#xff08;Append Only File&#xff09;日志和RDB&#xff08;Redis Database Backup&#xff09;持久化是Redis中两种重要的数据持久化机制。 RDB持久化机制原理RDB是Redis提供的一种数据快照保存机制&#xff0c;它将某个时间点的数据库状态保存到一个RDB文件中。这个…

算法定制LiteAIServer视频智能分析软件的过亮、过暗及抖动检测应用场景

在现代社会中&#xff0c;视频监控系统扮演着举足轻重的角色&#xff0c;其视频质量直接关乎监控系统的可靠性与有效性。算法定制LiteAIServer通过引入抖动检测和过亮过暗检测功能&#xff0c;为视频监控系统的稳定性和用户体验带来了显著提升。 以下是对这两种功能的技术实现、…

macOS Sonoma 14.7.1 (23H222) Boot ISO 原版可引导镜像下载

macOS Sonoma 14.7.1 (23H222) Boot ISO 原版可引导镜像下载 2024 年 10 月 28 日&#xff0c;Apple 智能今日登陆 iPhone、iPad 和 Mac。用户现可借助 Apple 智能优化写作&#xff0c;为通知、邮件和消息生成摘要&#xff0c;体验交互更自然、功能更丰富的 Siri&#xff0c;使…

Diving into the STM32 HAL-----Interrupts

硬件管理就是处理异步事件。其中大部分来自硬件外围设备。例如&#xff0c;计时器达到配置的 period 值&#xff0c;或者 UART 在数据到达时发出警告。 中断是一个异步事件&#xff0c;它会导致按优先级停止执行当前代码&#xff08;中断越重要&#xff0c;其优先级越高;这将导…

目录遍历漏洞

目录遍历 目录 概念漏洞分析 加密型传递参数编码绕过目录限定绕过绕过文件后缀过滤(截断上传原理) 漏洞挖掘 访问图片文件测试时去掉文件名只访问目录路径搜索引擎谷歌关键字 pikachu目录遍历 目录遍历与任意文件下载其实差不多,但是如果目录遍历比如etc/passwd只能看不能下…

MySQL安装配置教程

以下是 MySQL 在 Windows 系统下的安装配置教程: 1. 下载 MySQL 访问 MySQL 官方网站(https://dev.mysql.com/downloads/mysql/),根据您的操作系统版本(32 位或 64 位)选择合适的 MySQL 安装包。一般建议下载社区版(Community Server),它是免费且功能丰富的版本。2. …