希尔排序是建立在插入排序上的

写了一个插入排序，接着写希尔排序，分组之后的希尔排序就是进行好几次插入排序，这样子不是更费力了吗，数据结构与算法的一些简单的疑惑

希尔排序不是插入排序哦，发个希尔排序的算法给你参考一下。

package T5;

public class ShellSort {
    int a[];
    public ShellSort() {
        a = new int[]{8,19,2,3,100,99,1000,888,-1,0};
        
        
        /*
         * 第一次是d=5组
         * （8,99），（19,1000），（2,888），（3，-1），（100,0）
         * 交换
         * （8,99），（19,1000），（2,888），（-1,3），（0,100）
         * 8,19,2，-1,0,99,1000,888,3,100
         * 第二次是d=2组
         * (8,2,0,1000,3),(19,-1,99,888,100)
         * 交换
         * (0,2,3,8,1000),(-1,19,99,100,888)
         * 0,-1,2,19,3,99,8,100,1000,888
         * 第3次是d=1时，其实只有一组，就是直接插入排序
         * 
         * 
         * */
    }
    public ShellSort(int a[]) {
        this.a = a;
    }
    
    public void shellSort(){
        int n = a.length;
        /*分组排序：分组的规则
         * 1.d = 数组长度/2;
         * 2.d = d/2;
         * 
         */
        for(int d=n/2;d>0;d/=2){
//            System.out.println("d="+d+"时的排序情况");
            //插入排序
            for(int i=0;i<d;i++){ //增量为1时排序结束
                //遍历所有子序
//                System.out.print(i+"\t");
                for(int j=i+d;j<n;j+=d){
//                    System.out.print(j+"\t");
                    //对每个子序进行插入排序
                    int insertNode = a[j];
                    int k=j-d;
                    while(k>=i&& a[k]>insertNode){
                        a[k+d]=a[k];
                        k=k-d;
//                        print();
                    }
                    a[k+d]=insertNode;
//                    print();
                }
//                System.out.println("--------------------");
                
            }
//            print();
        }
        print();
    }
    public void print(){
        for (int e : a) {
            System.out.print(e+"\t");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        System.out.println("排序前");
        shellSort.print();
        shellSort.shellSort();
//        shellSort.print();
    }
}

希尔排序不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间的时间复杂度为O()，希尔排序时间复杂度的下界是n*log2n。

首先我们要明白几点：
1.对于基本有序的数列，对他进行插入排序的复杂度接近O(n)。
2.在数列长度非常小时，直接进行插入排序的复杂度O(n^2)是接近于O(n)的
其次，我们再来考虑希尔排序的过程：
1.在一开始，增量较大时，每个小数列的长度很小，它的复杂度也很小
2.当增量逐渐减小，每个小数列的长度增加，复杂度也成平方级增加。真的是这样吗？那前几次的排序还有何意义？其实，在前几次的排序后，数列逐渐变得基本有序，那么每次排序的复杂度也接近于O(n)
综合以上几点，我们可以得到，希尔排序的时间复杂度在大部分情况下优于直接插入排序。