Spiga

内排序（二）：希尔排序

2012-07-08 11:52:47

希尔排序(Shell Sort)是插入排序的一种。因D．L．Shell于1959年提出而得名。

一、基本思想
　　对待排记录序列先作“宏观”调整，再作“微观”调整。
　　所谓“宏观”调整，指的是 “跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序。关键是，这种子序列不是由相邻的记录构成的。假设将n个记录分成d个子序列，则这d个子序列分别为：
{ R[1]，R[1+d]，R[1+2d]，…，R[1+kd] }
{ R[2]，R[2+d]，R[2+2d]，…，R[2+kd] }
…
{ R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] }
　　其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。
　　下图为希尔排序示意图：
　　　　
二、希尔排序的实现

public class ShellSort
{ 
    public static List<int> Demo(List<int> data)
    {
        for (int gap =(int) Math.Floor(((decimal)(data.Count / 2))); gap > 0; gap = (int)Math.Floor(((decimal)(gap / 2))))
        {
            for (var i = gap; i < data.Count; i++)
            {
                var j = i;
                var current = data[i];
                while (j - gap >= 0 && current < data[j - gap])
                {
                    data[j] = data[j - gap];
                    j = j - gap;
                }
                data[j] = current;
            }
        }
        return data;
    }
}

三、时间复杂度分析

　　大量研究证明，若增量序列的取值比较合理，希尔排序时关键字比较次数和记录移动次数接近于O（n(log2n)2）
　　由于希尔排序法是按增量分组进行的排序，所以希尔排序是不稳定的排序。
　　希尔排序法适用于中等规模的记录序列的排序的情况。