对于大规模乱序的数组,插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组地一段移动到另一端。希尔排序改进了插入排序,交换不相邻地元素以对数组地局部进行排序,最终用插入排序将局部有序的数组排序。
希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组成为 h 有序数组。换句话说,一个 h 有序数组就是 h 个相互独立的有序数组组合在一起的一个数组。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLxAjN2gTM1YzMtYDNzAjM0MTOwkTM3ADMyAjMtIzMyQDO58CX3ADMyAjMvwlMzIDN4kzLcd2bsJ2Lc12bj5ycn9Gbi52YuAjMwIzZtl2Lc9CX6MHc0RHaiojIsJye.png)
public class Shell: BaseSort
{
public static long usedTimes = 0;
public Shell()
{
}
public static void Sort(IComparable[] a)
{
Stopwatch timer = new Stopwatch();
timer.Start();
int n = a.Length;
int h = 1;
while (h < n / 3)
h = h * 3 + 1;
/*
* 每次循环生成 h有序数组(h 个有序数组) 即 (h 0), (h+1 1), (h+2 2), ....
* 如果右边的值小于左边的值时,交换;
* 并退回到左边的位置,重新排序,循环比较(j>=h)。
* 因为交换可能引起原有序的数组乱序,所以需要退回去重新比较
* 当 h 递减到 1时,相当于插入排序一个部分有序数组
* */
while (h >= 1)
{
//Console.WriteLine(h);
for (int i = h; i < n; i++)
{
//Console.WriteLine(i+","+(i - h));
for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
{
Exch(a,j,j-h);
//Console.WriteLine("J:" + (j- h));
}
}
h = h / 3;
}
timer.Stop();
usedTimes = timer.ElapsedMilliseconds;
}
}
从另一个角度看希尔排序,插入排序是将每个比元素大的元素向右移动一个,希尔排序是交换到比它大的元素之前,移动距离从 1 改成 h 。
希尔排序更高效的原因是它将数组变成多个部分有序的数组,减少倒置。排序之初,各个子数组都很短,排序之后子数组都是部分有序的,这很适合插入排序。子数组部分有序的程度取决于递增序列的选择。(如何选择??)
和选择排序以及插入排序对比,希尔排序也可以用于大型数组,即使是随机数字排序也快很多。数组规模越大,对比越明显。
希尔排序的性能分析比较困难。它的运行时间达不到平方级别,在最坏情况下的比较次数和 N ^ 3/2 成正比。
如果中等大小的数组可以使用希尔排序,它代码量少,且不需要额外的内存空间。
百万级别的排序时间不超过十秒:
count:10000 shell use Milliseconds:6
count:100000 shell use Milliseconds:180
count:1000000 shell use Milliseconds:3226