希尔排序

概述：

首先将数组的一半作为步数，以步数作为起始值，通过插入排序，与之前的以增量为步数的成员进行比对，大的放后面，小的放前面，基本形成有序，之后步数减半，重复以上步骤，直到从小到大排序。

比较插入排序，会减少大量的插入步骤。

场景分析：

4，2，5，1，3

将数组的一半作为步数，

以步数作为起始值，

            ↓

            5，

4，2，    1，3

通过插入排序，与之前的以增量为步数的成员进行比对，

↓

4，2，5，1，3

后一位起始值   

              ↓ 

              1，

4，2，5，    3

大的放后面，小的放前面，

      ↓         ↓

4，1，5，2，3

3

4，1，5，2，

4，1，3，2，5

3，1，4，2，5

↑

这样基本形成大值在右，小值在左，

然后步数减半，重复以上步骤，

      1，

3，    4，2，5

1，3，4，2，5

          4

1，3，    2，5

1，3，4，2，5

               2，

1，3，4，    5

1，3，2，4，5

直到从小到大有序。

1，2，3，4，5   

JAVA实现：

package Sorts;

public class ShellSort {

    public static void main(String[] args) {

        int[] array = {5,4,3,2,1};

        shellSort(array);

        for (int i = 0; i < array.length; i++) {

        System.out.println(array[i]+",");

        }

    }

    public static void shellSort(int[] array) {

        int length = array.length;

        int temp = 0;

        int j = 0;

        //首先将数组的一半作为步数，     之后步数减半，

        for (int add = length / 2; add >= 1; add /= 2) {

            //以步数作为起始值，

            for (int i = add; i < length; i++) {

                    temp = array[i];

                    //通过插入排序，与之前的以增量为步数的成员进行比对，

                    for (j = i; j >= add; j -= add) {

                            if(temp < array[j - add]) {

                            //大的放后面，

                            array[j] = array[j - add];

                            }else {

                                    break;

                            }

                    }

                    //小的放前面，

                    array[j] = temp;

                    }

            }

        }

}