七大排序之直接插入排序

时间复杂度：  ~

空间复杂度：

稳定性：  稳定      

1、基本思想

直接插入排序是一种简单的插入排序法，其思想就是把待排序的数按照其大小逐个插入到一个已将排好的有序序列中，直到所有的记录插入完为止。

实际中，我们在玩扑克牌时，就与运用了插入排序的思想。

2、代码讲解和实现

       当插入第i(i>=1)个元素时，前面的array[0]、array[1].....array[i-1] 已经排好序。

第一步：定义一个 j 变量并赋值为i-1，同时定义一个 val 变量存储一下 array[i]的值。

第二步：让array[j] 与 val 进行比较

       如果 array[j] 大于 val ， 就把array[j]向前挪一步，也就是 array[j+1] = array[j]。

       如果 array[j] 小于等于 val，就把 val 放到 array[j+1]中。

j 必须 大于等于0 ，要不然会越界。

  public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int j = i-1;
            int val = array[i];
            for(; j >= 0 ; j--){
                if(array[j] > val){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1]= val;
        }

3、特性总结

3.1 时间复杂度：

当数据有序时，直接插入排序耗时最少，为

数据有序时，外循环每遍历一个元素，都比前 i-1个元素都大，内循环相当于没有执行。总的时间就是遍历数组的时间。

当数据逆序时，耗时最多，为

数据逆序，每次插入第 i 个元素，内循环都要遍历 i-1 次。当 n 数排序完，也就是遍历了 次

3.2 空间复杂度：

      因为直接插入排序是内部排序，所以空间复杂度为

3.3 适合场景：

       当数据基本上是有序的时候，使用直接插入排序