插入排序

基本思想：插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。简而言之就是将一个数寻找合适的位置插入到已经有序的数组中。

基本思想又来，就有相应的具体实现：我们在寻找合适的位置的时候，可以通过逐个比较，也可以通过效率较高的二分查找算法，而逐个查找可以从前往后也可以从后往前进行查找，因此又来以下三个版本：

版本1从前往后查找，版本2从后往前查找：

public class InsertSort {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a [] = {45, 12, 11, 32, 56, 11, 8, 30, 3};
		
		System.out.println("插入排序之前:");
		for(int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		
		System.out.println("插入排序之前:");
		/**
		 * 第一种方法
		 */
		/*for(int i=1; i < a.length; i++) {
			int inserted = a[i];
			int pos = i-1;				//默认是最后插入位置
			for(int j=0; j<= i-1; j++){
				if(a[j] >= a[i]){       //找到合适插入位置
					pos = j;
					break;
				}
			}
			for(int k=i-1; k >= pos;k--){
				a[k+1] = a[k]; 
			}
			a[pos] = inserted;//a[i]应该放到全局变量中
		}*/
		
		/**
		 * 第二种方法
		 */
		//从后往前查找
		for(int i=1; i< a.length;i++) {
			int pos = 0;
			int inserted = a[i];
			//寻找合适的插入位置
			
			for(int j = i-1;j >=0 ; j--) {
				if(a[i] >= a[j]){
					pos = j+1;
//					pos = j;//错误写法
					break;
				}//找到合适的插入位置
			}
			//移动元素
			for(int k=i-1;k>=pos;k--) {
				a[k+1] = a[k]; 
			}
			a[pos] = inserted/*a[i]*/;//保存之前的位置
		}//end_for
		
		for(int i=0;i<a.length;i++){
			System.out.print(a[i] + " ");
		}
	}

}

 版本3，二分查找

public class BinaryInsertSort {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] = { 45, 12, 11, 32, 56, 11, 8, 30, 3 };

		System.out.println("插入排序之前:");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		int low, high, mid, tmp;
		for (int i = 0; i < a.length; i++) {
			low = 0;// low指向子序列的起始位置
			high = i - 1;// high指向末端
			tmp = a[i];// 待插入元素
			// 寻找位置
			while (low <= high) {
				mid = (low + high) / 2;
				if (a[i] < a[mid])// 小于mid
					high = mid - 1;
				else
					low = mid + 1;
			}
			// high+1则为待插入位置
			// 将r[high+1...i-1]移动到r[high+2...i]
			for (int j = i; j > high + 1; j--) {
				a[j] = a[j - 1];
			}
			a[high + 1] = tmp;
		}
		System.out.println("插入排序之后:");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}
}

 PS:一定要注意在最后选择插入位置时候是?+1还是？