直接插入排序算法,看这篇就够了

举报
游坦之 发表于 2022/10/23 19:28:40 2022/10/23
【摘要】 前言:✌ 作者简介:游坦之 ✌🏆 大学软件工程在读,希望学到真本领,经世致用 🏆📫 如果文章知识点有错误的地方,请指正!和大家一起学习,一起进步👀💬 人生格言:成好人,行好事,做儒猿💬🔥 如果感觉博主的文章还不错的话,还请👍关注、点赞、收藏三连支持👍一下博主哦@TOC 🍉什么是直接插入排序?直接插入排序(Straight Insertion Sort)是一种最简单的排序方...

在这里插入图片描述

前言:
✌ 作者简介:游坦之 ✌
🏆 大学软件工程在读,希望学到真本领,经世致用 🏆
📫 如果文章知识点有错误的地方,请指正!和大家一起学习,一起进步👀
💬 人生格言:成好人,行好事,做儒猿💬
🔥 如果感觉博主的文章还不错的话,还请👍关注、点赞、收藏三连支持👍一下博主哦

@TOC

在这里插入图片描述

🍉什么是直接插入排序?

直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。

🍊举个例子

对{5,2,8,7,9,4,3}进行直接插入排序

第一步,容器是空的,取出第一个元素5,放在容器的第一位。

在这里插入图片描述

第二步,取出第二位元素2,与有序容器里的元素依次排序,此时有序容器里只有一个元素5,2与5进行比较,2比5小,2放在5前面。

在这里插入图片描述

第三步,取出元素8,依次与有序容器里的元素进行比较。与2进行比较,大于2,继续往后进行比较,8还是大于5,所以放在5的后面。

在这里插入图片描述

第四步,取出元素7,依次与有序容器里的元素进行比较。和2进行比较,7>2,继续往后取出元素5进行比较,7>5,继续取出元素8进行比较。7<8,所以7放在元素8的前面。

在这里插入图片描述

第五步,取出元素9,依次与有序容器里的元素进行比较。和2进行比较,9>2,继续往后取出元素5进行比较,9>5,继续元素7进行比较,9>7,继续往后取出元素8,进行比较,9>8,所以9放在8的后面。

在这里插入图片描述

第六步,取出元素4,依次与有序容器里的元素进行比较,和2进行比较,4>2,继续往后取出元素5进行比较,4<5,所以4就放在5前面。

在这里插入图片描述

第七步,取出元素3,依次与有序容器里的元素进行比较,和2进行比较,3>2,继续取出元素4进行比较,此时3<4,所以把元素3放在元素4的前面。

在这里插入图片描述

🍌代码

#include <iostream>
using namespace std;
const int M = 10010;
int a[M];
int s[M];
int n;
int s_num = 0;//记载 
int main()
{
	cout<<"请输入有多少个数据"<<endl;
	cin>>n;
	cout<<"请输入数据"<<endl;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<n;i++)
	{
		bool flag = true;
		for(int j=0;j<s_num;j++)
		{
			if(a[i]<=s[j])
			{
				for(int k = s_num-1;k>=j;k--)//后移的操作 
				{
					s[k+1] = s[k]; 
				}
				s_num++;
				flag = false;//代表置换了
				s[j] = a[i];
				break; 
			}
		}
		if(flag)//意味着这个数比s这个有序数组里面所有的元素的都大 
		{
			
			s[s_num++] = a[i];
		}
	}
	for(int i=0;i<s_num;i++)
	{
		cout<<s[i]<<" ";
	}
	
	return 0;
 } 

在这里插入图片描述

🍋总结

​ 由上面的栗子可以清晰的看出,直接插入排序需要两个容器,一是承载所有的集合,而是承载逐步扩充的有序集合。有序集合本是空集,随着每一步的扩充,集合的元素总数加1.也就是原集合有多少个元素,就需要进行多少步,即原有n个元素,就要进行n步排序。而每一步排序,最坏情况都需要遍历m次,这就意味着直接插入排序的时间复杂度即为O(n2)。但是从上面的代码来看,如果用到的是普通的数组,对于数组后移这样的操作,仍需要遍历z次,这就意味着时间复杂度变成了O(n3)。对此,我们可以用动态数组或者是链表进行优化。

​ 就比赛而言,每个比赛的时间限制大体在1s,计算量在10的8次方,对于O(n2)的时间复杂度而言,直接插入排序适合的计算量大约在10000左右,超过10000的数据不太适合用直接插入排序。则需要更高效的算法,或者需要更方便的容器。

​ 而对于容器而言,常见的有数组、链表、set、vector、map、queue、stack等等。

在这里插入图片描述

原创不易,还希望各位大佬支持一下 \textcolor{blue}{原创不易,还希望各位大佬支持一下}

👍 点赞,你的认可是我创作的动力! \textcolor{green}{点赞,你的认可是我创作的动力!}

⭐️ 收藏,你的青睐是我努力的方向! \textcolor{green}{收藏,你的青睐是我努力的方向!}

✏️ 评论,你的意见是我进步的财富! \textcolor{green}{评论,你的意见是我进步的财富!}

在这里插入图片描述

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

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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