简析
概念
希尔排序（Shell Sort） 希尔排序的实质就是分组插入排序，该方法又称缩小增量排序。
原理
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序
依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
范例（java）
初始时，有一个大小为 10 的无序序列{9,1,2,5,7,4,8,6,5,3}。
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组
{9,4}，{1,8}，{2,6}，{5,5}，{7,3}
接下来，按照直接插入排序的方法对每个组进行排序
{4,9}，{1,8}，{2,6}，{5,5}，{3,7}
排序后位置交换原数组 {4,1,2,5,3,9,8,6,5,7}
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
{4,2,3,8,5},{1,5,9,6,7}
按照直接插入排序的方法对每个组进行排序。
{2,3,4,5,8},{1,5,6,7,9}
排序后位置交换原数组 {2,1,3,5,4,6,5,7,8,9}
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
{2,1,3,5,4,6,5,7,8,9}
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
{1,2,3,4,5,5,6,7,8,9}
需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法
概念代码
public static void main(String[] args) {
int[] arr = {9, 1, 2, 5, 7, 4, 8, 6, 5, 3};
int i, j, gap;
int m = 1;//输出gap步数
int count = arr.length;
for (gap = count / 2; gap > 0; gap /= 2) { //步长
for (i = 0; i < gap; i++) {//直接插入排序
for (j = i + gap; j < count; j += gap)
if (arr[j] < arr[j - gap]) {
int temp = arr[j];
int k = j - gap;
while (k >= 0 && arr[k] > temp) {
arr[k + gap] = arr[k];
k -= gap;
}
arr[k + gap] = temp;
}
}
System.out.print("第" + m + "次排序结果：");
for (int anArr : arr) {
System.out.print(anArr + "\t");
}
System.out.println("");
m++;
}
System.out.print("最终排序结果：");
for (int anArr : arr) {
System.out.print(anArr + "\t");
}
}
1 | 第1次排序结果：4 1 2 5 3 9 8 6 5 7 |