Title Date Modified Category
shell sort 2019-07-09 12:00 2019-07-09 12:00 algorithm

1. shell sort

希尔排序(Shell Sort)。希尔排序是D.L.Shell于1959年提出来的一种排序算法,在这之前排序算法的时间复杂度基本都是O(n^2)的,希尔排序算法是突破这个时间复杂度的第一批算法之一。

所谓的 基本有序,就是小的关键字基本在前面,大的基本在后面,不大不小的基本在中间,像{2,1,3,6,4,7,5,8,9}这样可以称为基本有序了。

将相距某个“增量”的记录组成一个子序列,这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

/* 对顺序表L作希尔排序 */
void ShellSort(SQList *L)
{
    int i, j;
    int increment = L->length;

    do
    {
        increment = increment / 3 + 1; /* 增量序列 */
        for (i = increment + 1; i <= L->length; i++)
        {
            if (L->r[i] < L->r[i - increment])
            {
                /* 需将L->r[i] 插入有序增量子表 */
                L->r[0] = L->r[i]; /* 暂存在L->r[0] */
                for (j = i - increment; j > 0 && L->r[0] < L-r[j]; j -= increment)
                {
                    L->r[j + increment] = L->r[j]; /* 记录后移,查找插入位置 */
                }
                L->r[j + increment] = L->r[0]; /* 插入 */
            }
        }
    }
    while (increment > 1);
}

1.1. 希尔排序复杂度分析

希尔排序的关键并不是随便分组后各自排序,而是将相隔某个“增量”的记录组成一个子序列,实现跳跃式的移动,使得排序的效率提高。

增量序列的最后一个增量值必须等于1才行。

不管怎么说,希尔排序算法的发明,使得我们终于突破了慢速排序的时代(超越了时间复杂度为O(n^2)),之后,相应的更为高效的排序算法也就相继出现了。

2. 参考资料

2.1. books

  • 《大话数据结构》

results matching ""

    No results matching ""