希尔排序
维基百科，自由的百科全书
希尔排序(Shell Sort)也称为递减增量排序算法，是插入排序的一种高速而安定的改良版。因希尔(Donald L. Shell)于1959年提出而得名。各种实现在如何进行递减上有所不同。
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-1<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
[编辑] Code Sample in C
void main()
{
const int n = 5;
int i, j, gap, temp;
int a[n] = {5, 4, 3, 2, 1};
gap = n/2;
while (gap>0)
{
for (i = gap; i < n; i++)
{
j = i - gap;
while (j >= 0)
{
if (a[j]>a[j + gap])
{
temp = a[j];
a[j] = a[j + gap];
a[j + gap] = temp;
j = j - gap;
}
else
j = -1;/* or break */
}
}
gap = gap/2;
}
}
[编辑] Code Sample in Java
void shellsort (int[] a, int n)
{
int i, j, k, temp, gap;
int[] gaps = { 1,5,13,43,113,297,815,1989,4711,11969,27901,84801,
213331,543749,1355339,3501671,8810089,21521774,
58548857,157840433,410151271,1131376761,2147483647 };
for (k=0; gaps[k]<n; k++) ;
while (--k >= 0)
{
gap = gaps[k];
for (i=gap; i<n; i++)
{
temp = a[i];
j = i;
while (j>=gap && a[j-gap]>temp)
{
a[j] = a[j-gap];
j = j-gap;
}
a[j] = temp;
}
}
}
