八大排序·直接插入排序

举报
安然无虞 发表于 2022/05/27 00:17:27 2022/05/27
【摘要】 文章目录 直接插入排序1.基本思想2.算法实现3.时间复杂度 遇见安然遇见你,不负代码不负卿。 大家好,我是安然无虞。 插入排序分为两种:直接...

在这里插入图片描述

大家好,我是安然无虞。

插入排序分为两种:直接插入排序&希尔排序

直接插入排序

1.基本思想

直接插入排序是一种简单的插入排序算法,其基本思想是:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列

说得通俗一点就是:

假设区间[0, end]有序,将end+1位置的值插入到[0, end]中,保持区间[0, end+1]依旧有序。

生活中我们玩扑克牌时,就用了插入排序的思想。
在这里,我们以排升序为例。

核心思想:摸牌的过程

在这里插入图片描述
动图演示:
在这里插入图片描述

2.算法实现

写排序时,先从单趟开始考虑
//[0, end]已经有序,将end+1位置的值插入到[0,end]中,使得[0,end+1]依旧保持有序
//有一个有序区间,插入一个数据,依旧保持有序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	//控制摸牌的过程,一开始从仅一张开始
	//注意循环结束条件,只需要到n-2的位置,若将其改成i<n,则会出现越界的情况
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)//保证牌是有序的
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];//往后挪,注意画图感受哦
				end--;
			}
			else
			//有两种可能:(现想常规的,再考虑特殊情况)
			//一是找到了比它小的数,放到其后;
			//二是没有比它小的数,直到end为-1才结束
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

完整代码:
在这里插入图片描述

3.时间复杂度

直接插入排序时间复杂度是O(N^2),注意哦,不是因为双重循环,需要实际计算来得出时间复杂度。
最坏情况:逆序有序,1+2+3+……+n - 1;O(N^2)
最好情况:顺序有序,1+1+1+……+1。O(N)

遇见安然遇见你,不负代码不负卿。

在这里插入图片描述

文章来源: bit-runout.blog.csdn.net,作者:安然无虞,版权归原作者所有,如需转载,请联系作者。

原文链接:bit-runout.blog.csdn.net/article/details/124698830

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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