signed

QiShunwang

“诚信为本、客户至上”

刻意练习-希尔排序C语言

2021/6/24 20:21:26   来源:

一、介绍

  1. 希尔排序,是插入排序的改进版。是为了减少插入排序中对数值的移动次数。

  2. 比如,这个数列需要插入一次就完成排序。

    在这里插入图片描述

  3. 但是这个序列就要插入好多次。

    在这里插入图片描述

    如图,1,2,3,4,都要前移,而且都是最远距离。

  4. 说明一个问题,插入排序在基本有序的情况下,做的插入操作更少,效率更高。 希尔排序就是为了让数列基本有序。

  5. 希尔排序让每个值先跳着插,让整个数列基本有序。最后再调用插入排序。

在这里插入图片描述

先跳5/2=2个插入:

在这里插入图片描述

变成这样:

在这里插入图片描述

此时已经是基本有序了。

然后跳2/2=1个插,就是基本的插入排序。

得到结果。
在这里插入图片描述

二、抽象

  1. 这里可以参考插入排序。

    https://blog.csdn.net/renyongjian1994/article/details/118115418

    在这里插入图片描述

    基本上有这些元素。

  2. 希尔排序的不同点在于要先大幅度的插入几次。

    所以要多抽象一个移动的幅度。gap。还有计算幅度的算法。在例子中,第一次是5/2=2,第二次是2/2=1。算法在这里就是每次除以2。

    • 在插入排序中是这样找插入位置的。

          //每个成员都可能是那个3.
          for(i=0;i<arr_len;i++)
          {
              //从后往前,每次往前插入一个。
              for(j=i+1;j>1;j--)
              {
                  if(compare(&arr[j],&arr[j-1]) < 0)
                  {
                      //还需继续前移
                      swap(&arr[j],&arr[j-1]);
                  }
                  else
                  {
                      break;
                  }
              }
          }
      
    • 希尔排序中,需要先计算前移的幅度。就是把步长从原来的1->gap。

      int gap = 1;
      //从后往前,每次往前插入一个。
      gap = shell_calculate_gap(gap);
      
      //每个成员都可能是那个3.
      for(i=0;i<arr_len;i=i+gap)
      {
          for(j=i+gap;j > gap && j < arr_len;j=j-gap)
          {
              if(compare(&arr[j],&arr[j-gap]) < 0)
              {
                  //还需继续前移
                  swap(&arr[j],&arr[j-gap]);
              }
              else
              {
                  break;
              }
          }
      }
      

三、实现

  1. 借助插入排序的代码,其实可以看出来,插入排序其实就是gap始终是1的情况。所以可以做个简单的修改。

    //插入排序代码不变,但是多传了一个gap为参数。
    int insert_sort(int *arr,int arr_len,int gap)
    {
        int i = 0;
        int j = 0;
        //每个成员都可能是那个3.
        for(i=0;i<arr_len;i=i+gap)
        {
            //从3的位置往前找。
            for(j=i;j>0;j=j-gap)
            {
                if(compare(&arr[j],&arr[j-gap]) < 0)
                {
                    //还需继续前移
                    swap(&arr[j],&arr[j-gap]);
                }
                else
                {
                    break;
                }
            }
        }
    }
    
  2. 然后只需要依次把 gap=5/2=2,2/2=1,传进来就可以

    int arr[] = {8,7,6,5,4,3,2,1,0};
    int arr_len = sizeof(arr)/sizeof(arr[0]);
    int gap = shell_calculate_gap(arr_len);
    while(gap)
    {
        insert_sort(arr,arr_len,gap);
        gap = shell_calculate_gap(gap);
    }
    

四、整理总结

  1. 比插入排序对数组进行了预处理。让数组先基本有序。所以抽象了一个gap,让每次前移数据的步长不同。

  2. 最终代码。

    #include<stdio.h>
    
    int compare(int *a,int *b)
    {
        if(a == NULL || b == NULL)
        {
            return 0;
        }
        if(*a > *b)
        {
            return 1;
        }
        
        if(*a == *b)
        {
            return 0;
        }
    
        return -1;
    
    }
    
    int swap(int *a,int *b)
    {
        int tmp = *a;
        *a = *b;
        *b = tmp;
        return 0;
    }
    
    int print_arr(int *arr,int len)
    {
        int i = 0;
        for(i = 0;i < len;i++)
        {
            printf("%d,",arr[i]);
        }
        printf("\n");
        return 0;
    }
    
    
    int insert_sort(int *arr,int arr_len,int gap)
    {
        int i = 0;
        int j = 0;
        //每个成员都可能是那个3.
        for(i=0;i<arr_len;i=i+gap)
        {
            //从3的位置往前找。
            for(j=i;j>0;j=j-gap)
            {
                if(compare(&arr[j],&arr[j-gap]) < 0)
                {
                    //还需继续前移
                    swap(&arr[j],&arr[j-gap]);
                }
                else
                {
                    break;
                }
            }
        }
    }
    
    
    int shell_calculate_gap(int src_gap)
    {
        return src_gap/2;
    }
    
    int main(int argc, const char *argv[])
    {
        int arr[] = {8,7,6,5,4,3,2,1,0};
        int arr_len = sizeof(arr)/sizeof(arr[0]);
        int gap = shell_calculate_gap(arr_len);
        //第一次的gap是 arr_len/2,算出来的。
        while(gap)
        {
            //使用间距为gap跳着插入,做预处理。如果间距是1了,就会做插入排序。然后就退出了。
            insert_sort(arr,arr_len,gap);
            //重新调整间距
            gap = shell_calculate_gap(gap);
        }
        
        print_arr(arr,arr_len);
        return 0;
    }
    
  3. 简单的看看两者移动操作数量变化。

在这里插入图片描述

希尔排序仅仅移动了20次,但是插入排序移动了36次。

五、方法记忆

  1. 希尔排序是加强版本的插入排序。在插入排序之前,做了预处理,让数列先基本有序。

  2. 插入排序gap就是1,希尔排序是先大幅度移动,让数列基本有序,逐步变成1.

  3. 相关抽象整理

    在这里插入图片描述

六、参考

https://blog.csdn.net/renyongjian1994/article/details/118115418