• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

C++插入排序

互联网 diligentman 3周前 (02-17) 11次浏览

文章目录


前言

今天来和大家分享插入排序。


一、插入排序的基础知识点

1.插入排序的排序原理

用未排序序列中的首个元素a,与已排序元素b从后向前逐个对比,若a>b则a插入b的后一位,若a<b,则a、b位置互换。

2.插入排序的所属类别

插入排序属于“比较类排序

3.插入排序的算法复杂度

最坏的情况为与所求序列相反的序列,所以需要依次操作 1、2、3…(n-1)次,由公式得,共为n(n-1)/2次。
所以时间复杂度为O(n²)。

二、插入排序动态图

C++插入排序
图来自 https://visualgo.net/zh/sorting?slide=10-2&#xff0c++;侵删。

三、代码

代码如下:

void calculate()
{
	int n, count, i, min, x, temp;
	cin >> n;    //定义n个数
	int a[999];    //数组里存放n个数
	for(count = 1; count <= n; count++)
	{
		cin >> a[count];    //输入已知序列 a[1]-a[n]
	}
	
	for(count = 2; count <= n; count++)    //以此提取 a[2]到a[n] 
	{
		x = a[count];    //先得到a[count]也就是提取出来的那个数 
		for(i = count-1; i >= 1 ; i--)    //遍历提取的数之前的每个数 到a[1]
		{

		    if(x < a[i])    //若之前的数比提取出来的数大 
	    	{
			    a[i+1] = a[i];    //向后移动一位
				a[i] = x;    
		    }

		}
	}
	
	for(count = 1;  count <= n; count++)
	cout << a[count] << " ";
} 

总结

以上就是今天要和大家分享的内容,本文仅仅简单介绍了插入排序的使用。笔者不才,若有错误,愿大家提出,笔者定及时纠正。愿与大家同学习,共进步!


程序员灯塔
转载请注明原文链接:C++插入排序
喜欢 (0)