1.概述

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

原理：先将序列分割成若干个子序列（由相隔某个“增量”的 元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。插入排序在元素基本有序的情况下，效率会更高，因此先分组，再插入排序，再组装，已达到序列基本有序，所以希尔排序在时间效率上比插入排序有较大提高，时间复杂度为O(n^3/2)。

2.示例

//希尔排序        public static void ShellSort(int[] nums)        {            //取步长            int step = nums.Length / 2;            while (step >= 1)            {                for (int i = step; i < nums.Length; i++)                {                    var temp = nums[i];                    int j;                    for (j = i - step; j >= 0 && temp < nums[j]; j = j - step)                    {                        nums[j + step] = nums[j];                    }                    nums[j + step] = temp;                }                step = step / 2;            }        }        //    int[] list = new[] { 4, 1, 2, 7, 9, 0, 8 };        //    Sorter.ShellSort(list);