排序算法---希尔排序（Shell Sort）

前面一口气写了冒泡、选择、插入三个排序算法，感觉今天和他们死磕上了。。。
就不该十一点多还看了几眼。。。然后又掉坑里了，大半夜果然的效率低，看个希尔排序然后居然写了1个小时。。。哇，难受

WTF

抄起键盘一顿梭，就是干

---

严格来说，希尔排序是基于插入排序的思想的，稍后在代码里可以看出，希尔排序又称缩小增量排序，是简单插入排序的增强版本，于1959年由Donald Shell提出。

算法基本思想：

1. 将有n个元素的数组分成n/2份，第1个数据与第n/2+1个数据属于同一份。。。
2. 使用类似插入排序的方法，将同一份的数据排序
3. 然后，再变为n/4份，同样的操作再次排序
4. 不断重复上述3个步骤之后，最后分成n份数据，再通过一次插入排序就完成了全部的排序。

示意图

（网上搜的图，自己不想画了，大半夜要睡觉去了，偷个懒）

代码实现：

import java.util.Arrays;

public class ShellSort {
    public static void sort(int[] arr) {
        int len = arr.length;
        int gap;//步长
        int istIndex;//插入位置索引
        int tmp;
        System.out.println("原始顺序： "+ Arrays.toString(arr));
        //按照步长来分组
        for(gap = len / 2; gap >= 1; gap /= 2) {
            //类似插入排序的方法
            for (int i = gap; i < len; i++) {
                tmp = arr[i];//取出暂存
                istIndex = i;//插入的位置
                while ((istIndex > (gap-1) && tmp < arr[istIndex - gap])) {
                    //插入位置往前移，寻找合适位置
                    arr[istIndex] = arr[istIndex - gap];
                    istIndex -= gap;
                }
                arr[istIndex] = tmp;
            }
            System.out.println("步长为"+gap+"的排序: "+ Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[10];
        //初始化数组
        for (int i = 0; i < 10; i++) {
            arr[i] = (int) (Math.random() * (100 + 1));
        }
        ShellSort.sort(arr);
    }
}

分析小结：

其实希尔排序就是分了组的插入排序，通过这样做可以减少大部分的情况下，数据的移动次数，从而减小时间复杂度，同时希尔排序也是当时冲破O(n^2）的第一批算法之一。

在代码中可以看到，当我们将第二层for循环里的gap视为1的时候，其实接下来的代码就和之前的插入排序一模一样了！！！
其实对于该算法，还可以继续优化，就是改善步长的计算部分，现在是每次变为原来的1/2，其实有个公式h=3*h+1来计算步长，有兴趣的话可以自己研究一下，对于步长的选择是一种魔力，我就不多说了。。。睡觉睡觉了，不能在修仙了zzz