算法系列： 10大常见排序算法（4）希尔排序

一句

 希尔排序(Shell Sort)是最早突破复杂度O(n^2)的排序算法

算法引入

希尔排序（Shell Sort）是Shell提出来的，对插入排序法的改进，也是最早突破复杂度O(n2)的排序算法。

插入排序法有2个特点：

1.  插入排序在对几乎已经排序的数据操作时，效率高，可以达到线性时间

2.  插入排序一般来说是低效的，其每次只能将数据移动一位：

   假设一个极端的例子，如果最小的数据在一个已按升序排好序的数组的末端。冒泡排序或插入排序可能会进行 n 次的比较和交换才能将该数据移至正确位置。

希尔排序提供了一个办法，可以直接比较交换间隔较远的数据

h-sort

希尔排序的关键思想是先用间隔较远的数据相互排序，这样有机会把位置很偏的数据迅速安放到正确的位置。首先我们介绍一个新概念：h-sort

一句

 如果一个序列中任何一个间隔为h的子序列都是排好序的，那么这个序列叫做h-sorted

答案：

原序列有5个间隔为5的子序列：

（a1,a6,a11）->【62，17，25】，

（a2,a7,a12）->【83，95，28】，

（a3,a8）->【18，86】，

（a4,a9）->【53，47】，

（a5,a10）->【07，69】

如果上述5个子序列都排好序，那么原来都序列就变成了5-sorted.

（a1,a6,a11）->【62，17，25】->  （a1,a6,a11）->【17，25，62】

（a2,a7,a12）->【83，95，28】->   (a2,a7,a12）->【28，83，95】

（a3,a8）->【18，86】->                （a3,a8）->【18，86】

（a4,a9）->【53，47】->                （a4,a9）->【47，53】

（a5,a10）->【07，69】->                 (a5,a10）->【07，69】

想一想：

如果一个序列是h-sorted,  那么这个序列是已经排好序的了.这句话对不对？

再想一想：

希尔排序

 我们定义一个从大到小的数列叫做步长序列， 只要最终步长为 1 任何步长串行都可以使用。希尔排序就是用步长序列定义的步长对数组用插入排序法反复排序对过程。

问题1： 为什么只要最终步长为 1 任何步长串行都可以完成排序？

问题2:   既然如此，为什么开始不直接使用插入排序？ 而要计算n-sorts?

 

算法实现

为什么循环从i=gap开始？， 因为我们对所以子序列用插入排序法进行排序；而在插入排序法中，第一个元素可以看做已经排好序的，这里有gap个子序列，所以前面一共有gap个排好序的元素。

学而时嘻之,不亦乐乎～， 来做个填充练习：

算法复杂度

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。