排序算法：希尔排序（更高效的插入法排序）_高效的插入排序

希尔排序：
      希尔排序，英文名Shell Sort,又被称为缩小增量排序。无论是中文名，英文名，还是别名，都透露着一股学渣不可侵犯的“神圣”感。当初学习插入法的时候，一看到这么接地气的名字，学起来也有信心。但是看到希尔排序这高端大气上档次的名字，一下子就起了退避三舍的心思。那么，希尔排序真的就这么的拒人于千里之外吗？其实学会了希尔排序的思路后，就不觉得它有多难了。

      希尔排序其实也是插入排序的一种，不过希尔排序是将序列按下标的一定增量分组，分别对每组序列使用直接插入排序算法排序，随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个序列恰被分成一组，再进行一次整个序列的直接插入排序，整个算法就此终止。
      既然最终都是要使用直接插入排序对整个序列进行排序，那么为什么要用一个增量来把序列分组呢？这是因为直接插入排序在元素基本有序的情况下，效率是很高的，当通过分组完成插入排序，首先每一组的数据基数小了，因此使用直接插入的代价变小，同时，每完成一组序列的排序，整个序列就更趋于有序化，对于下一轮的插入排序来说，更加有序的序列代表着效率的进一步提高，因此相比排序算法：插入排序中介绍的直接插入排序算法，以及排序算法：二分法插入排序中介绍的二分法插入排序算法，希尔排序在时间效率上要快得多。

下面以长度为10的序列:{4，6，3，1，7，5，2，9，8，6}的希尔排序过程做示范：
首先求增量：10/2=5；
增量的目的是将序列按增量分组，增量为5意味着序列中的元素每隔5个是一组
这就将序列分成了5组，分别是：（相同颜色为一组）

4     6     3     1     7     5     2     9     8     6

即为{4，5}、{6，2}、{3，9}、{1，8}、{7，6}
（注：这里的分组并不是将序列的元素拷贝出来放入新的序列，而只是在原序列上用增量去逻辑上的划分，其实从物理上来看，元素仍然存储于原序列里）

对这5个分组分别使用直接插入排序，结果如下：

4     2     3     1     6     5     6     9     8     7
（ps:可以看到两个6之间的相互位置交换了，这证明希尔排序是不稳定的）

然后，缩小增量：5/2=2
对序列按增量2进行分组：

4     2     3     1     6     5     6     9     8     7

分别是{4，3，6，6，8}、{2，1，5，9，7}
对这两个组分别使用直接插入排序，结果如下：

3     1     4     2     6     5     6     7     8     9

接下来再缩小增量：2/2=1
发现增量已经减小到1了，这代表将整个序列分为一组，也就相当于不分组。
对序列：
3     1     4     2     6     5     6     7     8     9
进行直接插入排序：
第一趟：[1]     3     4     2     6     5     6     7     8     9
第二趟：[1     3]     4     2     6     5     6     7     8     9
第三趟：[1     3     4]     2     6     5     6     7     8     9
第四趟：[1     2     3     4]     6     5     6     7     8     9
第五趟：[1     2     3     4     6]     5     6     7     8     9
第六趟：[1     2     3     4     5     6]     6     7     8     9

此时整个序列已经有序，以上就是一次完整的希尔排序过程。

本文根据上述的希尔排序思路思路给出C++与Java的代码实现，并且使用Java对希尔排序算法和，二分法插入排序算法、插入排序算法、选择排序算法，以及两种冒泡排序算法进行性能比较。

C++代码：

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void shellSort(int *arr, int length)
{
    if (arr == NULL || length <= 0)return;
    int d = length / 2;
    for (; d > 0; d = d / 2)
    {
        for (int i = d; i < length; ++i)
        {
            for (int j = i - d; j >= 0;j-=d)
            if (arr[j]>arr[j + d])
            {
                swap(&arr[j], &arr[j + d]);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Java代码：

private void shellSort(List<Integer> list) {
    int length = list.size();
    for (int gap = length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < length; ++i) {
            int temp = list.get(i);
            int j = i - gap;
            while (j >= 0 && list.get(j) > temp) {
                list.set(j + gap, list.get(j));
                j -= gap;
            }
            list.set(j + gap, temp);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

使用完全相同的，元素为整数的List对上述几种算法进行性能测试结果如下：
序列长度为1000：

序列长度为5000：

序列长度为10000：

序列长度为50000：

可以看出希尔排序的效率远远高于其他几种排序算法。