`
12616383
  • 浏览: 51504 次
  • 性别: Icon_minigender_1
  • 来自: 待定
社区版块
存档分类
最新评论

排序之插入排序

阅读更多

插入算法


循环数组,以指针数据为基值 并且记录,,通过和左侧(右侧)的循环比较,当比较值大于(小于)基值时
将大的值至后,指针继续移动,比较,置换。直到遇到小于基值,或者到数组边界时截止,并且置换至首位。
结束一次内循环,这是外循环的指针左侧的是有序。

 

 

class Sort{
	private long[] a;
	private int nElement;
	public Sort(long[] array){
		this.a = array;
	}
	
	
	public static void main(String[] args) {
		long[] array = new long[]{5,3,1,7,9,2,0};
		Sort b = new Sort(array);
		b.insertSort();
		System.out.println(b);
	}

	public void insertSort(){
		int out ,in;
		int step = 0;
		for(out = 0; out < a.length; out++){
			long temp = a[out];//记录外层循环时当前的基值
			in = out; //比较位置已外层循环指针的位置开始,指针左侧已有序。
			while(in > 0 && a[in-1] > temp){ 
				//当没有到数组边界 并且前一个值大于基值时 置换,并且将内循环指针前移,继续比较
				//前一个值,直到条件不满足时跳出
				a[in] = a[in-1];
				--in;
				step++;
			}
			// 将外层的基值至于排序中正确的位置
			a[in] = temp;
		}
		System.out.println(step);
	}
	

	public String toString(){
		StringBuilder b = new StringBuilder();
		for(long l : a){
			b.append(l);
			b.append(",");
		}
		return b.toString();
	}
}

 例:

{5,3,1,7,9,2,0}


循环,3 < 5 将大值像后置换。并且指针前移


5,5,1,7,9,2,0,


已到数组边界,将基值至于当前内循环指针位置。


3,5,1,7,9,2,0,

 

3,5,5,7,9,2,0,
3,3,5,7,9,2,0,
1,3,5,7,9,2,0,

1,3,5,7,9,9,0,
1,3,5,7,7,9,0,
1,3,5,5,7,9,0,
1,3,3,5,7,9,0,
1,2,3,5,7,9,0,

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics