【数据结构与算法】第10课—数据结构之插入排序

ops/2024/11/14 11:01:57/

文章目录

  • 1. 排序
  • 2. 算法>排序算法
  • 3. 插入排序
    • 3.1 直接插入排序
    • 3.1 希尔排序
  • 4. 插入排序时间复杂度和空间复杂度

1. 排序

  什么是排序?所谓排序,就是使用一串记录,按照其中的某个字或或某些关键字来对其进行递增或递减式的排列。
  简单通俗点讲,就像我们在淘宝页面,所有商品我们可以让他按照价格排序,也可以按照销售量排序等,排序在我们生活中随处可见。
在这里插入图片描述

  • 这张图片就是我的博客按照时间顺序来进行排序的,还麻烦各位兄弟姐妹路过时点个赞奥!

2. 算法>排序算法

  那么常见的算法>排序算法都有哪些呢?接下来一张图来带大家了解
在这里插入图片描述

  • 今天呢,我们先来学习第一种算法>排序算法—插入排序

3. 插入排序

  • 插入排序呢,又分为两种:直接插入排序和希尔排序,接下来我们直入主题

3.1 直接插入排序

  • 那什么是直接插入排序呢?

在这里插入图片描述

  • 相信大家都玩过扑克牌吧,其实玩扑克牌的过程就应用了直接插入排序的思想,在拿到牌的时候,是不是每次都要对比一下手里已经排好顺序的手牌,然后再将拿到的牌按照顺序插入其中,没错,直接插入排序的思想如出一辙
  • 直接插入排序的思想就是从头开始排序,拿到新的元素与之前已经排好序的序列对比,然后将它放到合适的位置,再拿新的元素与已经排好序的序列对比,插入和合适的位置,以此往复,直到所有都插入完毕结束

  接下来我将用图解的方式来帮助大家去理解
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
  通过上述图解我们可以看出直接插入排序的过程,每趟对比arr[end]和tmp,如果arr[end]大,那么就要赋值,再让end–,再对比arr[end]和tmp,以此往复,就可以完成排序

  • 那么接下来我们看看代码如何实现
//直接插入排序
void InsertSort(int* arr, int sz)
{int i = 0;//排序的趟数for (i = 0; i < sz - 1; i++)//由于排序的趟数 = 数组元素-1,数组下标是从0开始的,则i<sz-1{int end = i;//已排好序的序列尾元素下标int tmp = arr[end + 1];//已排好序的尾元素后面那个元素(每趟)while (end >= 0) //end不越界进入循环{if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}//如果tmp > arr[end]else{break;}}//此时已经对比完arr[end + 1] = tmp;}
}

3.1 希尔排序

  通过上述直接插入排序我们可以看出,如果数组arr是有序(降序)的,那么它的时间复杂度就是O(n^2),这也是它最坏的情况,如果数组arr是有序(升序)的,那么它的时间复杂度是O(n),它只用每趟对比,不用赋值交换
  那么如何可以降低它的时间复杂度呢?这时候就提出了希尔排序

  • 希尔排序的算法思想是先选定一个整数(通常呢是gap=n/3+1),然后把待排序的数组分为三组进行直接插入排序,然后再让gap=gap/3+1得到下一个整数,按照这个整数再进行分组,直接插入排序,当gap=1时,相当于直接插入排序
  • 它是在直接插入算法>排序算法的基础上改进的,自然效率要比直接插入要好点

  接下来来我们来看看它是怎么实现的吧
在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


  接下来让我们看看代码是如何实现的吧
在这里插入图片描述


  • 代码
//希尔排序
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 end = i;int tmp = arr[end + gap];//初始时tmp在end+gap的位置while (end >= 0){//如果arr[end]大于tmpif (arr[end] > tmp){arr[end + gap] = arr[end];//让arr[end+tmp]等于arr[end]end = end - gap;//因为分组,end不再--,而是走到end-gap的位置}else{break;}}arr[end + gap] = tmp;//最后end+gap的位置要将tmp的值放进来}}
}

  这里为什么让gap=gap/3+1呢?因为如果gap除的数大了,那么分的组少,对比的次数也多;而gap除的数小了,分的组少,每组对比的次数少,所以一般取gap=gap/3+1或者gap=gap/2+1
在这里插入图片描述


4. 插入排序时间复杂度和空间复杂度

  • 直接插入排序的时间复杂度是O(N^2),空间复杂度是O(1)
  • 希尔排序的时间复杂度一直存在着争论,因为希尔排序中用到的gap值不确定,这就导致它的时间复杂度存在不确定性,不过目前经过大量实验证明,希尔排序的时间复杂度约为O(n^1.3)

  由于直接插入排序的时间复杂度较高,因此它并不是一个好的算法>排序算法,常常用来作为教学


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

相关文章

【系统配置】命令行配置麒麟安全中心应用程序来源检查

原文链接&#xff1a;【系统配置】命令行配置麒麟安全中心应用程序来源检查 Hello&#xff0c;大家好啊&#xff01;今天带来一篇关于如何通过命令行配置麒麟系统安全中心应用程序来源检查的文章。应用程序来源检查是系统安全管理中的重要功能之一&#xff0c;它可以帮助用户识…

高边坡安全监测系统的工作原理和应用领域

高边坡安全监测系统的工作原理主要依赖于各种先进的传感器设备&#xff0c;这些传感器能够实时地捕捉和记录边坡的位移、应力、裂缝、倾斜和沉降等多种关键数据。这些数据的采集是通过高精度的监测设备进行的&#xff0c;确保了数据的准确性和可靠性。采集到的数据随后通过高效…

Elasticsearch可视化工具Elasticvue插件用法

目录 1.打开浏览器扩展程序(示例Edge浏览器) ​2.搜索elasticvue并安装 3.打开elasticvue ​4.连接Es 5.有些浏览器无法下载安装扩展&#xff0c;例如谷歌。可以打包扩展给别的浏览器使用。 5.1打开浏览器扩展&#xff0c;打开开发人员模式&#xff0c;记住扩展程序id 5…

第 6 章 - Go 语言 运算符

在编程语言中&#xff0c;运算符用于执行程序代码中的各种操作。它们可以分为多个类别&#xff0c;包括算术运算符、关系运算符和逻辑运算符等。下面我将为您简要介绍这些运算符的基本概念和用法。 算术运算符 算术运算符用于执行基本的数学运算&#xff0c;如加法、减法、乘…

FPGA学习(10)-数码管

前3节视频目的是实现显示0~F的数码管仿真&#xff0c;后3节是用驱动芯片驱动数码管。 目录 1.数码管显示原理 2.代码过程 2.1仿真结果 3.串行移位寄存器原理 3.1原理 ​编辑 3.2 数据手册 3.3 先行设计思路 4.程序 4.1确定SRCLK的频率 4.2序列计数器 4.3 不同coun…

蓝桥杯c++算法学习【1】之枚举与模拟(卡片、回文日期、赢球票、既约分数:::非常典型的比刷例题!!!)

重发一下&#xff0c;之前得排版有问题&#xff0c;而且另外加了一道题。。 别忘了请点个赞收藏关注支持一下博主喵&#xff01;&#xff01;&#xff01; 关注博主&#xff0c;更多蓝桥杯nice题目静待更新:) 枚举与模拟 一、卡片&#xff1a; 【问题描述】 小蓝有很多数字…

数据库期末考试简答题

1&#xff0e;试述数据、数据库、数据库管理系统、数据库系统的概念。 答&#xff1a;&#xff08;1&#xff09;数据是数据库中存储的基本对象&#xff0c;是描述事物的符号记录。数据有多种表现形式&#xff0c;它们都可以经过数字化后存入计算机。数据的种类有数字、文字、…

FPGA在航空航天领域的应用案例解析!!!

FPGA&#xff08;Field-Programmable Gate Array&#xff0c;现场可编程门阵列&#xff09;在航空航天领域有着广泛的应用&#xff0c;其优势在于高度的可定制性、出色的实时性能、以及良好的抗辐射能力。以下是FPGA在航空航天领域的几个典型应用案例解析&#xff1a; 1. 星载…