27 希尔排序.md

#数据结构 #算法 #C

[85] 希尔排序（Shell Sort）

也称递减增量排序算法，是插入排序的一种更高效的改进版本。按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

1. 算法思想

希尔排序：先追求表中元素部分有序，再逐渐逼近全局有序。

对于插入排序而言，如果原本的表中元素基本有序的话，那采用直接插入排序会达到一个相应不错的效率。
具体方法：
先将待排序表分割成若干形如 $L[ i, i + d, i + 2d,…, i + kd ]$ 的“特殊”⼦表，对各个⼦表分别进行直接插入排序。缩小增量 $d$，重复上述过程，直到 $d = 1$ 为⽌。

2. 算法过程

d的值从表长开始，每一轮d值折半。

3. 算法实现

以{50, 60, 61, 70, 80, 61, 83, 88, 87, 99}表排序为例。

// 希尔排序
void shellSort(int array[],int n){
    // d是元素的增量，
    int d, i, j;

    // array[0]是暂存单元，不是哨兵，当j <= 0时,插入位置已到
    for (d = n/2; d >= 1; d = d/2) {                // 控制步长
        for (i = d + 1; i <= n; ++i){
            if (array[i] <= array[i - d]){          // 需要将array[i]插入有序增量子表
                array[0] = array[i];                // 暂存在array[0]
                for (j = i-d; j > 0 && array[0] < array[j]; j -= d){
                    array[j + d] = array[j];        // 记录后移
                }
                array[j + d] = array[0];            // 插入
            }
        }
    }
}

动画演示： #未完待续

4. 算法性能分析

• 空间复杂度： $O(1)$
• 时间间复杂度：和增量序列 $d_1, d_2, d_3 …$ 的选择有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度。
  • 最坏时间复杂度为 $O(N^2)$ ，当 $n$ 在某个特定条件下，可以保证性能提升到至 $O(nlog^2n)$。
• 稳定性：不稳定的排序算法
• 适⽤性：仅适⽤于顺序表，不适⽤于链表。