【大话数据结构C语言】67 希尔排序

比眉伴天荒 2022-10-15 00:47 201阅读 0赞

众所周知，排序算法最重要的就是速度，但是前边介绍的几个算法时间复杂度都是n的平方

这个问题其实困扰了计算机界前辈们很久，一度有人认为“排序算法时间复杂度不可能突破n方”

但是，终有一天还是有科学家发现了，并且接连就出现好几种可以超越n方的排序算法，把内培训算法的时间复杂度提升到了nlogn

**希尔排序的时间复杂度是![2021052223155210.png][]，比前边几种的![202105222315529.png][]要好**

### **希尔排序** ###

事实上还是直接插入排序，然后分成几个小组分别排序

![dd33d928572b67fbcf657dacf9386286.png][]

#include <stdio.h>
    
    void InsertSort(int k[], int n)
    {
        int i, j, temp;
        int gap = n;
    
        do
        {
            gap = gap/3 + 1;
    
            for( i=gap; i < n; i++ )
            {
                if( k[i] < k[i-gap] )
                {
                    temp = k[i];
    
                    for( j=i-gap; k[j] > temp; j-=gap )
                    {
                        k[j+gap] = k[j];
                    }
    
                    k[j+gap] = temp;
                }
            }
        }while(gap > 1);
    }
    
    int main()
    {
        int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    
        InsertSort(a, 10);
    
        printf("排序后的结果是：");
        for( i=0; i < 10; i++ )
        {
            printf("%d", a[i]);
        }
        printf("\n\n");
    
        return 0;
    }

[2021052223155210.png]: https://img-blog.csdnimg.cn/2021052223155210.png
[202105222315529.png]: /images/20221014/4f51d35f3a724e88b862cf9dc1391971.png
[dd33d928572b67fbcf657dacf9386286.png]: /images/20221014/5ffb40c9542e4f7ea14fb8764051bdfa.png