一、直接插入排序

 

整个区间被分为

 

有序区间

 

无序区间

 

每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入。

 

   public static void insertSort（int[] arr）{

 

        for （int i = 1; i < arr.length; i++） {

 

            int tmp = arr[i];

 

            int j = i - 1;

 

            for （ ; j >= 0 ; j--） {

 

                if （arr[j] > tmp）{

 

                    arr[j + 1] = arr[j];

 

                }else{

 

                    //arr[j + 1] = tmp;//只要j回退的时候，遇到了比tmp小的元素，就结束了这次的比较

 

                    break;

 

                }

 

            }

 

            //j回退到了小于0的地方

 

            arr[j + 1] = tmp;

 

        }

 

    }

 

    public static void main（String[] args） {

 

        int[] array = {6,10,9,3,5};

 

        insertSort（array）;

 

        System.out.println（Arrays.toString（array））;

 

    }

 

}

 

输出结果：

 

时间复杂度：最好O（N）–>数据本身是有序的；

 

* 最坏O（N^2）；–>数据逆序；

 

* 当一组数据，数据量不大且趋近于有序，此时用插入排序时间更快，越有序越快。

 

空间复杂度：O（1）；

 

稳定性：稳定的排序；

 

一个稳定的排序可以实现为不稳定的排序，但是一个本身就不稳定的排序不可以变成稳定的排序。

 

二、希尔排序

 

希尔排序法又称缩小增量法。

 

希尔排序法的本质是插入排序，只不过是将待排序的序列按某种规则分成几个子序列，分别对几个子序列进行直接插入排序。这个规则就是增量，增量选取很重要，增量一般选序列长度一半，然后逐半递减，直到最后一个增量为1，为1相当于直接插入排序。

 

public static void shell（int[] arr,int gap）{

 

    for （int i = 1; i < arr.length; i++） {

 

        int tmp = arr[i];

 

        int j = i - gap;

 

        for （; j >= 0 ; j-=gap） {

 

            if（tmp < arr[j]）{

 

                arr[j + gap] = arr[j];

 

            }else{

 

                break;

 

            }

 

        }

 

        arr[j+gap] = tmp;

 

    }

 

}

 

    public static  void shellSort（int[] arr） {

 

        int gap = arr.length;

 

        //增量在缩小，最后一组的增量为1

 

        while （gap > 1）{

 

            gap /= 2;

 

            shell（arr,gap）;

 

        }

 

        shell（arr,1）;

 

    }

 

    public static void main（String[] args） {

 

        int[] array = {9,1,2,5,7,4,8,6,3,5};

 

        shellSort（array）;

 

        System.out.println（Arrays.toString（array））;