首页 > 编程语言 >【数据结构】排序算法系列——插入排序(附源码+图解)

【数据结构】排序算法系列——插入排序(附源码+图解)

时间:2024-09-05 16:50:01浏览次数:13  
标签:tmp arr end int 插入排序 begin 源码 数据结构

插入排序

算法思想

插入排序的算法思想其实很容易理解,它秉持着一个不变的循环:比较->交换->比较->交换…因为我们排序最终的目的是要得到递增或者递减的数据,那么在原有的数据中,我们可以将数据依次两两进行比较:

  • 如果是升序,那么就将较小的放在较大的前面
  • 如果是降序,那么就将较大的放在较小的前面

图解

请添加图片描述

我们看图解中,单次比较过程中,拿出来比较的数只会同它左侧的数进行比较,而被比较的数随着比较结束也会根据具体情况向后移动或者是进行交换,向后移动的过程也称为——补位。在全程的比较中,随着补位和交换的进行,进行比较操作的数只会与曾经进行过比较操作的数进行比较——简单来说,就是比较与被比较是交替进行的。我们总结插入排序算法的核心思路——将待排列元素划分为「已排序」和「未排序」两部分,每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。

C语言代码分析

//升序情况
void InsertSort(int* arr, int n)
{
	int end = n - 1;//从最后一个数据开始进行比较
	int tmp = arr[end];//保存最后一个数据
	while (end >= 0)
	{
		if (tmp <= arr[end])//当tmp小于等于arr[end]时,说明tmp还没有找到合适的位置
		{
			arr[end + 1] = arr[end];//那么就将arr[end]向后移动
			end--;//继续向前比较
		}
		else//当tmp大于arr[end]时,说明tmp已经找到了合适的位置
		{
			break;//那么就直接退出循环
		}
	}
	arr[end + 1] = tmp;
}

//降序情况
void InsertSort2(int* arr, int n)
{
	int begin = 0;//从第一个数据开始进行比较
	int tmp = arr[begin];//保存第一个数据
	while (begin <= n - 1)
	{
		if(tmp>=arr[begin])//当tmp大于等于arr[begin]时,说明tmp还没有找到合适的位置
		{
			arr[begin - 1] = arr[begin];//那么就将arr[begin]向后移动
			begin++;//继续向后比较
		}
		else//当tmp小于arr[begin]时,说明tmp已经找到了合适的位置
		{
			break;//那么就直接退出循环
		}
		arr[begin + 1] = tmp;
}

在现实生活中,扑克牌的排序事实上就是遵循着插入排序的思想:

在这里插入图片描述

时间复杂度

  • 插入排序的最优时间复杂度为O(n),在数列几乎有序时效率很高。

  • 插入排序的最坏时间复杂度和平均时间复杂度都为O(n2)

稳定性

鉴于插入排序不会改变前后元素的相对位置,所以: 稳定

标签:tmp,arr,end,int,插入排序,begin,源码,数据结构
From: https://blog.csdn.net/Skrrapper/article/details/141891428

相关文章

  • 软件开发教学:基于数字药店系统源码的医保购药APP开发策略
    本篇文章,小编将详细探讨基于数字药店系统源码的医保购药APP开发策略,并提出一些开发中的关键技术要点。 一、数字药店系统源码的功能概述数字药店系统源码是构建在线药店的基础,它集成了药品信息管理、订单处理、支付系统、用户管理等核心模块,旨在实现药品销售的全流程数字化。一个......
  • php基于Vue的民宿短租平台(源码+文档+调试+讲解)
    收藏关注不迷路!!......
  • php基于Vue的门诊管理系统(源码+文档+调试+讲解)
    收藏关注不迷路!!......
  • java+vue计算机毕设社区独居老人健康管理系统【源码+开题+论文】
    本系统(程序+源码)带文档lw万字以上文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着我国人口老龄化的加速,独居老人的数量显著增加,这一群体在健康管理上面临着诸多挑战。传统的养老模式难以全面覆盖并有效满足独居老人的健康需求,特......
  • java+vue计算机毕设汽车租赁管理系统【源码+开题+论文】
    本系统(程序+源码)带文档lw万字以上文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着城市化进程的加速和居民生活水平的提高,汽车租赁作为一种便捷、灵活的出行方式,日益受到广大消费者的青睐。传统汽车租赁行业面临着管理效率低下、......
  • java+vue计算机毕设求职招聘管理系统【源码+开题+论文】
    本系统(程序+源码)带文档lw万字以上文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着互联网的飞速发展,网络招聘已成为企业与求职者之间沟通的主要桥梁。传统的招聘方式,如招聘会、报纸广告等,不仅成本高、效率低,而且难以精准匹配企业......
  • 从源码到应用:数字药店系统与医保购药APP的开发实践
    本篇文章,我们将深入探讨数字药店系统的开发过程,并介绍医保购药APP如何通过源码设计实现从基础功能到完整应用的转化。 一、数字药店系统概述数字药店系统是一种基于互联网技术开发的在线药品销售与管理平台,通常包括药品展示、在线购买、订单管理、物流追踪等功能。与传统药店不同,......
  • 基于C#网上购物商城管理系统,Web的网上购物商城的研究现状(源码+数据库+文档)
    目录一.研究目的1.1网上购物系统研究背景1.2网上购物系统开展研究的意义二.功能分析三,数据库分析四.界面展示五.源码获取方式一.研究目的1.1网上购物系统研究背景随着互联网技术的飞速发展,电子商务已成为全球经济的重要组成部分。网上购物商城作为电子商务的一种......
  • 还不懂 ConcurrentHashMap ?这份源码分析了解一下
    1.源码分析在JDK8中的ConcurrentHashMap一共有5个构造方法,这几个构造方法中都没有对内部的数组做初始化,只是对一些变量的初始值做了处理,其中ConcurrentHashMap的数组初始化是在第一次添加元素时完成的。//没有维护任何变量的操作,如果调用该方法,数组长度默认是16public C......
  • 简述Activity Manager的源码
    一、ActivityManager的作用及重要性ActivityManager在Android系统中扮演着至关重要的角色。它负责管理应用程序的Activity的生命周期,包括启动、暂停、恢复和销毁等操作。同时,它还管理着任务栈和返回栈,控制着用户在不同Activity之间的导航。此外,ActivityManager还......