排序算法---希尔排序

针对直接插入排序的改进

缩小增量排序 　　不稳定

现将待排序序列恩城多个子序列进行直接插入排序，待整个序列基本有序时，再对整个序列进行直接插入排序

子序列不是简单地逐段分割，而是将相隔某个增量的关键字组成一个子序列，在一趟排序完成之后，缩小增量，直到增量为1（即为一次针对所有关键字的直接插入排序）

增量序列：增量序列中的值应该没有除1之外的公因子，并且，最后一个增量必须为1

    public static void shellSort(int[] array,int increment){
        //将增量一开始设为待排序序列长度的一半，之后，一趟排序完成之后，将增量设为之前增量的一半，直到增量为1
        if(increment>=1){
            for(int i=0;i<increment;i++){//子序列的个数为增量的个数
                //对子序列进行直接插入排序
                for(int j=i+increment;j<array.length;j=j+increment){
                    int temp = array[j];
                    if(array[j-increment] > array[j]){
                        int k=j-increment;
                        for(;k>=0&&array[k]>temp;k=k-increment){
                            array[k+increment] = array[k];
                        }
                        array[k+increment] = temp;
                    }
                }
                System.out.print("---");
                listArray(array);
            }
        }else{
            return;
        }
        listArray(array);
        shellSort(array, increment/2);
    }

原始数据：49 38 65 97 76 13 27 49 0
---0 38 65 97 49 13 27 49 76
---0 13 65 97 49 38 27 49 76
---0 13 27 97 49 38 65 49 76
---0 13 27 49 49 38 65 97 76
0 13 27 49 49 38 65 97 76
---0 13 27 49 49 38 65 97 76
---0 13 27 38 49 49 65 97 76
0 13 27 38 49 49 65 97 76
---0 13 27 38 49 49 65 76 97
0 13 27 38 49 49 65 76 97

时间复杂度O(n^3/2)