希尔排序可以看成优化之后的插入排序 首先想一下插入排序的思想
插入排序的思想和选择排序其实有一点像 都是把数据分为2个区域 已经有序的区域和无序的区域 可以先看插入排序的代码

 public static void insertSort(int [] arr)
    {
        int j;
        int wanToInsert;//想要插入的元素 从1开始
        for (int i = 1; i < arr.length; i++)
        {
            wanToInsert=arr[i];
            j=i-1;
           //从i-1开始  往前比较 如果当前想要插入的比j位置的元素小 那就把j位置的元素往后挪1位  因为已经确定是当前的0到j是有序的 所以不会出现覆盖使得数据丢失的情况 
            while (j>=0&&wanToInsert<arr[j])
            {
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=wanToInsert;
        }

第一个元素组成的序列已经可以看成是有序的了 所以只需把后面的len-1个元素插入到对应位置就可了 所以是for 1 到 <len 对于每个想要插入的元素 依次往前检测 （以从小到大的排序规则举例子） 我当前要插入的元素如果比你前面有序区的小 说明我应该在你前面 所以该元素需要往后移动 所以就有了这个循环

 while (j>=0&&wanToInsert<arr[j])
            {
                arr[j+1]=arr[j];
                j--;
            }

一直下去 最后找到的位置就是不比我当前的元素小的位置 有两种可能 就是我当前需要插入的元素是最小的 那最后j的值就是-1了 或者是不是最小的 那就一个对应的 位置 这个位置上的值我不比它小 所以我应该插入在它后面的位置
于是arr[j+1]=wantToInsert 因为这个前面是有序的 所以不会出现直接覆盖导致数据丢失的问题
再来看希尔排序 希尔排序呢 相当于把 一个数组分为几组对每一组进行插入排序 排序完成之后 更换分组方式 这里表现为 减小分组间隔 直到分组间隔为1 此时已经变成了普通的插入排序 但是此时的序列已经可以使得插入排序的效率很高了
分组方式如下 假设分组间隔为step
那就是 0 0+step 0+2*step ...... 为一组
以此类推
代码中的第二个for循环 大概可以看成是 同时对多组进行插入排序 而不是让每一组插入排序完成 再进行下一组 代码中是让i从step开始 这正好是分组后的第一组的第二个元素 也就是第一组的第一个想插入的元素 依旧是按照插入排序的规则来插入 只是j--改成了j-=step
代码如下

public static void shellSort(int []arr)
    {
       int len=arr.length;
       int wanToInset;
       int j;
        for (int step=len/2; step >=1; step/=2)
        {
            for (int i = step; i < arr.length; i++)
            {
                wanToInset=arr[i];
                j=i-step;
                while (j>=0&&wanToInset<arr[j])
                {
                    arr[j+step]=arr[j];
                    j-=step;
                }
                arr[j+step]=wanToInset;
            }
        }
    }

最后贴一个排序的过程 实例

原数组:  [33, 49, 22, 4, 44, 43, 26]
分组间隔为 :3
[4, 49, 22, 33, 44, 43, 26]
[4, 44, 22, 33, 49, 43, 26]
[4, 44, 22, 33, 49, 43, 26]
[4, 44, 22, 26, 49, 43, 33]
分组间隔为 :1
[4, 44, 22, 26, 49, 43, 33]
[4, 22, 44, 26, 49, 43, 33]
[4, 22, 26, 44, 49, 43, 33]
[4, 22, 26, 44, 49, 43, 33]
[4, 22, 26, 43, 44, 49, 33]
[4, 22, 26, 33, 43, 44, 49]
排序后的数组: [4, 22, 26, 33, 43, 44, 49]