插入排序

插入排序思想
1、分类：把数组R的数据分成2类，A = { 已排序的子数组 }，B = { 未排序的子数组 }。
2、排序：遍历B，依次取B中各个数据插入到A中的适当位置。

直接插入排序
设数组 R[0,1,...,n] = { A[0,1,...,i-1], B[i,i+1,...,n] } （数组从0开始计数，i=1,2,...,n-1)。
遍历数组R： i从1到n-1，i始终指向B的第一个元素，拿R[i]=B[i]倒序到A中比较（A[i-1]，A[i-2],...,A[0]），若A中当前比较值A[j]比B[i]大，则把A[j]往后挪一位，B[i]继续向前倒序比较；否则，B[i]插入A[j]后面那个位置A[j+1]。

public class InsertSort {
	
	public int[] sort(int[] arr){
		for(int i=1; i<arr.length; i++){
			int j=i-1,tmp=arr[i];
			while(j>=0 && arr[j]>tmp){
				arr[j+1] = arr[j];
				j--;
			}
			arr[j+1] = tmp;
		}
		return arr;
	}
	
}

希尔排序
希尔排序采用分组插入思想：1、取一个小于R.length的整数gap1，把R分成gap1个小组(所有距离为gap1的数据放在同一小组)，在各组内进行直接插入排序。 2、取小于gap1的整数gap2，重复第1步的分组和排序。 3、重复第2步，直至gap(k)=1，整个重复过程中gap(k)<gap(k-1)<……<gap2<gap1，其中当gap(k)=1时相当于所有记录放在同一组中进行插入排序。

public class ShellSort {
	
	public int[] sort(int[] arr){
		for(int gap=arr.length; gap>0; gap=gap/2){
			for(int i=gap; i<arr.length; i++){
				int j=i-gap,tmp = arr[i];
				while(j>=0 && arr[j]>tmp){
					arr[j+gap] = arr[j];
					j = j - gap;
				}
				arr[j+gap] = tmp;
			}
		}
		return arr;
	}

}

 

测试用例

public class SortTest extends TestCase {

	public int[] getSortDatas(){
		return new int[]{11,14,9,13,20,5,12,3,18,4,0,19,1,15,8,2,16,7,6,17,10};
	}
	
	public void testInsertSort(){
		InsertSort sortTool = new InsertSort();
		int[] arr = getSortDatas();
		System.out.print("排     序     前：");
		PrintUtils.printIntArr(arr);
		int[] arr1 = sortTool.sort(arr);
		System.out.print("升序排序后：");
		PrintUtils.printIntArr(arr1);
	}
	
	public void testShellSort(){
		ShellSort sortTool = new ShellSort();
		int[] arr = getSortDatas();
		System.out.print("排     序     前：");
		PrintUtils.printIntArr(arr);
		int[] arr1 = sortTool.sort(arr);
		System.out.print("升序排序后：");
		PrintUtils.printIntArr(arr1);
	}
	
}

 
运行结果：

插入排序

排    序    前：[11,14,9,13,20,5,12,3,18,4,0,19,1,15,8,2,16,7,6,17,10]

升序排序后：[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

 

希尔排序

排    序    前：[11,14,9,13,20,5,12,3,18,4,0,19,1,15,8,2,16,7,6,17,10]

升序排序后：[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

总结：
1、直接插入排序，是一种稳定的排序算法；希尔排序，是一种不稳定的排序算法。

2、直接插入排序，在表初态为正序时取得最好时间复杂度为O(n)，在表初态为反序时取得最坏时间复杂度为O(n^2)。

3、希尔排序时间性能优于直接插入排序的原因：
    a、直接插入排序，在表初态为正序时所需时间最少。
    b、希尔排序采用分组插入，使得每次在小数组里使用直接插入排序时，小数据的长度n较小。当n较小时，n和n^2差别

         不大，由总结第2条可知，对小数组直接插入排序因表初态影响时间复杂度较小，即小数组直接插入排序较快。

    c、希尔排序，先用小数组排序，再用大数组排序。该排序算法运行到后面时，经过小数组排序的大数组也接近有序状

         态，由a可知，此时对大数组进行插入排序速度较快。

4、表面感觉希尔排序比较的次数比直接插入排序多，直接插入排序只用2个循环，希尔排序却要用3个循环。

       这是表面感觉，实际分析一下这2个算法都是在进行下面的比较，只是比较的方法不一样而已：

       都是拿R[i] (i=1,2,...,R.length-1)倒序和表初态排在它前面的数据R[j](j=0,1,...,i-1)进行比较。