希尔排序

维基百科，自由的百科全书

希尔排序(Shell Sort)也称为递减增量排序算法，是插入排序的一种高速而安定的改良版。因希尔(Donald L. Shell)于1959年提出而得名。各种实现在如何进行递减上有所不同。

對有n個元素的可比較資料，先取一个小于n的整数d₁作为第一个增量，把文件的全部记录分成d₁个组。所有距离为d₁的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d₂<d₁重复上述的分组和排序，直至所取的增量d_t=1(d_t<d_t-1<…<d₂<d₁)，即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法。

[编辑] Code Sample in C

int main()
{
    const int n = 5;
    int i, j, gap, temp; 
    int a[] = {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;
        }
    }
}