数据结构之直接插入排序（算法思想，复杂度分析）以及冒泡排序和直接插入排序的比较

一般来说，插入排序都采用in-place在数组上实现。

具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已经排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2-5；
   eg：
   

代码如下：直接插入排序：

public static void insertSort(int[] array){
    long start = System.currentTimeMillis();
    int n = array.length;
    if(n <= 1){
        return;
    }else{
        for(int i = 1;i < n;i++){
            int value = array[i];
            int j = i - 1;
            for(;j >= 0;j--){
                if(array[j] > value){
                    //搬移元素
                    array[j+1] = array[j];
                }else{
                    break;
                }
                //已找到插入位置
            }
            array[j+1] = value;
        }
    }

评判算法的三个经典问题：

1. 插入排序是一个原地排序算法：从实现过程可以看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度为O（1）；也就是说，这是一个原地排序算法。
2. 插入排序是稳定的算法：在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
3. 插入排序的时间复杂度分析：

如果要排序的数据已经是有序的，并不需要搬移数据从头到尾在有序数据组里面找插入位置，每次只需要比较一个数据就能确定插入的位置。在这种情况下，最好的时间复杂度为：O（n）；

如果数组是倒序的，每次插入就相当于在数组的第一个位置插入新的数据，所有需要移动大量的数据，最坏情况的时间复杂度为：O（n^2）；

对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O（n^2）；

直接排序与冒泡排序的比较：

冒泡排序和插入排序的时间复杂度都是O（n^2），都是原地排序算法；

比较俩段代码：

//冒泡排序中数据的交换操作
if (a[j] > a[j+1]) {
//交换
      int tmp = a[j]; 
      a[j] = a[j+1];  
      a[j+1] = tmp;  
      flag = true; 
    }
}

//插入排序中数据的移动操作
if (a[j] > value) { 
//数据移动
    a[j+1] = a[j]; 
    } 
    else { 
    break;
}

将执行一个赋值语句的时间粗略的记为单位时间，然后分别用冒泡排序和插入排序对一个逆序度为k的数组进行排序；用冒泡排序需要k次交换操作，每次需要3个赋值语句，则交换总耗时是3*k单位时间；而插入排序中数据移动操作只需要k个单位时间。