一文带你读懂排序算法（二）：希尔排序算法

上文我们一起学习了解了3种基础的简单排序算法（冒泡算法/简单选择排序算法/快速插入排序算法），这三种算法简单归纳是：

冒泡：通过元素之间的全量比较，达到排序的目的；

简单插入排序算法：通过组合元素为小序列，通过比较将元素插入到特定位置；

快速选择排序：全量比较抽出最大值或最小值，放到数组的开头或者末尾。

以上的算法，在数据量较小且数据大部分有序的情况下，性能可以表现优异；但在生产环境下，面临的往往是杂乱无章且数据量极大的场景，这时候如果继续依赖基础算法，会导致效率低下，或给服务器性能带来较大的压力。所以需要更有效的算法，来帮助我们解决在大数量场景的问题。

下文一起学习下“插入排序”的优化算法 -- “希尔排序”。

背景与基本思想

背景

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

概念

希尔排序也被称为“缩小增量排序”，基本原理是：先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个排序序列基本有序后，最后再对所有元素进行一次直接插入排序。

具体步骤如下：

1）选择一个步长序列（t1,t2,···,tk），满足ti > tj(i<j) ，tk=1;

2）按步长序列个数k，对待排序序列进行k趟排序；

3）每趟排序，根据对应的步长ti，将待排序列分割为ti个子序列，分别对各个子序列进行直接插入排序；

注意：当步长因子为1时，所有元素作为一个序列来处理，其长度为n。

通俗易懂的例子

下面用一个例子来说明“希尔排序”的执行过程，以数组{26,53,67,48,57,13,48,32,60,50}为例。

步骤1：数组长度为10，因此第一个步长t1取（10/2）= 5，第二步长t2取（5/2）= 3，第三步长t3取（3/2）= 1。

（挖个坑，为何第二步长选择向上取整得3，第三步长向下取整得1呢？这个留到后面再解释）

步骤2：步长序列长度为3，因此需要进行3趟排序

步骤3：每趟排序，根据对应的步长ti，组内排序

第1趟排序

第2趟排序

第3趟排序

算法实现

Demo

/**
 * <p>
 *     希尔排序算法
 *     希尔排序是1959年，Shell发明的，这是第一个突破O(n2)的排序算法，他与直接插入排序不同的是，他会优先比较距离较近的元素。因此，希尔排序又叫做缩小增量排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
 *     希尔排序的关键，并非随便的分组然后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式移动，使得排序效率提高。
 * </p>
 */

public class ShellSort {
  public static void main(String[] args)
  {
    int i = 0;
    int a[] = {6, 5, 3, 1, 8, 7, 2, 4, 9, 0};
    int len = a.length;
    shellSort(a);
  }

  private static void shellSort(int arr[]){
    int length = arr.length;
    int i,j;
    int h;
    int temp;
    // 确定步长h(确定步长序列以及需要几趟完成希尔排序)
    for (h = length/2; h > 0; h = h/2){
      // 遍历子序列，每次下标增量为h
      for (i = h; i < length; i ++){
        temp = arr[i]; //待插入元素
        // 子序列插入比较。可能会有疑问，为什么不是按照图示的[32,26,60]来逐个比较呢？因为代码不需要像图示那样，额外花销来维护第几趟。
        // 当i自增到60的下标时，下面的for循环，相当于会插入比较到[26,32]的子序列里面了。这是非常秒的！
        for (j = i-h; j >= 0; j -= h){
          if (temp < arr[j]){
            //较大值往后挪
            arr[j + h] = arr[j];
          } else {
            break;
          }
        }
        // 此时的j<0，因此temp赋值的意思是，将原本较小值移动到前面
        arr[j+h] = temp;
      }
    }

    for (int a=0; a<arr.length; a++){
      System.out.println("序列的第"+a+"元素是："+arr[a]);
    }
  }
}

结果输出

序列的第0元素是：0
序列的第1元素是：1
序列的第2元素是：2
序列的第3元素是：3
序列的第4元素是：4
序列的第5元素是：5
序列的第6元素是：6
序列的第7元素是：7
序列的第8元素是：8
序列的第9元素是：9

复杂度分析

总结与填坑

1）文章开头，在确定步长序列时，挖了一个坑（没有给出具体的确定步长的方法），这里给大家做个解答。

答：其实希尔排序的步长序列，常用的增量是以2为跨度的增量，所以每一次排序的时候那么增量都为上一次的一半，这也就是我们常说的希尔增量。

2）希尔排序首先要解决的问题是使得数组内部的序列大部分是有序的，怎么样实现这个想法呢？

答：方法是将数组按照不同的间隔分成若干个序列，在序列内进行直接插入排序，最后进行一趟直接插入排序。一般来说算法的时间复杂度低于O（n ^ 2），但是在极端的情况下，希尔排序的时间复杂度仍然是O(n ^ 2)，甚至比直接比直接插入排序更慢，因为数组的在划分增量的时候每一次都没有在内部移动元素进行排序，因为在划分的序列中都是有序的，等到最后一次增量为1的时候那么菜进行直接插入排序这个时候排序就比直接插入排序更慢了。

3）希尔排序是稳定排序吗？

答：否。因为步长确定以后，每个子序列内部会涉及到元素的交换，所以两个相同元素，可能在步长不一样的情况下，导致位置挪动。（由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的）

—END—