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

在这里插入图片描述

🎬 鸽芷咕：个人主页 🔥 个人专栏: 《数据结构&算法》

⛺️生活的理想，就是为了理想的生活!

📋 前言

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

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

文章目录

• 📋 前言
• 一、插入排序的思想
• 二、插入排序的具体实现
  • 2.1 实现思路
  • 2.2 实现代码
• 三、插入排序的时间复杂度
• 📝文章结语：

一、插入排序的思想

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

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

而我们从小被人熟知的扑克牌的摸牌的过程就非常像插入排序

在这里插入图片描述

二、插入排序的具体实现

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

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

在这里插入图片描述

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语句啦！ 看到这里了还不给博主扣个： ⛳️ 点赞🍹收藏 ⭐️ 关注！ 💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖 拜托拜托这个真的很重要！ 你们的点赞就是博主更新最大的动力！ 有问题可以评论或者私信呢秒回哦。

在这里插入图片描述