温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

java如何实现插入排序算法

发布时间:2022-01-17 09:37:10 来源:亿速云 阅读:145 作者:小新 栏目:云计算

这篇文章主要介绍了java如何实现插入排序算法,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。

    插入排序,这种排序在平时生活中很常见,打扑克时拿到凌乱的手牌捋顺序,整理手上大大小小的钞票等等。

    插入即是将目标元素插入到已经排序好的元素之中。

    所以需要两层循环。第一层循环取各个为排序的元素,第二层循环将要排序的元素插入到正确的位置。

    这么说好像挺简单。其实对于第二层循环将元素插入到正确的位置。我觉得有两种方法。第一种,将要插入的元素使用冒泡的方法两两比较循环找到正确的位置,另一种是比较要排序的元素和各个已经排序的元素,得到正确的角标,最后实现插入。

    对于第一种方法,感觉这不像是插入,因为他循环比较并且是通过移动获得正确的位置的。第二种方法由于只是比较大小,最后通过插入到正确的位置而结束。效率比第一种提高一倍。

    那么看代码实现吧

    第一种实现,效率地下

	@Override
	public void sort(int[] a) {
		int len=a.length;
		for(int i=1;i<len;i++){  //首先是最外层循环,表示插入多少次
			int j=i-1;//已经排序好的部分的右端点
			while(j>=0&&SortUtils.less(a[j+1], a[j])){//开始比较
				SortUtils.exch(a, j, j+1);//交换要排序的元素和已经排序好的元素
				j--;
			}
		}
	}

    第二种实现,效率较高

	@Override
	public void sort(int[] a) {
		int len=a.length;
		for(int i=1;i<len;i++){  //首先是最外层循环,表示插入多少次
			int j=i-1;//已经排序好的部分的右端点
			int e=a[i];//首先将要排序的元素储存起来
			while(j>=0&&SortUtils.less(e, a[j])){//开始比较
				a[j+1]=a[j];  //单单移动元素,比上面一种方法快捷
				j--; //循环找到要排序元素的正确位置 j+1 
			}
			a[j+1]=e;
//			为什么是 j+1  
//			因为内层while循环结束条件是找到第一个比要插入元素小的数组元素,这个元素的角标即是j
//			所以要插入元素的正确位置就是 j+1
		}

感谢你能够认真阅读完这篇文章,希望小编分享的“java如何实现插入排序算法”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI