希尔排序算法由 DONALD L. SHELL（1924-2015） 发明，于1959年发布于ACM算法存储库，它的算法复杂度取决于间隙序列的选择，当前仍无法确认希尔排序的算法复杂度

简介

希尔排序是一种不稳定（排序后可能会改变相同值的相对位置）的插入排序算法，它是一种自适应排序算法（当待排序队列部分有序时，算法执行更快），它是对插入排序的一种高效改进，通过增量序列使得元素能够快速移动，从而加速整个排序过程。增量序列的选取是希尔排序的关键，选择不当性能甚至会低于插入排序。10W个随机整数排序情况如下

原理

这里有视频图例

首先排序远距离的元素
逐渐缩小排序距离
最后变为原始的插入排序

间隙序列

计算机科学家对间隙序列的探索

代码实现

使用Rust语言实现希尔排序算法，间隙选择使用希尔序列

pub fn shell_sort<T:Ord + Copy>(arr:&mut[T]){
    let mut gap = arr.len() / 2;
    while gap > 0 {
        for i in 0..gap {
            for j in ((i+gap)..arr.len()).step_by(gap) {
                let mut k = j;
                let sorting = arr[k];
                while k >= gap && arr[k-gap] > sorting {
                    arr[k] = arr[k-gap];
                    k -=gap;
                }
                arr[k] = sorting;
            }
        }
        gap /=2;
    }
}

时间复杂度

应用

希尔排序在数据规模较小的情况下性能更佳，因此也常被用于一些混合排序中的子序列处理。它可以用很少的代码实现，并且不使用调用堆栈，因此针对嵌入式系统的C标准库中qsort函数的一些实现会使用它，例如uClibc库、以及早期Linux的内核中都有希尔排序的身影

参考

Shellsort
神秘的希尔排序

The best way to predict the future is to create it. - Vincent
There is no gene for the human spirit. - Irene

Gattaca

8lovelife's life

排序-希尔排序

简介

原理

间隙序列

代码实现

时间复杂度

应用

参考