希尔排序是插入排序的一种，时间性能优于直接插入排序，是一种不稳定的排序，时间复杂度为 O(nlogn)。
基本思想
将整个无序列分割成若干小的子序列分别进行直接插入排序。
先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组。所有距离为 dl 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量 d2 < d1 重复上述的分组和排序，直至所取的增量 dt = 1 (dt < dt-l < … <d2 < d1)，即所有记录放在同一组中进行直接插入排序为止。
最后一个增量必须为 1。
当第一个增量为 1 时，就等于直接插入排序。
如下：
增量：2，分为 2 组
30 20 40 15 35 25
30 -- 40 ---35 <- 第一组
20 -- 15 -- 25 <- 第二组
每组进行直接插入排序。
40 和 30 比较，顺序正确(第一组的有序段：30 40)
15 和 20 比较，顺序错误，20 后移，已经是最前面了，15 插入原 20 的位置(第二组的有序段：15 20)
35 和 40 比较，顺序错误，40 后移，40 前面还有数，所以还要继续比较
35 和 30 比较，顺序正确，35 找到了插入点(第一组的有序段：30 35 40)
25 和 20 比较，顺序正确(第二组的有序段：15 20 25)
到这里，第一趟结束。
第一组：30 35 40
第二组：15 20 25
30 15 35 20 40 25
例子
using System;
namespace System
{
public class Test
{
public static void Main()
{
int[] array = new int[6] { 30, 20, 40, 15, 35, 25 };
PrintArray(array);
Console.WriteLine("-----------------");
ShellSort.Sort(array);
PrintArray(array);
Console.ReadKey();
}
public static void PrintArray(int[] array)
{
for (int i = 0; i < array.Length; i++)
{
if (i > 0) Console.Write(" ");
Console.Write(array[i].ToString());
}
Console.WriteLine();
}
}
public class ShellSort
{
public static void Sort(int[] array)
{
int increment = array.Length;
do
{
increment = increment / 3 + 1; // 设置增量
Sort(array, increment);
} while (increment > 1);
}
public static void Sort(int[] array, int increment)
{
// 进行直接插入排序
for (int i = increment; i < array.Length; i++) // 从第二个开始
{
if (array[i] < array[i - increment]) // 前面有大的数，需要后移
{
int j = i - increment; // j 表示前面数的指针
int temp = array[i];
do
{
array[j + increment] = array[j]; // 后移元素
j = j - increment;
} while (j >= 0 && array[j] > temp); // 前面的数还是大的时，继续循环后移
array[j + increment] = temp; // array[i] 插入正确的位置上
}
}
}
}
}
希尔排序算法是对插入排序的一种改进，其核心是减少已排序区域的右移次数来提高速度。具体做法是先获得一个间隔数值 h，然后将 n-1 替换成 n-h 来完成插入排序。
具体例子：
元素集合 = [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