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

  发布日期:   2018-06-13
  最新修改:   2020-10-23
  阅读次数:   85 次

一、前言:
  • 我们在上一章分析了插入排序的实现步骤及用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序列的有序化。
  • 希尔排序对于大型序列和任意序列,处理效果都是很好的。
  • 希尔排序对于插入排序和选择排序在大型序列排序上,优势是非常明显的。

   转载规则

《算法回顾篇:插入排序进阶之希尔排序字》GajAngels 采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。