概述
希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。
代码实现
/**
* 基本思想：
* 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
* 所有距离为d1的倍数的记录放在同一个组中。
* 先在各组内进行直接插入排序；然后，取第二个增量d2<d1
* 重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，
* 即所有记录放在同一组中进行直接插入排序为止。
*
*
*
*
* @author yeoggc
*
*/
public class 希尔排序 {
private void shellSort(int[] array) {
int gap = array.length / 2;// 初始化gap为数组长度/2
while (1 <= gap) {// 中止条件是gap<1
// 对步长为gap的元素进行分组
// 交替的对每组进行直接插入排序
for (int i = gap; i < array.length; i++) {
int temp = array[i];// 待排序的数据
int j = 0;// 有序区中待比较元素的下标，初始时，从有序区中最后一个元素开始比较起
// 对步长为 gap 的元素组进行排序
for (j = i - gap; j >= 0 && temp < array[j]; j = j - gap) {
array[j + gap] = array[j];
}
array[j + gap] = temp;
}
System.out.format("gap = %d:\t", gap);
printAll(array);
gap = gap / 2; // 减小增量
}
}
public static void main(String[] args) {
int[] array = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
// 调用希尔排序方法
希尔排序 shell = new 希尔排序();
System.out.print("排序前:\t\t");
shell.printAll(array);
shell.shellSort(array);
System.out.print("排序后:\t\t");
shell.printAll(array);
}
// 打印完整序列
public void printAll(int[] list) {
for (int value : list) {
System.out.print(value + "\t");
}
System.out.println();
}
}
算法分析
这例子希尔排序的步长选择都是从n/2开始，每次再减半，直到最后为1。这并不是最高效的步长选择。
希尔排序是不稳定的：我们知道一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，即希尔排序中相等数据可能会交换位置。
希尔排序的平均时间复杂度为O(nlog2n)。
直接插入排序和希尔排序的比较
直接插入排序是稳定的；而希尔排序是不稳定的。
直接插入排序更适合于原始记录基本有序的集合。
希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。
直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。
