常用排序算法-希尔排序

清疚 2023-10-17 13:27 6阅读 0赞

1. 希尔排序简介

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序可以看作是对直接插入排序的一次升级，通过局部有序化，使得排序效率更高。下图引自百度百科：

![Center][]

可以看出希尔排序的原理过程非常简单，通过选择一个增量gap，暂定为N/2，N为待排序数字个数，在本例中gap=5，那么对分出的gap=5组子序列进行直接插入排序。接着将gap缩小，可以简单的将gap/=2，这样再对第二次分出的gap=3组子序列进行直接插入排序。重复此过程，直到gap=1的时候，此时希尔排序就化成了完全的直接插入排序，但是由于此时直接插入排序的对象是局部有序的，其速度和效率会大大增加。

2. 希尔排序基本流程

1. 选择增量gap=N/2

2. 将分出的gap组子序列分别进行直接插入排序；

3. 将gap缩小为gap=gap/2，继续过程2，直到gap=1的时候进行最后一次排序，也就是局部已经有序的直接插入排序。

3. 希尔排序实现

template <class T>
    void mySeqList<T>::ShellSort(T seqList[])
    {
        for (int gap=length/2; gap>=1; gap/=2)
        {
            for (int i=0; i<gap; ++i)
            {
                for (int j=i+gap; j<length; j+=gap)
                {
                    if (seqList[j]<seqList[j-gap])
                    {
                        int k = j-gap;
                        T temp = seqList[j];
                        while (k>=0&&temp<seqList[k])
                        {
                            seqList[k+gap] = seqList[k];
                            k = k-gap;
                        }
                        seqList[k+gap] = temp;
                    }
                }
            }
        }

4. 应该注意的问题

1. 增量gap一定等于分出的子序列组数；

2. 暂时没搞懂为何速度就能快，解释是交换次数变少了？存疑

[Center]: https://img-blog.csdn.net/20170526080639152?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveWhhbl9zaGVu/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center