排序-希尔排序

概念

希尔排序是插入类排序算法，它的本质就是分组插入排序，它采取分割策略：将相距某个“增量”的记录组成一个子序列，保证在每个子序列内部分别进行插入排序后得到的结果是基本有序。

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

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

Java实现

// 定义接口
interface Sorter {
	/**
	 * 将数组按升序排序
	 */
	int[] sort(int[] arr);

	/**
	 * 交换数组arr中的第i个位置和第j个位置的关键字
	 */
	default void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}
//希尔排序
public class ShellSorter implements Sorter {

	@Override
	public int[] sort(int[] arr) {
		shellSort(arr);
		return arr;
	}

	// Shell排序的关键就是增量序列的选取：
	// 增量序列原则： 增量序列的最后一个增量必须等于1
	private void shellSort(int[] arr) {
		int len = arr.length;
		int increment = len;
		for (; increment != 1;) {// 循环直至increment=1
			increment = increment / 3 + 1; // 计算增量序列(将整个序列分成increment组,在组内进行插入排序)
			for (int i = increment; i < len; i++) {
				if (arr[i] < arr[i - increment]) {
					int tmp = arr[i]; // 暂存arr[i]的值
					int j;
					for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) {
						// 组内记录后移,查找插入位置
						arr[j + increment] = arr[j];
					}
					// 找到插入位置
					arr[j + increment] = tmp;
				}
			}
		}
	}
}

演示

比如我们待排序的数组是 {9, 1, 5, 8, 3, 7, 4, 6, 2}
初始时increment=arr.length=9，increment != 1，执行第1次循环：
increment = 9/3+1 = 4，将整个序列分成4组，组内进行插入排序：

第 1 组： 9 3 2    -----------> 2 3 9
第 2 组： 1 7      -----------> 1 7
第 3 组： 5 4      -----------> 4 5
第 4 组： 8 6      -----------> 6 8

此时序列为 2 1 4 6 3 7 5 8 9

increment=4，increment != 1，执行第2次循环：
increment = 4/3+1 = 2，将整个序列分成2组，组内进行插入排序：

第 1 组： 2 4 3 5 9    ----------->  2 3 4 5 9
第 2 组： 1 6 7 8      ----------->  1 6 7 8

此时序列为 2 1 3 6 4 7 5 8 9

increment=2，increment != 1，执行第3次循环：
increment = 2/3+1 = 1，将整个序列分成1组，组内进行插入排序（演变为直接插入排序）：

第 1 组 ： 2 1 3 6 4 7 5 8 9  -----------> 1 2 3 4 5 6 7 8 9

increment=1，结束循环，排序完毕。