1 using System;
 2  using System.Collections.Generic;
 3 
 4  namespace Com.Colobu.Algorithm.Insertion
 5 {
 6     /// <summary>
 7     /// <b>Shell sort</b> is a sorting algorithm that is a generalization of insertion sort, 
 8     /// with two observations:
 9     /// insertion sort is efficient if the input is "almost sorted"
10     /// insertion sort is typically inefficient because it moves values just one position at a time.
11     /// 
12     /// 对有n个元素的可比较资料，先取一个小于n的整数d1作为第一个增量，
13     /// 把文件的全部记录分成d1个组。
14     /// 所有距离为d1的倍数的记录放在同一个组中。
15     /// 先在各组内进行直接插入排序；然后，取第二个增量d2<d1
16     /// 重复上述的分组和排序，直至所取的增量dt=1(dt<dt-1<…<d2<d1)，
17     /// 即所有记录放在同一组中进行直接插入排序为止。
18     /// 该方法实质上是一种分组插入方法。
19     ///
20     /// 平均时间复杂度:O(nlogn)
21     /// Stability:No
22     /// </summary>
23     public class ShellSortAlgorithm
24     {
25         public static void ShellSort<T>(IList<T> szArray) where T : IComparable
26         {
27             int i, j, k, gap;
28             T temp;
29 
30             //gap sequence:a(n) = floor(fibonacci(n+1)^(1+sqrt(5)))
31             //the Fibonacci numbers (leaving out one of the starting 1's) to the power of twice the golden ratio
32             int[] gaps = { 1,5,13,43,113,297,815,1989,4711,11969,27901,84801,
33                    213331,543749,1355339,3501671,8810089,21521774,
34                    58548857,157840433,410151271,1131376761,2147483647 };
35 
36             int n = szArray.Count;
37             
38             //从素数序列中得到一个满足条件的最大的素数
39             for (k = 0; gaps[k] < n; k++) ;
40 
41             while (--k >= 0)
42             {
43                 gap = gaps[k]; //取增量
44 
45                 for (i = gap; i < n; i++) //按照此增量分组
46                 {
47                     temp = szArray[i];
48                     j = i;
49                     while (j >= gap && szArray[j - gap].CompareTo(temp) > 0) //将此组插入排序
50                     {
51                         szArray[j] = szArray[j - gap];
52                         j = j - gap;
53                     }
54                     szArray[j] = temp;
55                 }
56             }
57 
58         }
59     }
60 }
61