Java——希尔排序

希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。

希尔排序是基于插入排序的。将插入排序算法 内for循环中的所有 1 改为增量就可以。。。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量  =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

假设有一组数：5  6  1  3  7  8  4  2  0  9

假设取增量为3，即把这组数下标为3*0、3*1，3*2，3*3的数进行插入排序、再把这组数下标+1再进行插入排序，直到所有数都进行排序。

即把下标为0、3、6、9的数进行插入排序：5  3  4  9插入排序结果为 3 4 5 9

把下标为1、4、7的数进行插入排序；6  7  2 插入排序结果为  2  6  7

把下标2、5、8的数进行插入排序 1  8  0 插入排序结果为 0  1  8

最终得到的结果为：3  2  0  4  6  1  5  7  8  9  

这时把增量-1即增量为2，进行和上面一样的操作

现在的这组数为：3  2  0  4  6  1  5  7  8  9  

把下标为0、2、4、6、8的数进行插入排序： 3  0  6  5  8 插入排序结果为：0  3  5  6  8

把下标为1、3、5、7、9的数进行插入排序：2  4  1  7  9 插入排序结果为：1  2  4  7  9

最终得到的结果为：0  1  3  2  5  4  6  7  8  9

这时的序列已经接近升序了

再将增量-1即增量为1，进行插入排序 ，

得到结果 0  1  2  3  4  5  6  7  8  9

关于希尔排序增量的选择有很多说法，理论上最后是1就可以，但是在时间上有所不同，关于希尔增量的选择大家可以去查阅一些资料，也可以看一下这个ReviewForJob——希尔排序（缩小增量排序）之塞奇威克增量序列

/** * 希尔排序 */ class Shell_Sort{ public static void shellSort(int[] a){ int increment = a.length; while(increment > 1){ increment = increment / 3 + 1; for(int i = increment;i < a.length;i++){ int get = a[i]; int end = i - increment; while(end>=0 && get < a[end]){ a[end + increment] = a[end]; end -= increment; } a[end + increment] = get; } } System.out.println("希尔排序:"); for (int var : a) { System.out.print(var+","); } } } class Test{ public static void main(String[] args) { int[] data = new int[]{5,6,1,3,7,8,4,2,0,9}; for (int var : data) { System.out.print(var+","); } System.out.println(); Shell_Sort.shellSort(data); } }