算法描述

在本节中，我们考虑如何用减-技术对-一个数组A[..n- 1]排序。遵循该方法的思路，

我们假设对较小数组A[0..n - 2]排序的问题已经解决了，得到了一个大小为n-1的有序数组: A[0]≤..≤A[n- 2]。我们如何利用这个较小规模的解，并将元素A[n- 1]考虑进来，来得到原问题的解呢?显然，我们需要做的就是在这些有序的元素中为A[n- 1]找到一个合适的位置，然后把它插入到那里。一般来说，我们可以从右到左扫描这个有序的子数组，直
到遇到第一个小于等于A[n- 1]的元素，然后把A[n - 1]插在该元素的后面。这种算法被称为直接插入排序(straight insertion sort)，或者简称为插入排序(insertion sort)。

虽然插入排序很明显是基于递归思想的，但从底至上地实现这个算法，也就是使用迭代，效率会更高。从A[I]开始，到A[n- 1]为止，A[1]被插在数组的前i个有序元素中的适当位置.上(但是，和选择排序不同，这个位置一般来说并不是它们的最终位置)。

算法设计

public class TEST {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[]= {89,45,68,90,29,34,17};
		System.out.print("排序前：");
		for(int k=0;k<a.length;k++){
			System.out.print(a[k]+" ");
			}
			System.out.println();
		for(int i=1;i<a.length;i++) {
			int v=a[i];
			int j=i-1;
			while(j>=0&&a[j]>v) {
				a[j+1]=a[j];
				j=j-1;
				a[j+1]=v;
			}
		}
		System.out.print("排序后：");
		for(int k=0;k<a.length;k++){
			System.out.print(a[k]+" ");
			}
	}

}

运行结果

排序前：89 45 68 90 29 34 17 
排序后：17 29 34 45 68 89 90