具体例子：
元素集合 = [2, 9, 5, 1, 8, 3, 6, 4, 7, 0]
间隔数值 h = 4
第一次循环: 当前元素 Array[4] = 8，那么 (n - h) = (4 - 4) = Array[0] = 2，由于 8 > 2，因此不发生交换。
第二次循环: 当前元素 Array[5] = 3，那么 (n - h) = (5 - 4) = Array[1] = 9，由于 3 < 9，交换结果 2, [3], 5, 1, 8, [9], 6, 4, 7, 0。
继续循环，直到 n == Array.Length - 1。
接下来减小 h 值开始下一轮间隔循环，直到获得最终排序结果。
对于间隔数值的获取，通常用以下公式。
我们先给出具体的代码，然后和插入排序做个对比。
{
var h = 1;
while (h <= array.Length / 3)
{
h = h * 3 + 1;
}
while (h > 0)
{
for (int outer = h; outer <= array.Length - 1; outer++)
{
var inner = outer;
var temp = array[outer];
while ((inner > h - 1) && array[inner - h] >= temp)
{
array[inner] = array[inner - h];
inner -= h;
}
array[inner] = temp;
var s = String.Join(",", Array.ConvertAll(array, i => i.ToString()));
Console.WriteLine("h:{0}, outer:{1}, temp:{2}, {3}", h, outer, temp, s);
}
h = (h - 1) / 3;
}
}
static void Main(string[] args)
{
var array = new int[] { 2, 9, 5, 1, 8, 3, 6, 4, 7, 0 };
ShellSort(array);
}
结果：
h:4, outer:5, temp:3, 2,3,5,1,8,9,6,4,7,0
h:4, outer:6, temp:6, 2,3,5,1,8,9,6,4,7,0
h:4, outer:7, temp:4, 2,3,5,1,8,9,6,4,7,0
h:4, outer:8, temp:7, 2,3,5,1,7,9,6,4,8,0
h:4, outer:9, temp:0, 2,0,5,1,7,3,6,4,8,9
h:1, outer:1, temp:0, 0,2,5,1,7,3,6,4,8,9
h:1, outer:2, temp:5, 0,2,5,1,7,3,6,4,8,9
h:1, outer:3, temp:1, 0,1,2,5,7,3,6,4,8,9
h:1, outer:4, temp:7, 0,1,2,5,7,3,6,4,8,9
h:1, outer:5, temp:3, 0,1,2,3,5,7,6,4,8,9
h:1, outer:6, temp:6, 0,1,2,3,5,6,7,4,8,9
h:1, outer:7, temp:4, 0,1,2,3,4,5,6,7,8,9
h:1, outer:8, temp:8, 0,1,2,3,4,5,6,7,8,9
h:1, outer:9, temp:9, 0,1,2,3,4,5,6,7,8,9
我们测试一下和插入排序的性能 比较。
{
static int InsertionSort(int[] array)
{
var count = 0;
for (int outer = 1; outer <= array.Length - 1; outer++)
{
var inner = outer;
var temp = array[outer];
while (inner > 0 && array[inner - 1] >= temp)
{
array[inner] = array[inner - 1];
inner--;
++count;
}
array[inner] = temp;
}
return count;
}
static int ShellSort(int[] array)
{
var count = 0;
var h = 1;
while (h <= array.Length / 3)
{
h = h * 3 + 1;
}
while (h > 0)
{
for (int outer = h; outer <= array.Length - 1; outer++)
{
var inner = outer;
var temp = array[outer];
while ((inner > h - 1) && array[inner - h] >= temp)
{
array[inner] = array[inner - h];
inner -= h;
++count;
}
array[inner] = temp;
}
h = (h - 1) / 3;
}
return count;
}
static void Main(string[] args)
{
for (int x = 1; x <= 5; x++)
{
var length = 10000 * x;
Console.WriteLine("-{0}-------------", length);
int[] array = new int[length];
var ran = new Random();
for (int i = 0; i < array.Length; i++)
{
array[i] = ran.Next();
}
Action<int[], Func<int[], int>> sort = (arr, func) =>
{
var count = 0;
var watch = Stopwatch.StartNew();
if (func != null)
count = func(arr);
else
Array.Sort(arr);
watch.Stop();
Console.WriteLine("{0,15}: {1,-4}, {2}",
func != null ? func.Method.Name : "Array.Sort",
watch.ElapsedMilliseconds,
count);
};
var a1 = array.Clone() as int[];
var a2 = array.Clone() as int[];
var a3 = array.Clone() as int[];
sort(a1, InsertionSort);
sort(a2, ShellSort);
sort(a3, null);
}
}
}
测试结果：
InsertionSort: 187 , 24806724
ShellSort: 3 , 165022
Array.Sort: 1 , 0
-20000-------------
InsertionSort: 608 , 99354518
ShellSort: 7 , 373684
Array.Sort: 2 , 0
-30000-------------
InsertionSort: 1377, 226557244
ShellSort: 12 , 653250
Array.Sort: 4 , 0
-40000-------------
InsertionSort: 2441, 401343428
ShellSort: 16 , 927861
Array.Sort: 5 , 0
-50000-------------
InsertionSort: 3823, 628045456
ShellSort: 21 , 1169268
Array.Sort: 7 , 0
我们可以看到，无论是时间还是右移次数上，希尔排序都比插入排序少很多，整体性能有极大提高，甚至接近 Array.Sort() 。