数据结构
最差时间复杂度	O（n log^2 n）
最优时间复杂度	O (n log^2 n)
平均时间复杂度	O（n log n）
空间复杂度	O(1)
排序方式	in-place
稳定性	不稳定
比较次数	n*(n-1)/2
适用场景

 

 

 

 

 

 

 

 

 

 

 

 

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。  希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

思路：

初始数据:74 88 69 67 75   72 11 89 77 60 gap=5（分5组,每组进行插入排序）74和72:　　72 88 69 67 75   74 11 89 77 6088和11:　　72 11 69 67 75   74 88 89 77 6069和89:　　72 11 69 67 75   74 88 89 77 6067和77:　　72 11 69 67 75   74 88 89 77 6075和60:　　72 11 69 67 60   74 88 89 77 75 gap=2（分2组,每组进行插入排序）（72、69、60、88、77）（11、67、74、89、75） 第一组结果：　　60 11 69 67 72   74 77 89 88 75第二组结果：　　60 11 69 67 72   74 77 75 88 89 gap=1（整个数组进行插入排序）结果：　　11 60 67 69 72   74 75 77 88 89________________________________________________数组个数为奇数74 88 69 67 75   72 11 89 77 60   10 初始数据

gap=5（分5组,每组进行插入排序）

第一组：　　72 88 69 67 75 74 11 89 77 60 10（74、72、10 插入排序） 其余同上。

　　

代码：

public class ShellSort : SortBase, ISort    {
            public void Sort()        {            int n = arr.Length;            int i, j, gap;            // gap为步长，每次减为原来的一半。            for (gap = n / 2; gap > 0; gap /= 2)            {                // 共gap个组，对每一组都执行直接插入排序                for (i = 0; i < gap; i++)                {                    for (j = i + gap; j < n; j += gap)                    {                        // 如果arr[j] < arr[j-gap]，则寻找arr[j]位置，并将后面数据的位置都后移。                        if (arr[j] < arr[j - gap])                        {                            int tmp = arr[j];                            int k = j - gap;                            while (k >= 0 && arr[k] > tmp)                            {                                arr[k + gap] = arr[k];                                k -= gap;                            }                            arr[k + gap] = tmp;                        }                    }                }            }            base.output(arr);        }        public void Sort2()        {        }    }