数据结构与算法-算法篇：排序—希尔排序（四）

数据结构与算法系列文章：数据结构与算法目录

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

每一遍根据区间，分为若干组，对这些组进行进行插入排序，排序后，整体不是有序的，但是这些分组间是有序的，然后继续分组排序
如：若总共10个数， 则初始区间为13；
第一遍时：区间为13，超出长度，直接跳到下一遍
第二遍时：区间为4，对若干的分组，进行插入排序：分组为（索引）4,0 5,1 6,2 7,3 8,4 9,5
第三遍时：区间为1，对若干的分组，进行插入排序：分组为（索引）1,0 2,1 3,2 4,3 5,4 6,5 7,6 8,7 9,8
第四遍时：区间为0，说明排序完毕。

其实当区间为 1 的时候，它使用的排序方式就是插入排序

实现：

/// <summary>
/// 希尔排序
/// </summary>
/// <param name="arr"></param>
public void ShellSort(int[] arr)
{
    int length = arr.Length;
    //区间
    int gap = 1;
    while (gap < length)
    {
        gap = gap * 3 + 1;
    }

    // 若干区间
    while (gap > 0)
    {
        // 对此区间，进行若干分组，插入排序
        for (int i = gap; i < length; i++)
        {
            int temp = arr[i];
            int j = i - gap;
            // 对当前组排序
            while (j >= 0 && arr[j] > temp)
            {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = temp;
        }

        // 当前区间完毕，进行下一区间
        gap = gap / 3;
    }
}

区间为什么要以 gap = gap*3 + 1 去计算，其实最优的区间计算方法是没有答案的，这是一个长期未解决的问题，不过差不多都会取在二分之一到三分之一附近。