学步园

转载请注明出处：http://blog.csdn.net/droyon/article/details/8780598

/**
 * 插入排序利用到了这样的事实：0到p-1上的元素，全部处于已排序状态。
 * 插入排序没有数据替换，而是用到了数据移动。
 * 位置p上的元素，储存于temp上，p之前所有更大的元素向右移动一个位置，然后temp被置于正确的位置上。
 * 由于嵌套循环，因此插入排序的时间复杂度为O（N的平方	）
 * @author
 *
 */
public class SimpleInsertMethodSort {
	private static int[] array = new int[]{1,8,2,9,3,7,11,23,90,4,5};
	
	public static void main(String args[]){
		System.out.println("排序前");
		printArray();
		simpleInsertSort();
		System.out.println("\n排序后");
		printArray();
	}
	
	public static void simpleInsertSort(){
		for(int p=1;p<array.length;p++){
			int temp;
			temp = array[p];
			int j;
			for(j=p;j>0&&temp<array[j-1];j--){//找到合适的位置，插入元素，并将位置之后的元素后移
				array[j]=array[j-1];
			}
			array[j] = temp;
		}
	}
	
	public static void printArray(){
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]+"   ");
		}
	}
}

运行结果：

排序前
1   8   2   9   3   7   11   23   90   4   5   
排序后
1   2   3   4   5   7   8   9   11   23   90