插入排序

插入排序算法重复地将一个特定的值插入到表中已有序的子序列中，从而完成一组值的排序。每次将每个未排序的元素插入到有序子序列中的合适位置，直到表中全部元素都有序。

插入排序算法的一般策略是：对表中最前面的两个元素的值进行排序，必要的话就进行交换。将表中第三个值插入到前两个（已有序）值组成的子序列中的合适位置。然后将第四个值插入到表中前三个值中的合适位置。每次插入时，已有序的子序列中元素个数增加一个。

继续这个过程，直到表中所有的元素全部有序时为止。插入过程要求，数组中的其他元素都要向后移动，为新插入的元素腾出空间。下图所示为插入排序过程。

插入排序示例图

与选择排序的实现一样，insertionSort方法用双重循环来排序对象数组。但在插入排序中，外层循环控制下一个元素在数组中的插入位置。内层循环将当前插入元素的值与它前面位置存储的值（已经构成了整个表的有序子序列）进行比较。如果当前插入元素小于position所指位置的值，则将这个值右移。继续右移过程，直到腾出一个合适的位置来接受插入元素。外层循环的每次迭代都使得表中有序子序列延长一个，直到整个表有序时为止。

    public static void insertsort(int arr[]){                
        for(int i = 1;i < arr.length; i ++){
            if(arr[i] < arr[i-1]){//注意[0,i-1]都是有序的。如果待插入元素比arr[i-1]还大则无需再与[i-1]前面的元素进行比较了，反之则进入if语句
                int temp = arr[i];
                int j;
                for(j = i-1; j >= 0 && arr[j] > temp; j --){                
                        arr[j+1] = arr[j];//把比temp大或相等的元素全部往后移动一个位置            
                }
                arr[j+1] = temp;//把待排序的元素temp插入腾出位置的(j+1)
            }            
        }
        
    }
        
    public static void main(String[] args) {
        int array[] = {4,2,1,5};
        
        System.out.println("排序之前：");
        for(int element : array){
            System.out.print(element+" ");
        }
        
        insertsort(array);
        System.out.println("\n排序之后：");        
        for(int element : array){
            System.out.print(element+" ");
        }
    }
}

结果

排序之前：  
4 2 1 5 
排序之后：
1 2 4 5 

算法分析：

1.当元素的初始序列为正序时，仅外循环要进行n-1趟排序且每一趟只进行一次比较，没有进入if语句不存在元素之间的交换(移动)。此时比较次数(Cmin)和移动次数(Mmin)达到 最小值。

Cmin = n-1 Mmin = 0;

此时时间复杂度为O(n)。

2.当元素的初始序列为反序时，每趟排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移(arr[j+1] = arr[j])，i个元素后移移动次数当然也就为i 了，再加上temp = arr[i]与arr[j+1] = temp的两次移动，每趟移动的次数为i+2,此时比较次数(Cmin)和移动次数(Mmin)达到最小值。

Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2)

Mmax = (1+2)+(2+2)+...+(n-1+2) = (n-1)*(n+4)/2 = O(n2) (i取值范围1~n-1)

此时时间复杂度为O(n2)。

3.在直接插入排序中只使用了i,j,temp这3个辅助元素，与问题规模无关，所以空间复杂度为O(1).

4.在整个排序结束后，即使有相同元素它们的相对位置也没有发生变化，

              如：5,3,2,3排序过程如下

                 A--3,5,2,3

                 B--2,3,5,3

                 C--2,3,3,5

               排序结束后两个元素3的相对位置没有发生改变，所以直接插入排序是一种稳定排序。

参考文章：图解插入排序--直接插入排序