历史
希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根据Metzner本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”
希尔排序是基于插入排序的以下两点性质而提出改进方法的：插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
基本思想
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2，该方法实质上是一种分组插入方法。
应用
实时调度策略中,EDF算法应用最为广泛,但其在系统过载的情况下,仅由任务截止期决定任务执行顺序,使得截止期错失率非常高,且系统收益小。近年来,出现了一些改进的EDF算法,综合考虑了时间和执行价值,但未加入能量因素,对于能量有限的系统,充分利用能量是极其重要的。
针对这一问题,提出一种基于希尔排序的动态优先级调度算法,在系统过载时,综合考虑任务截止时间、执行价值、消耗能量三种因素确定任务优先级,通过希尔排序算法选出优先级高的任务加入优先调度子集,进行率先调度。实验结果表明,该算法不仅能降低任务截止期错失率,还能提高系统执行收益。
