图解希尔排序，超详细非常好理解 _希尔排序

文章插图

1. 基本概念【图解希尔排序，超详细非常好理解】希尔排序又叫递减增量排序算法，它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的；希尔排序是一种不稳定的排序算法。
希尔排序由唐纳德·希尔（Donald Shell）发明并于1959年公布，因此得名希尔排序。
我们之前讲过直接插入排序，它的算法复杂度为O(n^2)，整体来说它的效率很低；在后面第3小节中我们将简短地回忆一下它的工作方式。但是在两种情况下它表现得很好，我们这里将这两种情况归纳为直接插入排序的两种性质：
1. 当待排序的原序列中大多数元素都已有序的情况下，此时进行的元素比较和移动的次数较少；
2. 当原序列的长度很小时，即便它的所有元素都是无序的，此时进行的元素比较和移动的次数还是很少。
希尔排序正是利用了直接插入排序算法的这两个性质，它首先将待排序的原序列划分成很多小的序列，称为子序列。然后对这些子序列进行直接插入排序，因为每个子序列中的元素较少，所以在它们上面应用直接插入排序效率较高（利用了上面的性质2）。这样的过程可能会进行很多次，每一次都称为一趟，每一趟都将前一趟得到的整个序列划分为不同的子序列，并再次对这些子序列进行直接插入排序。最后由这些子序列组成的整个序列中的所有元素就基本有序了，此时再在整个序列上进行最后一次的直接插入排序（利用了上面的性质1），此后整个序列的排序就完成了。
2. 子序列的划分方式希尔排序最关键的地方就是如何对整个序列进行划分，理解了这一过程就理解了整个希尔排序。我们最直接的想法可能就是按顺序对整个序列进行平均划分，比如有n个元素的序列，我们要把它划分成i个子序列，每个子序列有m个元素（假设n = i * m，当n不能被i整除时可以让最后一个子序列的元素少于其它子序列）。该想法就是让原序列的第0 ~ m-1个元素为第一个子序列（第一个元素的下标为0），第m ~ 2m-1个元素为第二个子序列，以此类推，最后的第n-m ~ n-1个元素为最后一个子序列。
这样的划分虽然简单但是它却不适合希尔排序，这样划分并对子序列进行直接插入排序后，虽然每个子序列中的元素都是有序的，但整个原序列依旧是很无序的。为了便于理解为什么这种方式不行，我们用图1来对它进行说明。

文章插图
图1 按顺序划分的子序列
在图1中，原序列有9个元素，我们将它按顺序划分为3个子序列。即最前面的3个元素为第一个子序列，中间3个元素为第二个子序列，最后3个元素为最后一个子序列；图中我们用不同的颜色表示不同的子序列。
可以看到，对每个子序列应用直接插入排序后，虽然每个子序列都是有序的，但整个序列还是很无序的。此时，在整个序列上进行直接插入排序的效率还是很低。整个序列依旧无序的原因是每个元素只在它所在的子序列中移动，它的新位置离它的最终位置（即整个序列排好序后的位置）还是很远。
因此，子序列划分的方法必须保证对子序列进行排序后，每个元素在整个序列中的移动范围更大。这样跳跃式的位置移动，才可能让每个元素离它的最终位置较近，因而整个序列才是比较有序的。
希尔排序采用的是按增量的方式进行子序列划分，将整个序列中下标值相差固定值（增量）的所有元素划分到同一个子序列中。比如，整个序列有9个元素，而增量为3，那么第0、3、6个元素属于第一个子序列，第1、4、7个元素属于第二个子序列，第2、5、8个元素属于最后一个子序列。
为了便于理解，我们同样用图2来展示这种增量划分方式。我们同样用不同的颜色表示属于不同子序列的元素，并标出了每个子序列的元素的下标值。可以看到，以增量方式划分的子序列在整个序列中是交错出现的。

文章插图
图2 按增量划分的子序列
按照增量划分的时候，假设增量为increment，那么整个序列也将划分为increment个子序列。可以这样理解，我们遍历整个序列中的每个元素，并为每个元素指定它所属的子序列。首先是下标为0的元素，它属于第一个子序列；然后是下标为1的元素，它属于第二个子序列；以此类推，可知前increment个元素（下标为0 ~ increment-1）属于不同的子序列，共计increment个。从下标为increment的元素开始，每一个元素的下标值减去increment都大于或等于0，即这些元素都属于一个已存在的子序列。因此，整个序列将被划分为increment个子序列。