C语言
您现在所在的位置:首页>企业动态>C语言

希尔排序的底层逻辑-希尔排序的过程-学到牛C语言培训

编辑:学到牛牛IT培训    发布日期: 2022-06-24 17:32:28  

希尔排序的底层逻辑-希尔排序的过程-学到牛C++语言培训

希尔排序是一种特殊的插入排序,是对直接插入排序的升级改进。所以在学习希尔排序之前,一定要先弄清楚直接插入排序算法。

基本思路:

设一个序列里有n个待排序的元素,将间隔相同距离的元素分为一组进行比较,这里的间隔称之为增量,增量(gap)通常为n/2(奇数偶数都可以),随着算法的进行增量慢慢缩小,直到相邻的元素比较完,结束排序。

详细步骤:

首先,列出一组待排序的元素组成一个数组(如图1-1所示),数组长度len8,增量gap可为4,2,1(每结束一轮排序,增量减半),首先增量为4时,将间隔相同距离的元素分为一组进行比较

希尔排序图1 

1-1

 

相同颜色的元素即为一组进行比较(如图1-2所示)

希尔排序图2 

1-2

第一组:86进行比较,8 > 6两个元素交换位置(进行升序排序,小元素在前,大元素在后),如图1-3所示:

希尔排序图3 

1-3

第二组:12进行比较,1 < 2两个元素位置不变

第三组:53进行比较,5 > 3两个元素交换位置

第四组:47进行比较,4 < 7两个元素位置不变

第一轮比较结束,结果如图1-4所示:

 

希尔排序图4 

1-4

接下来增量为2重新对数组进行分组排序,共分为两组,如图1-5所示:

希尔排序图5 

1-5

第一组:6385进行比较,小的元素在前,大的元素在后,结果为3568

第一组:1427进行比较,小的元素在前,大的元素在后,结果为1247

第二轮比较结束,结果如图1-6所示:

希尔排序图6 

1-6

接下来继续缩小增量,当增量为1时,就是直接插入排序,如果不太清楚的同学可以看看之前插入排序算法的文章,最后一轮排序结束后就可以得到一个完整的升序数组(如图1-7所示)。

希尔排序图7 

1-7

代码实现:

#include <stdio.h>

 

void shellSort(int *a, int len)

{

   int i, j, k, temp, gap;  // gap 为增量

   for (gap = len / 2; gap > 0; gap /= 2)   // 增量初始化为数组长度的一半,每次遍历后增量减半

 {  

for (i = 0; i < gap; ++i)     // 变量 i 为每次分组的第一个元素下标

{

 for (j = i + gap; j < len; j += gap) //对增量为gap的元素进行直插排序,当gap1时,就是直插排序

{

                     temp = a[j];  // 备份a[j]的值

                     k = j - gap;  // j初始化为i的前一个元素(与i相差gap长度)

                     while (k >= 0 && a[k] > tmp)

{

                          a[k + gap] = a[k]; // 将在a[i]前且比temp的值大的元素向后移动一位

                           k -= gap;

                     }

                       a[k + gap] = temp;

                }

            }

        }

}

 

int main(  )

{

        int i;

        int a[8]={8,1,5,4,6,2,3,7};

        int len = 8;

        shellSort(a, len);        // 调用希尔排序函数

        printf("希尔升序排列后结果为: ");

        for (i = 0; i < len; i++)

 {                   

            printf("%d ",a[i]);      // 排序后的结果的输出

        }

        printf(" ");

 

        return 0;

}


免费试学
课程好不好,不如实地听一听

封闭学习

2

1

联系我们

电话:028-61775817

邮箱:1572396657@qq.com

地址:成都高新西区西芯大道4号

  • 学到牛牛在线咨询

    扫一扫,免费咨询

  • 学到牛牛公众号

    微信公众号

学一流技术,找高薪工作

7-24小时服务热线:

028-61775817

版权声明 网站地图

蜀ICP备2021001672号

课程问题轻松问