一，概念：希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一

二，复杂度：希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多

三：代码

 #include<stdio.h> #include<stdlib.h> //堆排序用于查找最大值 或者 最小值 void show(int *p, int n) {     for (int i = 0; i < n;i++)     {         printf("%4d", p[i]);     }     printf("n"); } void shellsort(int *p, int length) {     int d = length / 2;//增量     while (d >= 1)//增量终止条件     {         for (int i = d; d < length && i < length; i++)//最后的位置         {             int x = p[i];//备份数据             int j = i - d;//与其对于的前面的元素             while (j >= 0 && p[j]>x)//在数组范围内  找到擦入的位置             {                 p[j + d] = p[j];                 j = j - d;//每次变化             }             p[j + d] = x;//交换         }         //d = d / 2;         d--;//增量自由设定     } } void main() {     int a[8] = { 1, 8, 2, 7, 3, 6, 4, 5 };     show(a, 8);     shellsort(a, 8);     show(a, 8); }

你还在原价购买阿里云、腾讯云、华为云、天翼云产品？那就亏大啦！现在申请成为四大品牌云厂商VIP用户，可以3折优惠价购买云服务器等云产品，并且可享四大云服务商产品终身VIP优惠价，还等什么？赶紧点击下面对应链接免费申请VIP客户吧：

1、点击这里立即申请成为腾讯云VIP客户

2、点击这里立即注册成为天翼云VIP客户

3、点击这里立即申请成为华为云VIP客户

4、点击这里立享阿里云产品终身VIP优惠价

喜欢 (0)赏

[[email protected]]

分享 (0)