因为希尔排序的核心思想是插入排序，所以本篇将两篇排序一起记录

本篇内容：

• 插入排序
• 希尔排序

（一）插入排序

算法思想：

把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素；

排序过程即每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。

代码实现：

（注意：ArrayBase在第一篇中已给出代码）

/** *  */package com.cherish.SortingAlgorithm;/** * @author acer * */public class Chapter_3_插入排序 extends ArrayBase {    /**     *      */    public Chapter_3_插入排序() {        // TODO 自动生成的构造函数存根    }    /**     * @param args     */    public static void main(String[] args) {        // TODO 自动生成的方法存根        int[] array = new int[] {3,4,7,9,2,5,1,8,6};        printArray(array);        insertSorting(array);        printArray(array);    }        /*     * 把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素；     * 排序过程即每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。     * */    public static void insertSorting(int[] array) {        // TODO 自动生成的方法存根        int arrayLength = array.length;        for(int i = 1 ; i < arrayLength ; i++)        {            for(int j = i ; j > 0;j--)            {                if(array[j]

 

实现结果：

（二）希尔排序

 算法思想：

希尔排序的实质就是分组插入排序,又称缩小增量法；

将整个无序序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，

然后依次缩减增量再进行排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下，效率是很高的，因此希尔排序在时间效率上有很大提高

/** *  */package com.cherish.SortingAlgorithm;/** * @author acer * */public class Chapter_4_希尔排序 extends ArrayBase {    /**     *      */    public Chapter_4_希尔排序() {        // TODO 自动生成的构造函数存根    }    /**     * @param args     */    public static void main(String[] args) {        int[] array = new int[] {3,4,7,9,2,5,1,8,6};        printArray(array);        shellSorting(array);        printArray(array);            }            /*     * 希尔排序的实质就是分组插入排序,又称缩小增量法     * 将整个无序序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，     * 然后依次缩减增量再进行排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。     * 因为直接插入排序在元素基本有序的情况下，效率是很高的，因此希尔排序在时间效率上有很大提高     * */    public static void shellSorting(int[] array)    {        int arrayLength = array.length;//数组长度        int gap = arrayLength/2;//子序列数        while(gap>=1)        {            for(int i = gap;i < arrayLength;i++)            {            //    int j=i-gap;                for(int j = i-gap;j>=0;j--)                {                    if(array[j]>array[i])                    {                        swap(array,j,i);                    }                    }                                        }            gap = gap/2;            printArray(array);        }    }}

实现结果：