程序员必须掌握的排序算法:插入排序的原理与实现

举报
鸽芷咕 发表于 2023/12/31 17:09:06 2023/12/31
【摘要】 插入排序八大排序之一是一种非常简单直观的排序算法,尽管插入排序在时间复杂度上并不是最优的选择,但它的思想简单直观,易于实现

📋 前言

插入排序八大排序之一是一种非常简单直观的排序算法,尽管插入排序在时间复杂度上并不是最优的选择,但它的思想简单直观,易于实现。而且根据插入排序我们还可以推演出希尔排序这种效率更高的排序。

  • 今天就来带大家看一下选择排序的实现和完部代码吧

一、插入排序的思想

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

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

而我们从小被人熟知的扑克牌的摸牌的过程就非常像插入排序
在这里插入图片描述

二、插入排序的具体实现

插入排序对的思想就是每次把后面的一个值和前面的有序序列进行对比:

  • 如果比他大就把比他大的数往后移动
  • 直到遇到比我们要比较的值小的时候就停下来然后插入
    在这里插入图片描述

2.1 实现思路

所以实现思路也就很简单了 首先 需要一个end来表示有序队列的队尾:

  • 🔥 然后再 定义一个 tmp 用于和前面的有序序列进行比较
  • 🔥 而每一次插入一个数都需要遍历一遍比较所以还需要一个
  • 🔥 while循环来遍历,找到了位置之后就把 tmp 插入进去

2.2 实现代码

🍸 代码演示:

void insertsort(int* str,int n)
{
	
	for (size_t i=0; i<n-1; i++)
	{
		int end = i;
		int tmp = str[end + 1];
		while (end >= 0)
		{
			if (str[end] > tmp)
			{
				str[end + 1] = str[end];
			}
			else
			{
				break;
			}
			end--;
		}

		str[end+1] = tmp;
	}
	
}

三、插入排序的时间复杂度

由于插入排序每次,都要遍历一下再找打插入的位置所以插入排序的时间复杂度是

  • 时间复杂度:O(N*N)
  • 空间复杂度:O(1) 它并没有开辟额外空间

总结来说插入排序是一个非常稳定的算法,元素集合越接近有序,直接插入排序算法的时间效率越高。

📝文章结语:

☁️ 把本章的内容全部掌握,铁汁们就可以熟练应用switch语句啦!
看到这里了还不给博主扣个:
⛳️ 点赞🍹收藏 ⭐️ 关注

💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要!
你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。
在这里插入图片描述

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。