本文共 1843 字，大约阅读时间需要 6 分钟。

希尔排序算是对简单插入排序的一种改进，属于一种增量式的排序算法。今年工作普遍不好找，HR经常让手撕代码，所以提前做好准备是最好的应对方式。

一、基本原理

希尔排序听名字就能想到是Shell提出来的，只是对直接插入排序做了一个基本的改进。什么改进呢？

希尔排序是把序列按一定间隔分组，对每组使用直接插入排序；随着间隔减小，一直到1，使得整个序列有序

我们用一张图来表示一下：

上面的d表示间隔，也叫作增量，相同颜色的是一组。上面的元素看着花花绿绿的，不过找俩相同颜色的应该没什么大问题。

到了这有一个问题摆在大家面前了，也就是说一开始这个间隔应该取多少比较好呢？这里有一个公式：

上面10条数据，所以第一个增量是5。

还有一种计算的方式是这样的：增量的初始值是1，通过3*h+1循环计算，一直得到h刚好不大于数组长度。此时就取h做最大间隔。然后继需通过h=(h-1)/3来计算剩下的增量。

下面我们就使用代码来实现一下吧。

二、代码实现

我们来看一下简单的实现：

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

上面就是希尔排序的基本实现算法，希尔排序本身就是对插入排序算法的一种改进，我们如何在这个基础上进一步作出改进呢？

这里有两个思路我觉得需要考虑：

（1）对增量序列优化：使用更加复杂的方式。

（2）对每一趟的插入排序进行优化：在内循环中，总是将较大的元素向右移动。

public static void ShellSort2(int arr[]) {
   		int h = 1;		int step = arr.length;		//优化1		while (h < step / 3) {
   			h = 3 * h + 1;		}		//优化2        int exchanges = 0; //交换次数        //若 arr[index] < arr[index - 1]，则交换两数        for (int index = step - 1; index > 0; index--) {
               if (arr[index]
   
    = 1) {
               // 将数组变为 h 有序            for (int indexI = h; indexI < step; indexI++) {
                   int temp = arr[indexI];                  int indexJ = indexI;                          while (indexJ >= h && (temp
   

ok，这就是其优化，其实最主要的还是插入排序的优化，因为对于希尔排序而言，真正实现的还是插入排序。

三、分析

最佳情况：T(n) = O(nlogn)。

最坏情况：T(n) = O(n²)。 平均情况：T(n) = O(nlogn)。

希尔排序为什么这么有名气，是因为它是第一批突破o(n²)的排序算法之一。如有问题还请指正。

(nlogn)。

最坏情况：T(n) = O(n²)。 平均情况：T(n) = O(nlogn)。

希尔排序为什么这么有名气，是因为它是第一批突破o(n²)的排序算法之一。如有问题还请指正。

转载地址：http://anbdi.baihongyu.com/