算法回顾篇：插入排序进阶之希尔排序

• 更多分享：www.catbro.cn

一、前言：

• 我们在上一章分析了插入排序的实现步骤及用kotlin实际实现了该算法；
• 本章节我本将学习插入排序的改进算法希尔排序；

二、希尔排序的诞生

• 希尔排序又称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
• 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
• 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
• 而最糟糕的情况就是一个逆序的序列，此时，我们每次的移动次数和比较次数都是最大的。遇到这种情况是，插入排序是不可接受的。

三、希尔排序实现流程

• 代码如下：

  class XESortDemo {
      fun sort(list: Array<Comparable<Any>>) {
        //1、设初始增量因子为h=1；
          var h: Int = 1;
          //2、判断判断 h< list.size/3 是否成立，
          while (h < list.size / 3) {
            //3、成立则执行h=h*3+1；
            //为何是加1呢？这里留给你一个思考的点，有问题可以给我留言哦。
              h = h * 3 + 1;
          }
           //4、判断 h>=1是否成立（当h<1时，此时希尔排序就完成了）
          while (h >= 1) {
          //5、外循环，从h到数组的最后一个元素（h会不断减小，最终h=1时即如一般的插入排序一样，但此时已经不会在出现插入排序最糟糕的情况了）
              for (i in h..(list.size - 1)) {
                  var j = i;
                  while (j >= h && SortUtils.less(list[j], list[j - h])) {
                      SortUtils.exchange(list, j, j - h);
                      j = j - h;
                  }
              }
              h = h / 3;
          }
  
      }
  }
  

四、总结：

• 希尔排序很好的避免了插入排序最糟糕的情况，其先使局部序列有序化，最后一次再回归到简单的插入排序。
• 其思想为使序列中间隔h的序列都是有序的序列，在进行排序时，如果h足够大，我们就首先能对很远的元素进行排序，这样随着h的缩小，我们能更好地实现小h序列的有序化。
• 希尔排序对于大型序列和任意序列，处理效果都是很好的。
• 希尔排序对于插入排序和选择排序在大型序列排序上，优势是非常明显的。