希尔排序算法- 校招VIP

转载声明：文章来源 https://blog.csdn.net/qq_28063811/article/details/93172703

1、希尔排序简介

希尔排序，是插入排序的一种进阶排序算法，通过一个不断缩小的增量序列，对无序序列反复的进行拆分并且对拆分后的序列使用插入排序的一种算法，所以也叫作“缩小增量排序”或者“递减增量排序”。
既然希尔排序也是使用插入排序进行序列排序操作的，为什么会有希尔排序呢？

这是基于插入排序的两点性质而来：
第一：对一个“几乎”已经排好序的无序序列，插入排序的效率是很高的，可以达到线性排序的效率。比如，当序列中只有一位元素没有在适当的位置，那么整个序列只需要移动该序列的位置即可达到完成排序的任务。
第二：但是一般的无序序列不是一个“几乎”已经排好序的序列，所以插入排序是低效的。因为它每次只能移动一位元素。
基于以上两点出现了希尔排序，那么希尔排序到底如何利用了这两个性质呢？

2、希尔排序的步骤

首先根据初始序列的长度，选定一个递减增量序列t1，t2，t3......tk，其中ti>tj，tk = 1。
根据选定的增量序列元素个数k，对初始序列进行k趟排序。
根据增量序列的值ti，每趟排序会把初始序列划分成若干个元素的子序列，然后对这些子序列使用插入排序，因为这是递减增量序列，所以第一趟的排序，增量值最大，那么划分的子序列数量也就最多，每个子序列的元素也就越少，可以看做是一个“几乎”已经排好序的序列，当增量值越来越小的时候，子序列数量也就越少，每个子序列的元素也就越多，但是，基于前几次的排序，这些子序列虽然元素多，但是已经是一个“几乎”排好序的序列了，当最后一次排序的时候，即增量序列的值为1时，就是对整个无序序列进行排序，这时整个序列已经是一个“几乎”排好序的序列了。

以图为例进行说明，假设给定的初始无序序列如下：

首先，我们选择一个增量序列，这个增量序列如何选择呢？
首先我们得保证第一次的所有子序列元素数量应该至少保证为2个或以上，这样是用插入排序才有意义，如果元素数量为1，也就是增量序列的第一个值为初始序列的长度或者更大，
那么这次遍历将“无功而返”，所以至少应该保证子序列元素数量为2或以上，当子序列数量退化到初始序列长度时，希尔排序也退化成了插入排序。
事实上，希尔排序的效率依赖于增量序列的选择，好的增量序列可以大大的提高希尔排序的效率，但是增量序列的选择是和初始序列有关系的。

一个好的递减增量序列选取的标准是：
1、递减增量序列最后一个值应该为1；
2、递减增量序列中的值，尤其是相邻的值最好不要互为倍数的关系，如果是互为倍数的关系，那么根据这两个序列值的分组将会有重复的情况，可能会做“无用功”。

该示例中，我们选取的递减增量序列位[3,2,1]。

递减增量序列已经有了，下面开始进行3趟（增量序列长度为3）排序，先取增量序列第一个值3，然后将初始序列分组，如下：

对三组子序列[4,2,,7]，[5,3,1]，[8,9]分别使用插入排序，结果如下：

然后，对该序列再次进行增量序列的分组，这次增量序列的值为2，分组情况如下：

对两组子序列分别使用插入排序，结果如下：

最后，对整个序列做插入排序（增量序列值为1）即可。

从整个过程可以看出，每次的排序，都会将较小的值转移到序列的前边，整个序列的有序性不断的变强，可以使插入排序达到更高的效率。

3、代码实现（java版本）

public class ShellSort {
 
	public static void shellSort(int[] arr) {
		if (arr == null || arr.length == 0) {
			return;
		}
		int len = arr.length;
		// 首先选取一个增量序列
		int gap = 1;
		while (gap < len) {
			// 先找出增量序列最大的增量值，也就是将序列分为gap组
			gap = gap * 3 + 1;
		}
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }
	}
}

4、复杂度分析
希尔排序的效率依赖于递减增量序列的选择，时间复杂度最坏的情况是O(nlog2n)。