排序(3) 希尔排序

希尔排序又叫缩小增量排序，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。 希尔排序是对插入排序的优化，基于以下两个认识：1.数据量较小时插入排序速度较快，因为n和n²差距很小；2.数据基本有序时插入排序效率很高，因为比较和移动的数据量少。 希尔排序的时间复杂度和增量的选择策略有关，博客中的选择策略会导致排序的不稳定性。

希尔排序

原理

因此，希尔排序的基本思想是，将需要排序的序列划分成为若干个较小的子序列，对子序列进行插入排序，通过插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。

希尔排序的划分子序列不是像归并排序那种的二分，而是采用的叫做增量的技术，例如有十个元素的数组进行希尔排序，首先选择增量为10/2=5，此时第1个元素和第（1+5）个元素配对成子序列使用插入排序进行排序，第2和（2+5）个元素组成子序列，完成后增量继续减半为2，此时第1个元素、第（1+2）、第（1+4）、第（1+6）、第（1+8）个元素组成子序列进行插入排序。这种增量选择方法的好处是可以使数组整体均匀有序，尽可能的减少比较和移动的次数。
二分法中即使前一半数据有序，后一半中如果有比较小的数据，还是会造成大量的比较和移动，因此这种增量的方法和插入排序的配合更佳。

在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2, (n/2)/2, …, 1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。

希尔排序的时间复杂度和增量的选择策略有关，上述增量方法造成希尔排序的不稳定性。

因为直接插入排序在元素基本有序的情况下，效率是很高的，因此希尔排序在时间效率上有很大提高。

算法描述

无序序列：int a[] = {3, 1, 5, 7, 2, 4, 9, 6};

第一趟时：
n=8; gap = n/2 = 4； 把整个序列共分成了4个子序列{3, 2}、{1, 4}、{5, 9}、{7, 6}
第一趟结束时，数列为：{2, 1, 5, 6, 3, 4, 9, 7};

第二趟时：
gap = gap/2 = 2； 把整个序列共分成了2个子序列{2, 5, 3, 9}、{1, 6, 4, 7}
第一趟结束时，数列为：{2, 1, 3, 4, 5, 6, 9, 7};

第三趟时：
gap = gap/2 = 1； 对整个序列进行 插入排序

##代码实现

Shell排序

public class ShellSort {
	public static int[] shellSort(int[] arr) {
		for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
			// 对子序列插入排序
			for (int i = gap; i < arr.length; i++) {
				int j = i;
				int currentElement = arr[i];
				while (j - gap >= 0 && arr[j - gap] > currentElement) {
					arr[j] = arr[j - gap];
					j -= gap;
				}
				arr[j] = currentElement;
			}
		}
		return arr;
	}

	public static void main(String[] args) {
		int[] testList = new int[] { -6, -3, -2, 7, -15, 1, 2, 2 };
		int[] test = shellSort(testList);
		System.out.println(Arrays.toString(test));
	}
}

复杂度及稳定性

复杂度

时间复杂度（平均）： O(n^1.3)
时间复杂度（最坏）： O(n^2)
时间复杂度（最好）： O(n)

空间复杂度： O(1)

稳定性

Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。

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

例如，有100个整数需要排序：
第一趟排序，先把它分成50组，每组2个整数，分别排序。
第二趟排序，再把经过第一趟排序后的100个整数分成25组，每组4个整数，分别排序。
第三趟排序，再把前一次排序后的数分成12组，第组8个整数，分别排序。

照这样子分下去，最后一趟分成100组，每组一个整数，这就相当于一次插入排序。
由于开始时每组只有很少整数，所以排序很快。之后每组含有的整数越来越多，但是由于这些数也越来越有序，所以排序速度也很快。

希尔排序平均效率是O(nlogn)，其中分组的合理性会对算法产生重要的影响。

Shell排序比冒泡排序快5倍，比插入排序大致快2倍。
Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

由于开始时每组只有很少整数，所以排序很快。之后每组含有的整数越来越多，但是由于这些数也越来越有序，所以排序速度也很快。
然而，情况并不总是这么理想的，在一些特定（但并不算罕见）的情况下，虽然经过了很多趟排序但是数据却没有变得更有序。例如，如果用上面的算法对下面这些数进行排序：
1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16

在gap = 1之前的每一趟排序都在浪费时间！

这种坏情形是可以避免的，就是把上面的增量数列（1, 2, 4, 8）改成Hibbard增量（1, 3, 5, 7）由此可见，增量数列的选择对希尔排序的性能有着极大的影响。

Mark Allen Weiss指出，最好的增量序列是Sedgewick提出的 (1, 5, 19, 41, 109, …)，该序列的项来自 9 4^i - 9 2^i + 1 和 4^i - 3 * 2^i + 1 这两个算式。

---