【排序算法】希尔排序(缩小增量排序)

标签: 希尔排序  插入排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

基本思想:

先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

排序过程:

这里写图片描述

代码实现:

void shellSort(int *ary, int len)
{
    int i, j;
    int increment = len;//增量
    myDataType key;
    while (increment > 1)//最后在增量为1并且是执行了情况下停止。
    {
        increment = increment / 3 + 1;//根据公式
        //increment /= 2;

        printf("increment:%d\n",increment);
        for (i = increment; i<len; i++)//从[0]开始,对相距增量步长的元素集合进行修改。
        {
            key = ary[i];
            //以下和直接插入排序类似。
            j = i - increment;
            while (j >= 0)
            {
                if (key < ary[j])
                {
                    int temp = ary[j];
                    ary[j] = key;
                    ary[j + increment] = temp;
                }
                j = j - increment;
            }
        }
    }
}

分析:

shell其实是直接插入排序的优化写法,排序过程中,逆转数为0,表明排序完成了。

当inc = 1 时,相当于接近有序序列的直接插入排序。一般认为shell排序的时间复杂度为O(N^1.5)。

空间复杂度:O(1)。

稳定性:有序序列{2①, 4, 1, 2②},采用shell排序,设inc = 2,第一趟排序:{1,2②,2①,4},说明shell排序是不稳定的。

原文链接:加载失败,请重新获取