NOIP-C++大神培养计划Step1.2.2——排序之插入排序

  1. 云栖社区>
  2. 博客>
  3. 正文

NOIP-C++大神培养计划Step1.2.2——排序之插入排序

小笨笨qaq 2018-12-04 20:18:53 浏览483
展开阅读全文

上一节课呢,我们学习了冒泡排序,今天我们就来学学插入排序。


先看一个图

ee08799763dcc631d05f1c6d19bce83f7d13497a


很显然,我们要选出一个数,并找到他的位置,就像图中的一样。


有过一定生活经验的人会发现,这句就是打牌时的理牌嘛!


我们首先要用O(n)的时间来枚举每一个点,再用O(n)的时间查它之前在序列中的应有位置,所以,总复杂度是O(n^2)。


我们来看看代码:



#include<iostream>
using namespace std;
int n,a[10001],t,j,k;//循环之外要用的j,k 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		for(j=i-1;j>=0;j--)
			if(a[j]<a[i])//找到比a[i]小的位置就退出,插入其后 
				break;
		if(j!=i-1)
		{
			t=a[i];
			for(k=i-1;k>j;k--)
				a[k+1]=a[k];//位置前移一个 
			a[k+1]=t;
		}
	}
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}


这个代码看似和bubblesort冒泡排序很像,但是它的不同在于使用了全局变量j,k来储存a[i]应有的位置和现在所属的位置。

有时候这个代码很难理解,但是理清思路,最后也是很好理解的。


代码的关键在于:


for(j=i-1;j>=0;j--)
if(a[j]<a[i]) 
	break;
if(j!=i-1)
{
	t=a[i];
	for(k=i-1;k>j;k--)
		a[k+1]=a[k];
	a[k+1]=t;
}

其实,说句实话,插入排序的运用真的不广泛。只要懂得,不必太深究。


今天的课程就到这里,明天我们要讲选择排序,我们明天见!

网友评论

登录后评论
0/500
评论
小笨笨qaq
+ 关注