• 介绍

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

• 算法步骤

1.将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

2.从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

• 动画演示

• 直接插入排序

public int[] sort(int[] sourceArray) {
        long t1 = System.currentTimeMillis();
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        for(int i = 1; i < arr.length; ++i){
		int temp = arr[i];
		int j = i;
		while(j > 0 && temp < arr[j - 1]){
			arr[j] = arr[j - 1];
			j--;
		}
		if(i != j){
		   arr[j] = temp;
		}
	}
	return arr;
    }

• 折半插入排序

public int[] sort(int[] sourceArray) {
        int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
        int low,high,m,temp,i,j;
        for(i = 1;i<arr.length;i++){
            low = 0;
            high = i-1;
            while(low <= high){
                m = (low+high)/2;
                if(arr[m] > arr[i]) {
                    high = m - 1;
                } else {
                    low = m + 1;
                }
            }
            temp = arr[i];
            for(j=i;j>high+1;j--){
                arr[j] = arr[j-1];
            }
            arr[high+1] = temp;
        }
        return arr;
    }