排序算法07----------------------希尔排序

2021-02-19 06:18

阅读：476

标签：步骤 shel bsp main col turn 元素 print 一个

1.希尔排序

　　希尔排序是对直接插入排序的一种改进，基本思想是隔一定间隔取元素组成一组元素，然后对这组元素进行直接插入排序，所有元素排序完一次后。间隔减少，再进行同样的操作，直到间隔变为1，这时就是直接插入排序了，因为经过前面的步骤，元素大多数都是有序了，直接插入排序，对有序序列的效率是很高的。

2.步骤

　　1）首先取间隔gap,一般取gap=n/2,下面是8个元素进行一次排序后的结果。

　　　　每隔4个元素取一个元素组成一组，然后进行直接插入排序。

　　2）然后间隔gap=gap/2

　　技术图片

　　3)再取一次gap=gap/2 gap就为1，就是直接插入排序了

3.代码

　　代码其实不难，就是直接插入排序算法嵌套一层间隔循环

 1 #include 2 //希尔排序 
 3 void shellSort(int * arr,int num)
 4 {
 5     int i,j,k;
 6     int temp,gap;
 7     //间隔每次除2 
 8     for(gap=num/2;gap>0;gap/=2)
 9     {    
10         //直接插入排序算法 
11         for(k=gap;k)
12         {
13             temp=arr[k];
14             j=k-gap;
15             while(j>=0&&arr[j]>temp)
16             {
17                 arr[j+gap]=arr[j];
18                 j-=gap;
19             }
20             arr[j+gap]=temp;
21         }
22     }
23 }
24 int main()
25 {
26     int i; 
27     int arr[10]={1,3,-9,0,10,2,8,9,19,-1};
28     shellSort(arr,10);//希尔排序
29     for(i=0;i10;i++)
30         printf("%d\n",arr[i]);
31     return 0;
32 }

技术图片

希尔排序算法的时间复杂度O(n^1.3到n^2)

排序算法07----------------------希尔排序

标签：步骤 shel bsp main col turn 元素 print 一个

原文地址：https://www.cnblogs.com/duichoumian/p/12685403.html

上一篇：12Java泛型

下一篇：Horspool算法（java）随机生成字符串

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：排序算法07----------------------希尔排序
文章链接：http://soscw.com/index.php/essay/57399.html

亲，登录后才可以留言！

排序算法07----------------------希尔排序

评论

热门文章

推荐文章

最新文章

置顶文章