数据结构--排序之希尔排序

●🧑个人主页:你帅你先说.
●📃欢迎点赞👍关注💡收藏💖
●📖既选择了远方，便只顾风雨兼程。
●🤟欢迎大家有问题随时私信我！
●🧐版权：本文由[你帅你先说.]原创，CSDN首发，侵权必究。

🍟希尔排序基本思想及代码实现

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

希尔排序是在直接插入排序的思想上进行优化的，它主要分为两步:
1.分组预排序–数组接近有序
2.直接插入排序
🍔图解过程


上述过程用代码实现就是这样:

//橙色组单趟的希尔排序voidShellSort(int*a,int n){int gap =3;int end =0;int x = a[end+gap];while(end>=0){if(a[end]>x){
            a[end+gap]= a[end];
            end-=gap;}else{break;}}
    a[end+gap]= x;}

上述过程用代码实现就是这样:

//橙色整个组的希尔排序voidShellSort(int*a,int n){int gap =3;for(int i =0;i<n-gap;i+=gap){int end = i;int x = a[end+gap];while(end>=0){if(a[end]>x){
                a[end+gap]= a[end];
                end-=gap;}else{break;}}}
        a[end+gap]= x;}

同样，对绿色组和蓝色组进行插入排序。

上述过程用代码描述就是这样的:

//橙色整个组的希尔排序voidShellSort(int*a,int n){int gap =3;for(int j =0;j<gap;j++){for(int i = j;i<n-gap;i+=gap){int end = i;int x = a[end+gap];while(end>=0){if(a[end]>x){
                    a[end+gap]= a[end];
                    end-=gap;}else{break;}}}}
        a[end+gap]= x;}

🍿动图演示:

到这一步，我们先来分析一下它的时间复杂度。
最好时间复杂度:O(N)
最坏时间复杂度:F(N,gap) = (1+2+3+…

     N
    
    
     
      g
     
     
      a
     
     
      p
     
    
   
  
  
   \frac{N}{gap}
  
 
gapN​)***gap**

从图中我们可以发现这样的规律:
gap越大预排越快,预排后越不接近有序
gap越小预排越慢,预排后越接近有序

接下来我们就进行多组排序,过程我就不画了,大家可以自己动手画画,直接上代码。

//多个组一起排序voidShellSort(int*a,int n){int gap =3;for(int i =0;i<n-gap;i++){int end = i;int x = a[end+gap];while(end>=0){if(a[end]>x){
                a[end+gap]= a[end];
                end-=gap;}else{break;}}}
        a[end+gap]= x;}

现在只差最后一步了,控制gap。

voidShellSort(int*a,int n){int gap = n;while(gap>1){
        gap /=2;//gap = gap/3+1;这种方法也可以for(int i =0;i<n-gap;i++){int end = i;int x = a[end+gap];while(end>=0){if(a[end]>x){
                    a[end+gap]= a[end];
                    end-=gap;}else{break;}}}}
        a[end+gap]= x;}

那整个希尔排序的时间复杂度是多少呢?
如果是 gap /= 2，那么时间复杂度就是O(N

    l
   
   
    o
   
   
    
     g
    
    
     2
    
   
   
    N
   
  
  
   log_2N
  
 
log2​N)

如果是 gap/=3+1 那么时间复杂度就是O(N

    l
   
   
    o
   
   
    
     g
    
    
     3
    
   
   
    N
   
  
  
   log_3N
  
 
log3​N)

有的书上针对于这个时间复杂度还会给一种答案

即时间复杂度为: O(

     N
    
    
     1.3
    
   
  
  
   N^{1.3}
  
 
N1.3)。

🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲
觉得写的不错可以给个

一键三连

点赞👍关注💡收藏💖
🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲