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

佚名 4年前 (2020-04-12) 算法 617人围观抢沙发百度已收录

1.希尔排序

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

2.步骤

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

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

　　2）然后间隔gap=gap/2

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

3.代码

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

 1 #include<stdio.h>
 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<num;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;i<10;i++)
30         printf("%d\n",arr[i]);
31     return 0;
32 }