Question

希尔排序的思想

Answer 1

希尔排序算法思想：希尔排序是按照下标增量进行分组，对每组使用插入排序算法进行排序，随着增量减少，每组包含的关键字越来越多，增量减到1时，整个序列被分为一组，算法终止。

我们以增序排序为例，希尔排序基本步骤：选择初始增量gap=length/2，缩小增量继续以gap=gap/2的方式进行，直到增量gap=1为止，增量的每次变化都会将原始序列划分为若干组，分别对每一组进行插入排序。

每一次通过增量划分组进行插入排序宏观上小的数移到了前面，大的数移到了后面，最后增量gap=1进行插入排序后就是最终的有序序列。

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

发展历史

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由希尔在1959年所发表的论文“A high-speed sorting procedure”中所描述。

1961年，IBM公司的女程序员Marlene Metzner Norton（玛琳·梅茨纳·诺顿）首次使用FORTRAN语言编程实现了希尔排序算法。在其程序中使用了一种简易有效的方法设置希尔排序所需的增量序列：第一个增量取待排序记录个数的一半，然后逐次减半，最后一个增量为1。

该算法后来被称为Shell-Metzner算法，Metzner本人在2003年的一封电子邮件中说道：“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”