算法学习日记----直接插入排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法学习日记----直接插入排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1691字，纯文字阅读大概需要3分钟。

内容图文

直接插入排序

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

它的基本思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

这里先附上代码

#include<stdio.h>
int main()
{
	int a[]={1,4,2,6,3,8,9,5,0,10};
	int i,j,t;
	for(i=1;i<10;i++)
	{
		for(j=i;j>0;j--)
		{
			if(a[j]<a[j-1])
			{
				t=a[j];
				a[j]=a[j-1];
				a[j-1]=t;	
			}
		}
		
	}
	for(i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
}

输出结果如下

0 1 2 3 4 5 6 8 9 10

优化算法

优化算法需要增加一个哨兵，增加了哨兵，只需要与有序组的数字一一比较，如果小于就直接赋值，而不需要交换

#include<stdio.h>
int main()
{
	int a[]={0,4,2,6,3,8,9,5,1,10,7};
	int i,j,t;
	for(i=1;i<11;i++)
	{
		if(a[i]<a[i-1])
		{
			t=a[i];
			for(j=i-1;j>0&&t<a[j];j--)
			{
					a[j+1]=a[j];	
			
			}
			a[j+1]=t;
		}	
	}
	for(i=0;i<11;i++)
	{
		printf("%d ",a[i]);
	}
}

我这里是借一个变量来当哨兵，除此之外，还可以借a[0]来做哨兵
算法中引进的附加记录R[0]称监视哨或哨兵(Sentinel)。
哨兵有两个作用：
① 进人查找(插入位置)循环之前，它保存了R[i]的副本，使不致于因记录后移而丢失R[i]的内容；
② 它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R[0].可以和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。

如果能更快找到a[i]在有序组中应该插入的位置，那么能大大提高效率
这里用二分查找法来寻找该插入的位置

#include<stdio.h>
int main()
{
	int a[]={0,4,2,6,3,8,9,5,1,10,7};
	int i,j,t,mid,max,min;
	for(i=1;i<11;i++)
	{
		if(a[i]<a[i-1])
		{
			max=i-1;
			min=0;
			while(max>=min)
			{
				mid=(max+min)/2;
				if(a[mid]>a[i])
				{
					max=mid-1;
				}
				if(a[mid]<a[i])
				{
					min=mid+1;
				}
				
			}
			t=a[i];
			for(j=i-1;j>=max+1;j--)
			{
				a[j+1]=a[j];
			}
			a[max+1]=t;
		}	
	}
	for(i=0;i<11;i++)
	{
		printf("%d ",a[i]);
	}
}

内容总结

以上是互联网集市为您收集整理的算法学习日记----直接插入排序全部内容，希望文章能够帮你解决算法学习日记----直接插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---