希尔排序图文详解+代码实现

希尔排序也是一种插入排序，它是直接插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(1)

下面先介绍一下直接插入排序，理解了直接插入排序，希尔排序就很好理解了，实现代码也是由直接插入排序的代码改进得到。

首先将第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（每次插入后有序序列长度+1，未排序序列长度-1）

public class InsertSort {
    public int[] sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            for (; j >= 0 && arr[j] > temp; j--) {
                arr[j + 1] = arr[j];
            }
            arr[++j] = temp;
        }
        return arr;
    }
} 

希尔排序的基本思想是：先将整个待排序的记录序列按照一定的增量分割成为若干子序列分别进行直接插入排序。待整个序列中的记录"基本有序"时，再对全体记录进行直接插入排序（增量为1时）。
通常增量的大小依次是N/2、N/2/2、…、N/2^i、…、1。

比如有以下数组，N=10

第一轮：
增量gap=N/2=5，整个数组被分为5个子序列，分别是[8,3]、[9,5]、[1,4]、[7,6]、[2,0]，分别进行直接插入排序。

分别对子序列排序后为

第二轮：
增量gap=N/2/2=2，整个数组被分为2个子序列，分别是[3,1,0,9,7]、[5,6,8,4,2]，分别进行直接插入排序。

分别对子序列排序后为

第三轮：
增量gap=N/2/2/2=1，整个数组被分为1个子序列。此时可以看做没有分组，而是对全体记录进行直接插入排序。

经过前两轮的排序，此时该数组已经基本有序，所以这时的直接插入排序效率非常高，无需大量移动数组元素即可完成整个数组的排序。

可以基于直接插入排序的代码进行改进

public class ShellSort {
    public int[] sort(int[] arr) {
        //经典希尔算法的gap值为N/2, N/4, ...... 直到gap值为1
        for (int gap = arr.length / 2; gap >= 1; gap = gap / 2) {
            //gap值为多少，就会有多少个子数组，且每一个子数组的开头均是原数组的前gap个元素
            //对每一个子数组进行插入排序
            for (int n = 0; n < gap; n++) {
                //对每一个子数组进行插入排序，不过要注意子数组每个元素间的间隔为gap
                for (int i = n + gap; i < arr.length; i = i + gap) {
                    int temp = arr[i];
                    int j = i - gap;
                    for (; j >= 0 && arr[j] > temp; j = j - gap) {
                        arr[j + gap] = arr[j];
                    }
                    j = j + gap;
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}

希尔排序是对直接插入排序的改进版本，执行效率更高。

随机生成一个大小为100000的数组，使用直接插入排序，计算执行时间

    public static void main(String[] args) {
        //定义一个长度为100000的数组
        int[] arr = new int[100000];
        Random random = new Random();
        //随机生成int依次向数组当中插入
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(1000000);
        }

        //实例化自己编写的直接插入排序类
        InsertSort insertSort = new InsertSort();
        long start = new Date().getTime();
        //对数组进行排序
        int[] sort = insertSort.sort(arr);
        long end = new Date().getTime();
        System.out.println("耗时" + (end - start) + "毫秒");

        //验证是否有序
        boolean flag = true;
        for (int i = 0; i < sort.length - 1; i++) {
            if (sort[i] > sort[i + 1]) {
                flag = false;
                break;
            }
        }
        System.out.println("是否有序？" + (flag ? "是" : "否"));
    }

执行结果为

耗时746毫秒
是否有序？是

使用直接插入排序消耗了746ms的时间

接下来使用希尔排序，执行结果为：

耗时14毫秒
是否有序？是

可以看到同样是对大小为100000的随机数组进行排序，希尔排序仅仅使用了14ms，效率大大提高