[C语言] 插入排序之希尔(shell)排序的特性及实现

[C语言] 插入排序之希尔(shell)排序的特性及实现[C语言] 插入排序之希尔(shell)排序的特性及实现 1、算法特性 希尔排序法又称缩小增量法,由直接插入排序改进而来,是一种不稳定的插入排序方法。其本质上是一种分组排序方法,不需要大量的辅助空间,和归并排序一样容易实现,适合中小规模的数据排序。 其时间复杂度最好情况为O(n)、最差为O(n&#1

[C语言] 插入排序之希尔(shell)排序的特性及实现

 

1、算法特性

  希尔排序法又称缩小增量法,由直接插入排序改进而来,是一种不稳定的插入排序方法。其本质上是一种分组排序方法,不需要大量的辅助空间,和归并排序一样容易实现,适合中小规模的数据排序。

  其时间复杂度最好情况为O(n)、最差为O(n²)、平均为O(n^1.5),空间复杂度为O(1)。

 

2、算法思路

  希尔排序先是设定了一个增量l(一般初始l=len/2),并通过插入排序将所有相距为l的数据排成有序序列,接着将增量l缩小折半,继续利用插入排序排序。 经过不断循环,当l折半至1时便可以将所有数据排列有序。

[C语言] 插入排序之希尔(shell)排序的特性及实现       [C语言] 插入排序之希尔(shell)排序的特性及实现

 

3、实现代码

 1 #include <stdio.h>
 2 
 3 // 插入排序: shell排序
 4 void shell_sort(int a[], int len)
 5 {
 6     int i,j,l;
 7     for(l=len/2; l>0; l/=2)
 8     {
 9         for(i=l; i<len; i++)
10         {
11             int temp = a[i];
12             for(j=i; j>=l && a[j-l]>temp; j-=l)
13                 a[j] =a [j-l];
14             a[j] = temp;
15         }
16     }
17 }
18 
19 void travel(int arr[],int len)
20 {
21     for(int i=0;i<len;i++)
22     {
23         printf("%d ",arr[i]);    
24     }    
25     printf("\n");
26 }
27 
28 int main()
29 {
30     int arr[] = {53,82,9,233,43,14,55,9,4,67};
31     int len = sizeof(arr)/sizeof(arr[0]);
32 
33 /*    travel(arr,len);
34     insert_sort(arr,len);
35     travel(arr,len);*/
36 
37 /*    travel(arr,len);
38     binary_insert_sort(arr,len);
39     travel(arr,len);*/
40 
41     travel(arr,len);
42     shell_sort(arr,len);
43     travel(arr,len);
44 
45     return 0;
46 }

 

4、实现效果

[C语言] 插入排序之希尔(shell)排序的特性及实现

今天的文章[C语言] 插入排序之希尔(shell)排序的特性及实现分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/57306.html

(0)
编程小号编程小号
上一篇 2023-08-25
下一篇 2023-08-25

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注