java实现插入排序(思路和实现)

java实现插入排序(思路和实现)插入排序(英语:InsertionSort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。插入排序分析效果图:代码实现:publicclassInsert{ publicstaticvoidmain(Strin…

大家好,欢迎来到IT知识分享网。

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

插入排序分析

java实现插入排序(思路和实现)

效果图:

java实现插入排序(思路和实现)

代码实现:

public class Insert
{
	public static void main(String[] args)
	{
		int[] ins = {2,3,5,1,23,6,78,34};
		int[] ins2 = sort(ins);
		for(int in: ins2){
			System.out.println(in);
		}
	}

	public static int[] sort(int[] ins){
		
		for(int i=1; i<ins.length; i++){
			for(int j=i; j>0; j--){
				if(ins[j]<ins[j-1]){
					int temp = ins[j-1];
					ins[j-1] = ins[j];
					ins[j] = temp;
				}
			}
		}
		return ins;
	}
}

针对上面的这个排序算法改进:首先上面的这个每次替换都要定义一个temp赋值需要插入的数,这样会造成不必要的浪费:

所以我们可以吧所有的大于需要插入的数先保存,然后进行比较,然后将最后的正确位置空出来。吧之前保存的需要插入的数放到正确位置上;

代码:

public static int[] sort2(int[] ins){
		
		for(int i=1; i<ins.length; i++){
			int temp = ins[i];//保存每次需要插入的那个数
			int j;
			for(j=i; j>0&&ins[j-1]>temp; j--){//这个较上面有一定的优化
				ins[j] = ins[j-1];//吧大于需要插入的数往后移动。最后不大于temp的数就空出来j
			}
			ins[j] = temp;//将需要插入的数放入这个位置
		}
		return ins;
	}

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/21977.html

(0)
上一篇 2024-01-13 10:00
下一篇 2024-01-13 11:00

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信