算法与数据结构基础（二）排序基础2.插入排序

一句话概括：就像玩扑克牌时，每来一张新牌都要选择一个合适的插入位置，代码：循环从头依次抽“新牌”，与位置较前的依次比较和插入 直到插入最合适的位置。

最差情况复杂度：O（n2），但是在数据近乎有序的时候甚至超过O(nlogn)

一、算法

	public void insertSort(int arry[])
	{
		for (int i = 1; i < arry.length; i++) {
			
			for(int j=i;j>0&&arry[j]<arry[j-1];j--)
			{
				int tmp = arry[j];
				arry[j] = arry[j-1];
				arry[j-1]=tmp;
			}
		}
	}

外层循环是依次取数据，内层循环是依次和前面的比（位置不对则交换，则原目标数前移1，而j--，那么目标数就一直是j，那么就一直拿目标数arry[j]和前面依次的arry[j-1]比）。

注意：内层循环里可能一开始就不会进行（只有arry[j]<arry[j-1]才进行），这是通常优于选择排序的地方。

二、与选择排序比较

import java.util.Arrays;

public class test2 {

	public static void main(String[] args) {
		
		Integer[] arr1 = SortTestHelper.generateRandomArray(100000, 0, 100);
		Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
		
		SortTestHelper.testSort("test2", arr2);
		
		SortTestHelper.testSort("test1", arr1);
		
	}
	
	public static void sort(Comparable arry[])
	{
		for (int i = 1; i < arry.length; i++) {
			
			for(int j=i;j>0&&arry[j].compareTo(arry[j-1])==-1;j--)
			{
				Comparable tmp = arry[j];
				arry[j] = arry[j-1];
				arry[j-1]=tmp;
			}
		}
	}
}

输出：

耗时：1 ms!
排序成功!
耗时：30143 ms!
排序成功!

差距恐怖。。。。

三、插入排序的改进

在之前给出代码中应该可以发现一个数据插入了很多次不同的地方，那么这个点是可以改进的。

public static void sort(Comparable arry[])
	{
		for (int i = 1; i < arry.length; i++) {
			
			Comparable target = arry[i];//暂时存着要移动的数据
			int j;//最后要插入的位置
					
			for(j=i;j>0&&target.compareTo(arry[j-1])==-1;j--)//判断放到前一个是否合理
			{
				arry[j] = arry[j-1];//放到前一个合理则要把前面的往后挪
			}
			arry[j]=target;//放到合适的位置
		}
	}

四、插入排序在 数据越接近有序的时候 速度越快。因为内层循环会直接结束

很有实际意义，因为实际数据中大多数时候 数据都是有一定顺序的只不过乱了很少的几个要排序。