排序算法四——希尔排序

墨蓝 2022-06-10 02:44 117阅读 0赞

\*\*

# 排序算法三：希尔排序（shell） #

\*\*

希尔排序本质上还是插入排序，只不过是在直接插入排序前做一些小动作，什么小动作呢？那就是通过分组，在每一组组内进行排序，排完序再合并在一起，经过若干次这样的“小动作”之后，这一组数字就是基本有序了，注意是基本有序，而不是排好序。（基本有序的意思就是最小的基本上在前面，大的基本在后面）为什么要让这一组数字基本有序呢？在直接插入排序的时候我给大家证明了插入排序是在基本有序的时候交换次数最少，效率最高。  
当数字很多很多的时候用这样的方法排序时间大大缩减，希尔排序是第一个时间复杂度突破O（n^2）的排序方法，之前说的冒泡，选择，插入排序的时间复杂度都是O（n^2），所以我觉得shell这个人很牛x。  
上文的“分组”是有技巧的，假设一组数\{9，7，6，3，4，5，2，0，1\}，这么分：\{9，7，6\}，\{3，4，5\}，\{2，0，1\}，经过排序后合并成\{6，7，9，3，4，5，0，1，2\}，我们发现9还是在靠前的位置，0还是在靠后的位置，这样的方法分组分一万次，这组数字  
都不可能基本有序。所以shell想到了“步长”，隔几个数取一个数，这样分组后排序，然后再合并，几次后就基本有序了，然后再用直接排序（直接排序就是步长为1），这样岂不是美滋滋！  
（本人理解的希尔排序，如有错误，欢迎指正！）

希尔排序代码：

/***************************************************** File name:4shell_sort.c Author: Tang Zhiqian Date:2017-08-08 14:33 *****************************************************/
    //希尔排序
    
    #include <stdio.h>
    
    #define MAX 10
    
    typedef int ElementType;
    typedef ElementType ARR[MAX];    //定义数组
    
    ARR arr = {
       1,9,0,2,6,3,7,4,8,5};
    int len = sizeof(arr)/sizeof(ElementType);    //全局变量len
    
    void print(ARR arr)
    {
        int i;
        for (i = 0; i < len; i++)
        {
            printf("%d ",arr[i]);
        }
        printf("\n");
    }
    
    void ShellSort(ARR arr)
    {
        int i,j,gap;    //gap:步长
        int temp;
        int k = 0;    //记录输出的次数
        gap = len;
        while(gap > 1)    //步长为1时停止，此时步长为1的数组已经排好序
        {
            gap = gap/3 + 1;
            for (i = gap + 1; i < len; i++)
            {
                if (arr[i] < arr[i - gap])
                {
                    temp = arr[i];    //记录要插入的数
                    for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)    //将大于temp的数字往后移动
                    {
                        arr[j + gap] = arr[j];
                    }
                    arr[j + gap] = temp;    //插入到正确位置
    
                    printf("第%d次排序:",++k);
                    print(arr);
                }
            }
        }
    }
    
    int main()
    {
        ShellSort(arr);
    
        return 0;
    }

程序运行结果：  
![这里写图片描述][SouthEast]

美滋滋！

[SouthEast]: /images/20220610/ccfe1502503948fc890d757761e6ecf1.png