排序之插入排序

文章目录

  • 前言
  • 一、直接插入排序
    • 1、基本思想
    • 2、直接插入排序的代码实现
    • 3、直接插入排序总结
  • 二、希尔排序
    • 1、希尔排序基本思想
    • 2、希尔排序的代码实现
    • 3、希尔排序时间复杂度


前言

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


一、直接插入排序

1、基本思想

直接插入排序是一种简单的插入排序法,其基本思想是:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。
例如当有如下一组有序的数组。当分别将10、5、0按照插入排序的思想插入到数组中时,
在这里插入图片描述
此时插入的数据要与数组最后一位进行比较,如果比最后一位大,就插入到数组最后一位的后面;
在这里插入图片描述
如果比数组中最后一位小,就将数组中最后一位元素向后移一位,然后插入的数据与倒数第二个数据进行比较,就这样依次循环下去 。
在这里插入图片描述
如果插入的数据比数组中所有数据都小,此时插入的数据会被插入到数组下标为0的位置,即作为数组的第一个元素。
在这里插入图片描述
上述的操作就是插入排序的单趟排序,即在有序区间,插入一个数使这个区间继续有序。

2、直接插入排序的代码实现

直接写出来插入排序来将数组排序比较困难,我们可以先写出来单趟排序,即当有一个数组的[0,end]有序,把end+1位置的值插入数组中,然后保持数组的[0,end+1]有序。
例如有如下数组。
在这里插入图片描述
此时数组中end+1的值为5,该值小于数组中end位置的值,此时就用tmp记录end+1位置的值,然后将end的值向后移一位,移到end+1位置。然后将end–,此时再将end位置的值与tmp比较。
在这里插入图片描述
此时end位置的值比tmp小,则说明tmp的值就应该插入到end位置之后,此时直接将end+1位置赋值为tmp即可。然后数组中[0,end+1]有序。
在这里插入图片描述
上述就是单趟排序。

void InsertSort(int* arr, int n)
{//[0,end]有序,把end+1位置的值插入,保持有序int end;//将tmp赋值为数组中下标为end+1位置的值int tmp = arr[end + 1];//如果end没有到数组头部,就继续比较while (end >= 0){//如果tmp小于arr[end],就将此时end的数据向后移,然后将end--,使tmp与新的end位置的值比较if (tmp < arr[end]){arr[end + 1] = arr[end];end--;}else{//如果满足条件就跳出循环break;}}//此时end为数组中第一个小于tmp的位置,此时将end+1位置赋值为tmp。//如果当end为-1时,即插入的数据tmp比数组头元素还小,此时end+1刚好为0,即让插入的数据tmp作为新的数组头部。arr[end + 1] = tmp;
}

通过上述的操作我们明白了插入排序排序数组时的单趟操作,当我们有一个长度为n的数组arr时,我们先将end置为0,然后依次将数组首元素之后的元素依次进行插入,当end为n-2时,此时end+1为n-1,即为数组最后一个元素的插入。我们就可以再写一个循环将上面的代码套入其中,并且控制end的值从0到n-2。
在这里插入图片描述

void InsertSort(int* arr, int n)
{int i = 0;//控制end的值,将数组中的元素从首元素后面开始依次进行插入。for (i = 0; i < n-1; i++){//[0,end]有序,把end+1位置的值插入,保持有序int end=i;//将tmp赋值为数组中下标为end+1位置的值int tmp = arr[end + 1];while (end >= 0){//如果tmp小于arr[end],就将此时end的数据向后移,然后将end--,使tmp与新的end位置的值比较if (tmp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}//此时end为数组中第一个小于tmp的位置,此时将end+1位置赋值为tmp。//如果当end为-1时,即插入的数据tmp比数组头元素还小,此时end+1刚好为0,即让插入的数据tmp作为新的数组头部。arr[end + 1] = tmp;}}

3、直接插入排序总结

直接插入排序的特性总结:
1.元素集合越接近有序,直接插入排序算法的时间效率越高
2.时间复杂度:O(N^2)
3.空间复杂度:O(1),它是一种稳定的排序算法
4.稳定性:稳定
直接插入排序的最坏时间复杂度为O(N^2),即当数组为逆序时。
最优时间复杂度为O(N),即当数组为顺序有序/接近顺序有序。

二、希尔排序

由上面总结的直接插入排序的最优时间复杂度可知,当数组的顺序接近有序时,直接插入排序的性能可以得到提高,并且能达到O(N)的级别,而希尔排序就是利用了这一点。

1、希尔排序基本思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成gap个组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。然后gap=gap/gap,取gap,重复上述分组和排序的工作。当到达gap=1时,所有记录在统一组内排好序。
希尔排序分为两步。
1、预排序(接近顺序有序)
2、直接插入排序(有序)
例如有如下的一组逆序的数据。
在这里插入图片描述
假设gap为3,即将该组数据分为如图所示的三组数据,
在这里插入图片描述
然后将这三组数据分别进行直接插入排序,此时该组数据的排序虽然没有达到顺序有序,但是相比于原来的逆序,此时该组数据已经接近顺序有序。
在这里插入图片描述
此时将该组数据总体进行直接插入排序,这样相比于原来逆序时就直接进行直接插入排序,效率提高了很多。并且我们可以看出当gap=1时,此时就是进行直接插入排序。

2、希尔排序的代码实现

我们可以像实现直接插入排序一样,先了解希尔排序的一组数据中的单趟排序。
即将分成的3组数据的红色组数据先进行直接插入排序。
在这里插入图片描述

此时将end+gap位置的值赋值为end位置的值。
在这里插入图片描述
然后end = end - gap,此时end已经为负数,但是end+gap为0,刚好为数组的首位,所以将arr[end+gap]的位置存入tmp,即将tmp插入到数组的首位。
在这里插入图片描述
下列代码就实现了上述的操作。

void ShellSort(int* arr, int n)
{int gap = 3;int end = 0;//将tmp赋值为数组中end位置后gap位置的值int tmp = arr[end + gap];while (end >= 0){//如果tmp的值小于此时end位置的值if (tmp < arr[end]){//就将end+gap位置的值赋值为end位置的值,arr[end + gap] = arr[end];//然后将end向后移gap个距离,继续和tmp比较end -= gap;}else{break;}}//此时end位置的值是小于tmp的,将end+gap位置的值赋值为tmparr[end + gap] = tmp;
}

但是上述代码只是将红色数组中的一个数据完成了直接插入排序,下面我们要将红色数组的数据都进行直接插入排序,则需要加一个循环,然后使end的值每次都向后改变。

void ShellSort(int* arr, int n)
{int gap = 3;int i = 0;for (i = 0; i < n - gap; i += gap){int end = i;//将tmp赋值为数组中end位置后gap位置的值int tmp = arr[end + gap];while (end >= 0){//如果tmp的值小于此时end位置的值if (tmp < arr[end]){//就将end+gap位置的值赋值为end位置的值,arr[end + gap] = arr[end];//然后将end向后移gap个距离,继续和tmp比较end -= gap;}else{break;}}//此时end位置的值是小于tmp的,将end+gap位置的值赋值为tmparr[end + gap] = tmp;}}

上述代码只是将红色数组完成了直接插入排序,但是蓝色数组和紫色数组还没有完成直接插入排序,所以需要再次套入一个循环,将蓝色数组和紫色数组也完成直接插入排序操作。此时才算将gap组数都分别在各自组内进行了直接插入排序,此时数组arr中的数据接近顺序有序。

void ShellSort(int* arr, int n)
{int gap = 3;int i = 0;for (i = 0; i < gap; i++){int j = 0;for (j = i; j < n - gap; j += gap){int end = j;//将tmp赋值为数组中end位置后gap位置的值int tmp = arr[end + gap];while (end >= 0){//如果tmp的值小于此时end位置的值if (tmp < arr[end]){//就将end+gap位置的值赋值为end位置的值,arr[end + gap] = arr[end];//然后将end向后移gap个距离,继续和tmp比较end -= gap;}else{break;}}//此时end位置的值是小于tmp的,将end+gap位置的值赋值为tmparr[end + gap] = tmp;}}
}

上述代码嵌套了三层循环,会让人觉得循环太多,其实可以将外面的循环去掉,然后将第二层循环的i += gap变为i++。达到的效果和上面的代码一致,上面代码是将gap组数依次进行直接插入排序,而这个代码是将第一组数的一个进行直接插入排序后,然后将第二组数进行直接插入排序,然后将第三组数进行直接插入排序。这样两个代码达到的效果是一样的。

void ShellSort(int* arr, int n)
{int gap = 3;int j = 0;for (j = 0; j < n - gap; j ++){int end = j;//将tmp赋值为数组中end位置后gap位置的值int tmp = arr[end + gap];while (end >= 0){//如果tmp的值小于此时end位置的值if (tmp < arr[end]){//就将end+gap位置的值赋值为end位置的值,arr[end + gap] = arr[end];//然后将end向后移gap个距离,继续和tmp比较end -= gap;}else{break;}}//此时end位置的值是小于tmp的,将end+gap位置的值赋值为tmparr[end + gap] = tmp;}
}

到这里只完成了希尔排序的第一个步骤,即预排序,而想要将数组中的数据都有顺序,还需要将数组进行直接插入排序。预排序的目的是让数组中的数据达到基本顺序有序,这样使用直接插入排序对数组排序时效率就会提高。
希尔排序的gap该怎么选择呢?
由上面我们可以直到当排升序时,gap越大,大的数更快到后面,小的数可以更快到前面,但是越不接近有序。
排升序时,gap越小,越接近有序,当gap==1时,就是直接插入排序。
当数组中数据为10000个时,此时如果选择gap=3,则预排序和进行直接排序插入的复杂度差不多。当数组中数据为100个时,此时将gap=30,则经过预排序后数组中的数据还是没有达到基本顺序有序。
此时我们可以将gap设置为一个变化的值。

void ShellSort(int* arr, int n)
{int gap = n;int j = 0;//gap>1时都为预排序,并且随着gap越来越小,数组越来越接近有序while (gap > 1){//随着gap越来越小,数组中的数据越接近有序,当gap==1时,就是直接插入排序gap = gap / 3 + 1;  // gap / 3 + 1保证了最后一次gap=1,即最后一次为直接插入排序for (j = 0; j < n - gap; j++){int end = j;//将tmp赋值为数组中end位置后gap位置的值int tmp = arr[end + gap];while (end >= 0){//如果tmp的值小于此时end位置的值if (tmp < arr[end]){//就将end+gap位置的值赋值为end位置的值,arr[end + gap] = arr[end];//然后将end向后移gap个距离,继续和tmp比较end -= gap;}else{break;}}//此时end位置的值是小于tmp的,将end+gap位置的值赋值为tmparr[end + gap] = tmp;}}}

3、希尔排序时间复杂度

希尔排序的时间复杂度很难求,我们只需记住它的时间复杂度接近于O(N^1.3)。
《数据结构(C语言版)》— 严蔚敏
在这里插入图片描述

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

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

相关文章

【Vue】vue2预览显示quill富文本内容,vue-quill-editor回显页面,v-html回显富文本内容

文章目录 前言一、下载二、使用步骤1.引入样式2.html代码 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; vue后台框架&#xff0c;若依系统里有一个富文本编辑器&#xff0c;效果如下 在package.json里面查看&#xff0c;发现插件名叫quill 插件的…

基于食肉植物算法优化的BP神经网络(预测应用) - 附代码

基于食肉植物算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码 文章目录 基于食肉植物算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码1.数据介绍2.食肉植物优化BP神经网络2.1 BP神经网络参数设置2.2 食肉植物算法应用 4.测试结果&#xff1a;5…

【Leetcode】130.被围绕的区域

一、题目 1、题目描述 给你一个 m x n 的矩阵 board ,由若干字符 X 和 O ,找到所有被 X 围绕的区域,并将这些区域里所有的 O 用 X 填充。 示例1: 输入:board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“…

海外ios应用商店优化排名因素之视频预览与截图

当我们找到感兴趣的应用程序并转到该应用程序的页面时&#xff0c;首先引起注意的是预览视频。视频旨在以更具吸引力的方式展示应用程序的用户体验和UI。视频长度最多为30秒&#xff0c;其中前5秒最为重要&#xff0c;一定要让它尽可能引人注目。 1、关于优化预览视频的提示。…

【C语言】循环语句详解

✨个人主页&#xff1a; Anmia.&#x1f389;所属专栏&#xff1a; C Language &#x1f383;操作环境&#xff1a; Visual Studio 2019 版本 目录 1.什么是循环结构&#xff1f; 2.while循环 while流程图 while语句中的break和continue break continue 3.for循环 for流…

进程Start

Linux中的命令解释器和Windows的程序管理器explorer.exe一样地位,都是在用户态下运行的进程 共享变量发生不同进程间的指令交错&#xff0c;就可能会数据出错 进程只作为除CPU之外系统资源的分配单位 CPU的分配单位是线程 每个进程都有自己的独立用户空间 内核空间是OS内核的…

PyCharm切换虚拟环境

PyCharm切换虚拟环境 为了满足不同任务需要不同版本的包&#xff0c;可以在Anaconda或者Miniconda创建多个虚拟环境文件夹&#xff0c;并在PyCharm下切换虚拟环境。 解决方案 1、打开Ananconda Prompt 2、创建自己的虚拟环境 格式&#xff1a;conda create -n 虚拟环境名字…

PSP - 蛋白质结构预测 OpenFold Multimer 模型训练参数与配置

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/132575709 OpenFold Multimer 是用于预测蛋白质多聚体结构的计算方法。基于OpenFold 的单体预测框架&#xff0c;利用深度学习技术&#xff0c;结…

dayjs格式转换成日期

目录 方法一&#xff1a; ​编辑方法二&#xff1a; 这个项目在筛选订单时间的时候是由前端进行筛选的&#xff0c;用的是adt-design-pro进行二开的&#xff0c;其中在用日期组件的时候遇到了一个问题&#xff0c;组件返回的是&#xff1a; 但是我需要的是年-月-日&#xff…

java八股文面试[数据库]——MySql聚簇索引和非聚簇索引区别

聚集索引和非聚集索引 聚集索引和非聚集索引的根本区别是表记录的排列顺序和与索引的排列顺序是否一致。 1、聚集索引 聚集索引表记录的排列顺序和索引的排列顺序一致&#xff08;以InnoDB聚集索引的主键索引来说&#xff0c;叶子节点中存储的就是行数据&#xff0c;行数据在…

LeetCode 面试题 02.04. 分割链表

文章目录 一、题目二、C# 题解 一、题目 给你一个链表的头节点 head 和一个特定值 x&#xff0c;请你对链表进行分隔&#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。 点击此处跳转题目。 示例 1&#…

c# 本地化中英文切换

区域 线程默认区域为当前计算机所选区域 设置当前区域&#xff1a; Thread.CurrentThread.CurrentCulture new CultureInfo(“zh-cn”); 获取当前区域&#xff1a; Console.WriteLine(Thread.CurrentThread.CurrentCulture.ToString()); 区域名称&#xff1a; “zh-cn” 中文…

Spooling的原理

脱机技术 程序猿先用纸带机把自己的程序数据输入到磁带中&#xff0c;这个输入的过程是由一台专门的外围控制机实现的。之后CPU直接从快速的磁带中读取想要的这些输入数据。输出也类似。 假脱机技术&#xff08;Spooling技术&#xff09; 即用软件的方式来模拟脱机技术。要…

python爬虫14:总结

python爬虫14&#xff1a;总结 前言 ​ python实现网络爬虫非常简单&#xff0c;只需要掌握一定的基础知识和一定的库使用技巧即可。本系列目标旨在梳理相关知识点&#xff0c;方便以后复习。 申明 ​ 本系列所涉及的代码仅用于个人研究与讨论&#xff0c;并不会对网站产生不好…

如何实现AI的矢量数据库

推荐&#xff1a;使用 NSDT场景编辑器 助你快速搭建3D应用场景 然而&#xff0c;人工智能模型有点像美食厨师。他们可以创造奇迹&#xff0c;但他们需要优质的成分。人工智能模型在大多数输入上都做得很好&#xff0c;但如果它们以最优化的格式接收输入&#xff0c;它们就会真正…

DNS指向别名还是IP

现在有一台服务器dbprod126&#xff0c;ip是172.22.100.4 现在有一个需求&#xff0c;需要在dns中对dbprod126建一个别名wondadb3r的记录&#xff0c;也就是ping wondadb3r的时候显示的是dbprod126的ip&#xff0c;目前有两​种方法&#xff0c;主要使用方法1指向别名&#xf…

【Docker】网络

文章目录 Docker 网络基础Docker网络管理Docker网络架构CNMLibnetwork驱动 常见的网络类型 Docker 网络管理命令docker network createdocker network inspectdocker network connectdocker network disconnectdocker network prunedocker network rmdocker network ls docker …

多线程网络实现在线聊天系统(详细源码)

这篇博客整理自韩顺平老师的多线程网络学习&#xff0c;在Java基础中最难的就是多线程以及网络编程了&#xff0c;如果不太熟悉的小伙伴可以跟着课程学习&#xff0c;韩老师讲得很详细&#xff0c;缺点就是太详细有点墨迹。实现后的效果是在一个类似命令行窗口进行聊天&#xf…

软件测试—测试用例的设计

软件测试—测试用例的设计 测试用例是什么&#xff1f; 首先&#xff0c;测试用例&#xff08;Test Case&#xff09;是为了实施测试而向被测试系统提供的一组集合。这组集合包括&#xff1a;测试环境、操作步骤、测试数据、预期结果等要素。 好的测试用例的特征 一个好的测试…

349. 两个数组的交集

题目来源&#xff1a;力扣 题目描述&#xff1a; 给定两个数组 nums1 和 nums2 &#xff0c;返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1&#xff1a; 输入&#xff1a;nums1 [1,2,2,1], nums2 [2,2] 输出&#x…