【八大排序】直接插入排序 | 希尔排序 + 图文详解！！

在这里插入图片描述

📷 江池俊： 个人主页
🔥个人专栏： ✅数据结构冒险记 ✅C语言进阶之路
🌅 有航道的人，再渺小也不会迷途。

在这里插入图片描述

文章目录

    • 一、排序的概念
    • 二、直接插入排序
      • 2.1 基本思想
      • 2.2 适用说明
      • 2.3 过程图示
      • 2.4 代码实现
      • 2.5 直接插入排序特性总结
    • 三、希尔排序（缩小增量排序）
      • 3.1 算法步骤
      • 3.2 代码实现
      • 3.3 希尔排序的特性总结

在这里插入图片描述

一、排序的概念

  • 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
  • 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
  • 内部排序：数据元素全部放在内存中的排序。
  • 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

二、直接插入排序

2.1 基本思想

插入排序，一般也被称为直接插入排序。
对于少量元素的排序，它是一个有效的算法。

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想
在这里插入图片描述

2.2 适用说明

插入排序的平均时间复杂度是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性是有关联的。

插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。

2.3 过程图示

在这里插入图片描述

假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第 n 个数的这个序列也是排好顺序的。
按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

从小到大的插入排序整个过程如图示：

第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。
在这里插入图片描述
第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。
在这里插入图片描述
第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。
在这里插入图片描述
第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。
在这里插入图片描述
…

就这样依次比较到最后一个元素。

最终效果：
在这里插入图片描述

2.4 代码实现

// 直接插入排序
// 时间复杂度：O(N^2) 逆序
// 最好的情况：O(N)  顺序有序
void InsertSort(int* a, int n)
{// [0, end] end+1for (int i = 0; i < n - 1; i++){int end = i;int temp = a[end + 1]; while (end >= 0) {if (temp < a[end]){ a[end + 1] = a[end]; --end; }else{break;}}a[end + 1] = temp; }	
}void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestInsertSort()
{int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestInsertSort();return 0;
}

2.5 直接插入排序特性总结

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)，它是一种稳定的排序算法
  4. 稳定性：稳定

三、希尔排序（缩小增量排序）

希尔排序，也称缩小增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：首先选择一个整数作为增量（gap），将待排序序列分成若干个子序列，每个子序列的元素之间距离为增量。然后对每个子序列进行插入排序。接下来，逐渐减小增量，重复上述分组和排序的过程。当增量减小到 1 时（就是直接插入排序），所有记录都在同一组内排好序。

在这里插入图片描述

3.1 算法步骤

希尔排序的算法步骤可以分为以下两步：

  1. 预排序：这一步的目的是通过分组和子序列排序，使整个数组接近有序。
    • 选择一个初始的增量gap。
    • 将数组分成若干个子数组，每个子数组的元素之间的距离为gap。
    • 对每个子数组进行直接插入排序。随着增量的减小，子数组之间的距离会逐渐缩短。
  2. 直接插入排序：当增量减至 1 时，对整个数组进行直接插入排序，使数组完全有序。

希尔排序的时间复杂度与初始增量gap的选择和减小策略有关。选择合适的增量序列可以使得希尔排序的性能接近于最佳可能的线性时间复杂度。当前gap的减小策略以gap = gap/3 + 1较好，其它减小策略如：gap = gap/2 也可行，但唯一一点就是要保证最后gap的值最终能够减小到 1。

3.2 代码实现

 希尔排序
//void ShellSort(int* a, int n)
//{
//	int gap = n;
//
//	// gap > 1时是预排序，目的让数组接近有序
//	// gap == 1是直接插入排序，目的是让数组有序
//	while (gap > 1)
//	{
//		//gap = gap / 2;
//		gap = gap / 3 + 1;
//		// 一组一组排
//		for (int j = 0; j < gap; j++)
//		{
//			for (int i = j; i < n - gap; i += gap)
//			{
//				int end = i;
//				int temp = a[end + gap];
//				while (end >= 0)
//				{
//					if (temp < a[end])
//					{
//						a[end + gap] = a[end];
//						end -= gap;
//					}
//					else
//					{
//						break;
//					}
//				}
//				a[end + gap] = temp;
//			}
//		}
//	}
//}// 希尔排序（优化为多组并排，减少一层循环，关键在于i的变化）
// O(N^1.3)
void ShellSort(int* a, int n)
{int gap = n;// gap > 1时是预排序，目的让数组接近有序// gap == 1是直接插入排序，目的是让数组有序while (gap > 1){// 保证最后gap的结果为1//gap = gap / 2;gap = gap / 3 + 1;// 多组并排for (int i = 0; i < n - gap; i++){int end = i; int temp = a[end + gap]; while (end >= 0){if (temp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}}
}void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestShellSort()
{int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestShellSort();return 0;
}

3.3 希尔排序的特性总结

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

    • 《数据结构(C语言版)》— 严蔚敏
      在这里插入图片描述

    • 《数据结构-用面相对象方法与C++描述》— 殷人昆
      在这里插入图片描述

  4. 稳定性：不稳定，因为在分组时无法保证相同的值被分在同一组，所以在与排序时有可能发生相同的值对应位置的变化。

【八大排序】系列正在火热跟新中，大家敬请期待！！💖

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

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

相关文章

华为配置ARP安全综合功能实验

华为配置ARP安全综合功能实验

配置ARP安全综合功能示例 组网图形 图1 配置ARP安全功能组网图 ARP安全简介配置注意事项组网需求配置思路操作步骤配置文件 ARP安全简介 ARP&#xff08;Address Resolution Protocol&#xff09;安全是针对ARP攻击的一种安全特性&#xff0c;它通过一系列对ARP表项学习和A…
阅读更多...
Docker 基础篇

Docker 基础篇

目录 一、Docker 简介 1. Docker 2. Linux 容器 3. 传统虚拟机和容器的对比 4. Docker 的作用 5. Docker 的基本组成&#xff08;Docker 三要素&#xff09; 6. Docker 工作原理 7. Docker 架构 8. Docker 下载 二、Docker 安装 1. CentOS Docker 安装 2. CentOS8 …
阅读更多...
beep蜂鸣器驱动实验-创建蜂鸣器的设备节点

beep蜂鸣器驱动实验-创建蜂鸣器的设备节点

一. 简介 前面我借助 pinctrl 和 gpio 子系统编写了 LED 灯驱动。 I.MX6U-ALPHA 开发板上还有一个蜂鸣器&#xff0c;从软件的角度考虑&#xff0c;蜂鸣器驱动和 LED 灯驱动其实是相同的&#xff0c;都是控制 IO 输出高低电平。接下来我们就来学习编写蜂鸣器的 Linux 驱动。…
阅读更多...
5、应急响应-拒绝服务钓鱼识别DDOS压力测试邮件反制分析应用日志

5、应急响应-拒绝服务钓鱼识别DDOS压力测试邮件反制分析应用日志

目录 前言&#xff1a; 1、#内网应急-日志分析-爆破&横向&数据库 2、#红队APT-钓鱼邮件识别-内容&发信人&附件 3、#拒绝服务攻击-DDOS&CC-代理&防火墙防御 用途&#xff1a;个人学习笔记&#xff0c;欢迎指正&#xff01; 前言&#xff1a; 了解和…
阅读更多...
上海纽约大学信息技术部高级主任常潘：解密大数据引领的未来教育革命

上海纽约大学信息技术部高级主任常潘：解密大数据引领的未来教育革命

大数据产业创新服务媒体 ——聚焦数据 改变商业 在数字化时代&#xff0c;大数据技术的应用已经深刻地改变着各行各业。特别是在教育领域&#xff0c;智慧校园建设作为现代化校园的代名词&#xff0c;正迎来大数据技术的巨大机遇。 1月17日&#xff0c;上海纽约大学信息技术部…
阅读更多...
数据结构之红黑树

数据结构之红黑树

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 红黑树基础 前言一、什么是红黑树二、左旋和右旋实现三、插入的调整四、红黑树的删除1.引入库2.读入数据 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&…
阅读更多...
dockerpipwork相关测试过程

dockerpipwork相关测试过程

pipework可以减轻docker实施过程中的工作量&#xff0c;在网上也找了几篇类似的文章&#xff0c;按照相应配置&#xff0c;结果并不相同 如下测试过程记录下&#xff1a; docker run -it --rm --name c1 busybox docker run -it --rm --name c2 busyboxpipework br1 c1 192…
阅读更多...
AD24-固定孔放置

AD24-固定孔放置

1、固定孔放置的一般距离&#xff0c;分为金属和非金属 2、固定孔通过焊盘完成&#xff0c;放置焊盘&#xff0c;并将层修改为Multi Layer 焊盘与固定孔的等大小的 3、金属与非金属的区别 ①非金属 ②金属 4、设置固定孔放置的距离 5、通过复制粘贴即可完成其他孔的放置 6、导…
阅读更多...
【机器学习】正则化

【机器学习】正则化

正则化是防止模型过拟合的方法&#xff0c;它通过对模型的权重进行约束来控制模型的复杂度。 正则化在损失函数中引入模型复杂度指标&#xff0c;利用给W加权值&#xff0c;弱化了数据的噪声&#xff0c;一般不正则化b。 loss(y^,y)&#xff1a;模型中所有参数的损失函数&…
阅读更多...
Linux下安装openresty

Linux下安装openresty

Linux下安装openresty 十一、Linux下安装openresty11.1.概述11.2.下载OpenResty并安装相关依赖&#xff1a;11.3.使用wget下载:11.4.解压缩:11.5.进入OpenResty目录:11.6.编译和安装11.7.进入OpenResty的目录&#xff0c;找到nginx&#xff1a;11.8.在sbin目录下启动nginx11.9.…
阅读更多...
PySimpleGUI 综合应用｜英语文本朗读以及转换为语音Mp3

PySimpleGUI 综合应用｜英语文本朗读以及转换为语音Mp3

PySimpleGUI 综合应用 目录 PySimpleGUI 综合应用 应用界面 完整代码 所需模块 PySimpleGUI pyttsx3 pyaudio rapidfuzz 字典格式 应用界面 完整代码 英语朗读器.pyw import PySimpleGUI as sg import pyttsx3,pyaudio,pyperclip import os,re,datetime,wave,threa…
阅读更多...
Java List的合并与切分

Java List的合并与切分

在Java开发中经常遇到list结构数据的处理&#xff0c;如List的合并或拆分&#xff0c;记录下来&#xff0c;方便备查。 一、List 合并 两个list数据的合并处理&#xff0c;可使用Java8 新特性的stream流&#xff0c;根据实际需要遍历取值。 1、定义 UserInfo 对象 订单的相…
阅读更多...
【vim 学习系列文章 3.2 -- vim 删除 空格】

【vim 学习系列文章 3.2 -- vim 删除 空格】

文章目录 vim 删除行尾空格 vim 删除行尾空格 在代码开发的过程中&#xff0c;经常会遇到行尾有空格的现象&#xff0c;如下&#xff1a; 我们可以在 .vimrc 中通过map 命令来映射删除行尾空格的快捷键&#xff0c;如下&#xff1a; map d<space> :%s/\s*$//g <cr…
阅读更多...
Redis 学习笔记 2：Java 客户端

Redis 学习笔记 2：Java 客户端

Redis 学习笔记 2&#xff1a;Java 客户端 常见的 Redis Java 客户端有三种&#xff1a; Jedis&#xff0c;优点是API 风格与 Redis 命令命名保持一致&#xff0c;容易上手&#xff0c;缺点是连接实例是线程不安全的&#xff0c;多线程场景需要用线程池来管理连接。Redisson&…
阅读更多...
LVGL部件4

LVGL部件4

一.列表部件 1.知识概览 2.函数接口 1.lv_list_add_btn lv_list_add_btn 是 LittlevGL&#xff08;LVGL&#xff09;图形库中的一个函数&#xff0c;用于向列表&#xff08;list&#xff09;对象中添加一个按钮&#xff08;button&#xff09;。 函数原型为&#xff1a;lv_ob…
阅读更多...
新手不会Git也能玩Github吗？

新手不会Git也能玩Github吗？

新手不会Git也能玩Github吗&#xff1f; 前言使用Github的准备步骤使用一种访问外网资源的方法&#xff08;这一步才是新手最容易&#xff09;注册账号 创建一个自己的仓库创建完仓库后的界面 搜索你想要的代码类型以搜索坦克大战为例以下载烟花代码为例 总结 前言 说到Github&…
阅读更多...
使用Python的Turtle模块简单绘制烟花效果

使用Python的Turtle模块简单绘制烟花效果

import turtle import random# 初始化屏幕 screen turtle.Screen() screen.bgcolor("black") screen.title("烟花模拟")# 创建一个Turtle来绘制烟花 firework turtle.Turtle() firework.hideturtle() firework.speed(0) # 设置绘图速度为最快# 绘制烟花…
阅读更多...
关系型数据库的介绍与历史（History of DataBase）

关系型数据库的介绍与历史（History of DataBase）

昨晚和大家聊到 数据库&#xff08;DataBase&#xff09;简单概述 &#xff0c;今天和大家聊聊 关系型数据库&#xff08;关系数据库&#xff09; 也就是DataBase&#xff08;简称DB&#xff09;的历史&#xff0c;它是以关系模型&#xff08;Relational Model&#xff09;来构…
阅读更多...
C# 多线程（2）——线程同步

C# 多线程（2）——线程同步

目录 1 线程不安全2 线程同步方式2.1 简单的阻塞方法2.2 锁2.2.1 Lock使用2.2.2 互斥体Mutex2.2.3 信号量Semaphore2.2.3 轻量级信号量SemaphoreSlim2.2.4 读写锁ReaderWriterLockSlim 2.3 信号同步2.3.1 AutoResetEvent2.3.1.1 AutoResetEvent实现双向信号 2.3.2 ManualResetE…
阅读更多...
麒麟系统—— openKylin 安装 Nginx

麒麟系统—— openKylin 安装 Nginx

麒麟系统—— openKylin 安装 Nginx 一、准备工作1. 确保麒麟系统 openKylin 已经安装完毕。 二、下载 nginx三、解压与运行解压检查与编译安装编译运行 四、配置加入到服务中加入环境变量nginx 配置文件 五、常用命令 Nginx 是一款高性能的 HTTP 和反向代理服务器&#xff0c…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023