排序之插入排序

插入算法

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

 

 

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,