插入排序

一.直接插入排序

算法思想：当插入第i个元素的时候，前面的V[0],…,V[i-1]等i-1个 元素已经有序。这时，将第i个元素与前i-1个元素V[i-1]，…，V[0]依次比较，找到插入位置即将V[i]插入，同时原来位置上的元素向后顺移。在这里，插入位置的查找是顺序查找。直接插入排序是一种稳定的排序算法。

public void directInsertSort(int[] arr) {
		if(arr.length == 0 || arr == null) {
			return;
		}
		for(int i=1;i<arr.length;i++) {
			for(int j=i-1;j>=0;j--) {
				if(arr[j]>arr[j+1]) {
					int tmp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = tmp;
				} 
			}
		}
	}

二.希尔排序

算法思想：希尔排序也是一种插入排序，只不过希尔排序是根据步长进行比较，不是与前面一个一个元素进行比较。确定步长step，将每个步长为step的元素进行比较,使用插入排序，让该序列有序，之后步长递减，将每个步长为step的元素进行比较，使用插入排序，让该序列有序，直到步长为１．

public void shellSort(int[] arr) {
		//确定每次比较的步长 
		for(int step = arr.length/2;step>0;step/=2) {
			//　每个步长序列进行直接插入排序
			for(int i=step;i<arr.length;i++) {
				for(int j=i-step;j>=0;j-=step) {
					if(arr[j+step]<arr[j]) {
						int tmp = arr[j+step];
							arr[j+step]=arr[j];
							arr[j] = tmp;
					}
				}
			}
		}
	}

三.折半插入

算法思想：当插入第i(i>=1)个元素时，前面的V[0],…,V[i-1]等i-1个 元素已经有序，跟直接插入不同的是，折半插入不会与前面的元素一个个比较，而是利用二分搜索的思想，搜索到位置，进行插入

public void binarySerachInsert(int[] arr) {
		for(int i=1;i<arr.length;i++) {
			int right = i-1;
			int left = 0;
			int tmp = arr[i];
			// 第i个元素的值小于有序序列的最大值
			if(tmp<arr[right]) {
				while(left<=right) {
					int mid = (right+left)/2;
					if(tmp>arr[mid]) {
						left = mid+1;
					}else if(tmp<arr[mid]) {
						right = mid-1;
					}else {
						left = left+1;
					}
				}
				for(int j=i;j>left;j--) {
					arr[j] = arr[j-1];
				}
				arr[left] = tmp;
			}
		}		
	}