插入排序

 

插入排序的基本思想：

    在要排序的一组数种，假设前面(n-1)[n>=2]个数已经是拍好顺序的，现在要把第n个数插到前面的有序数种，使得这n个数也是拍好顺序的。如此反复循环，知道全部排好顺序。

 

一般的实现方式：

public static void insertSort1(int[] data){

		int tmp = 0;
		for(int i = 1 ; i < data.length ; i++){
			tmp = data[i];
			int j = i - 1;
			for(;j >= 0 && tmp < data[j];j--){
				data[j + 1] = data[j];
			}
			data[j + 1] = tmp;
		}
		
		
		for(int i = 0;i <  data.length; i++){
			System.out.print(data[i]+"，");
		}
		
	}

 

更巧妙的实现方式：

public static void insertSort2(int[] data ){
		int left = 0;
		int right = data.length -1;
		
		for (int i = left, j = i; i < right; j = ++i) {
			
            int ai = data[i + 1];
            while (ai < data[j]) {
            	data[j + 1] = data[j];
                if (j-- == left) {
                    break;
                }
            }
            data[j + 1] = ai;
            
        }
		for(int i=0;i<data.length;i++){
			System.out.print(data[i]+"，");
		}
	}