精华内容
下载资源
问答
  • 希尔排序(Shell’s Sort)又称为“缩小增量排序”(Diminishing Increment Sort),是对直接插入排序的改进版本。是一个非稳定的排序算法。时间复杂度为O(n1.3)~O(n2)。 算法的时间复杂度对比: 主要对插入排序作出...

    介绍

    希尔排序(Shell’s Sort)又称为“缩小增量排序”(Diminishing Increment Sort),是对直接插入排序的改进版本。是一个非稳定的排序算法。时间复杂度为O(n1.3)~O(n2)。

    算法的时间复杂度对比:
    在这里插入图片描述
    主要对插入排序作出以下改进:

    • 插入排序对近乎有序的数据效率非常高,可达到O(n)的时间复杂度。
    • 插入排序每次只移动一个位置,是低效的。

    思路

    • 设定一个增量gap,初始化gap=n/2,完成一趟插入后,gap /= 2
    • 进行插入排序,只是每次不是与前一个元素比较是与前gap个元素比较
      在这里插入图片描述

    实现代码

    以升序为例

    #include<bits/stdc++.h>
    using namespace std;
    
    template<typename T>
    void shellSort(T arr[], int n) {
        for(int gap = n/2; gap > 0; gap /= 2) {
            for(int i = gap; i < n; i++) {
                int j;
                T temp = arr[i];
                for(j = i; j >= gap && arr[j-gap] > temp; j -= gap) {
                    arr[j] = arr[j-gap];
                }
                arr[j] = temp;
            }
        }
        return;
    }
    
    int main(int argc, char const *argv[])
    {
        // 测试
        int arr[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        shellSort(arr, 10);
        for(int i = 0; i < 10; i++) {
            printf("%d ", arr[i]);
        }
        return 0;
    }
    

    最后

    • 由于博主水平有限,难免有疏漏之处,欢迎读者批评指正!
    展开全文
  • 希尔排序法

    2012-10-23 10:01:16
    希尔排序法练习 包括代码 算法描述 流程图 希望对您有帮助
  • 新增两中排序算法实现,测试ok,当做我今天的作业吧! template <typename T> void printArr(T* a,size_t sz,string sort_type) { cout<<sort_type<<" "; for(auto i=0;i<sz;++i) cout<<...

    新增两中排序算法实现,测试ok,当做我今天的作业吧!

    template <typename T>
    void printArr(T* a,size_t sz,string sort_type)
    {
        cout<<sort_type<<" ";
        for(auto i=0;i<sz;++i)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    template <typename T>
    void shell_st(T*a,size_t sz)
    {
        auto gap=sz/2;
        while(gap>=1)
        {
            for(auto i=gap;i<sz;++i)
            {
                T tmp=a[i];
               auto  j=0;
                for(j=i-gap;j>=0&&tmp<a[j];j-=gap)
                    a[j+gap]=a[j];
                  a[j+gap]=tmp;
            }
    
            gap/=2;
        }
        printArr(a,sz,"shell");
    }
    template <typename T>
    void Merge(T*a,int s,int m,int e)
    {
        T *t=new T[e-s+1];
        int iL=s,iR=m+1,iT=0;
        while(iL<=m&&iR<=e)
        {
            if(a[iL]<=a[iR])
                t[iT++]=a[iL++];
            else
                  t[iT++]=a[iR++];
        }
          while(iL<=m)
                t[iT++]=a[iL++];
          while(iR<=e)
                t[iT++]=a[iR++];
          for(int i=0;i<iT;++i)
              a[s+i]=t[i];
    }
    template <typename T>
    void MergeSort(T*a,int s,int e)
    {
        if(s>=e||a==nullptr)
            return;
        int m=(s+e)/2;
        MergeSort(a,s,m);
        MergeSort(a,m+1,e);
        Merge(a,s,m,e);
    }
    int main() {
        int  a[]{ 5,6,1,8,3,4,9,7,2,3,45,6,77,88,45,23};
        auto end=sizeof (a)/sizeof (int)-1;
        cout << "归并排序前:";
        for (int i = 0; i < end+1; i++)
            cout << a[i] << ' ';
        cout << endl;
        shell_st(a,end+1);
        MergeSort(a,0,end);
        //    merge_sort(a, end+1);
        cout << "归并排序后:";
        for (int i = 0; i < end+1; i++)
            cout << a[i] << ' ';
        cout << endl;
    }
    
    展开全文
  • 刻意练习-希尔排序

    2021-06-24 20:08:51
    希尔排序,是插入排序的改进版。是为了减少插入排序中对数值的移动次数。 比如,这个数列需要插入一次就完成排序。 但是这个序列就要插入好多次。 如图,1,2,3,4,都要前移,而且都是最远距离。 说明一个问题...

    一、介绍

    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. 数组是{1,2,4,5,3} 这种情况(基本有序)直接使用插入排序。数组是{5,4,3,2,1}这种情况(乱序)使用希尔排序。 和实际例子结合,具象化,应该效果更好。

    4. 相关抽象整理

      在这里插入图片描述

    六、参考

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

    展开全文
  • Scala练习-希尔排序

    2017-06-28 22:48:33
    白话经典算法系列之三 希尔排序的实现 ShellSortpackage day14/** * Created by doctorq on 2017/6/28. * 希尔排序:缩小增量排序 * 时间复杂度nlog2n~n2之间 */ object ShellSort extends App with Utils { ...

    参考文章:
    白话经典算法系列之三 希尔排序的实现
    ShellSort

    
    package day14
    
    /**
      * Created by doctorq on 2017/6/28.
      * 希尔排序:缩小增量排序
      * 时间复杂度nlog2n~n2之间
      */
    object ShellSort extends App with Utils {
    
    
      def sort(unSort: Array[Int]): Array[Int] = {
        var step = unSort.size / 2
    
        while (step > 0) {
          //分成的子数组个数为step
          for (i <- 0 until step) {
            //某个子数组采用插入排序算法进行排序
            for (j <- i + step to(unSort.size - 1, step)) {
              //直接插入排序
              if (unSort(j) < unSort(j - step)) {
                var k = j - step
                while (k > 0 && unSort(k + step) < unSort(k)) {
                  swap(unSort, k, k + step)
                  k -= step
                }
              }
            }
          }
          step /= 2
        }
    
        unSort
      }
    
      val list = Array(1, 4, 3, 5, 7, 3, 6, 8, 9, 23, 4, 5, 7, 2, 4, 5, 6, 7, 78, 3, 4)
      printlnArray(sort(list))
    
    }
    
    展开全文
  • 具体程序运行:E:\Java project\20200501-StringBuffer-练习 如果我们要进行拼串的操作,推荐使用StringBuffer. StringBuffer长度可变的字符序列。 String长度不可变的字符序列。 StringBuffer()构造一个其中不带...
  • 附加以前做的希尔排序图及代码: /// /======================================= void Shellpass( int a[], int d, int n) { // 希尔排序法中的一趟排序,d为增量 int i,j,t; int c; for (i=d; i;i++) ...
  • 插入排序,希尔排序,归并排序层层递进的方式进行解读评判一个算法的好坏一、插入排序二、希尔排序三、归并排序稳定性总结 评判一个算法的好坏 1.时间效率 2.空间复杂度 3.比较次数&交换次数 4.稳定性 排序肯定...
  • 希尔排序是插入排序的优化版。 插入排序的最坏时间复杂度是O(n2),但如果要排序的数组是一个几乎有序的数列,那么会降低有效的减低时间复杂度。 希尔排序的目的就是通过一个increment(增量)来对数列分组进行交换...
  • 希尔排序法(Shell Sort) 希尔排序法(缩小增量法)属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序的方法。 该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个...
  • java语言对希尔排序的实现,以及对该算法的思考
  • public static void shellSort(int[] data){ int j = 0; int temp = 0; for (int i = data.length/2; i&gt;0; i/=2) { for (int k = i; k &lt; data.length; k++) { temp = data[k];......
  • 算法描述:希尔排序是插入排序的一种改进,主要是为了解决当较小的数据大都出现在数组后面时导致的移动次数明显增多的问题,思想是使用一个不断缩小的增量gap将数组元素分组,在每个分组内部先进行插入排序,当gap...
  • 希尔排序是非稳定排序算法希尔排序是基于插入排序的以下两点性质而提出改进方法的: 1,插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。(这是为啥呢?点击去看看), ...
  • 本文件是7种常用排序算法的实现(C++),包括冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序。代码详细有注释且有测试用例。
  • shell sort也称缩小增量排序,是对插入排序算法的改进,其工作原理是定义一个间隔序列来表示排序过程中进行比较的元素之间有多远的间隔,每次将具有相同间隔的数分为一组,进行插入排序,大部分场景中,间隔是可以...
  • 内部排序 内部排序指的是待排序记录全部存放在计算机内存中进行排序地过程 插入排序 希尔排序 交换排序 冒泡排序 快速排序 选择排序 简单选择排序 堆排序 归并排序 ...
  • 进行希尔排序练习。明白希尔排序原理。 希尔排序:将间隔d的元素视为待排序数组,对该数组进行插入排序。然后逐步缩小d的值,最后直到d=1。这个特点又可以称呼希尔排序为缩小增量排序。 d=1时为直接插入排序。 d...
  • 程序实现希尔排序,C语言入门程序,适合C语言课程入门的小练习。 程序实现希尔排序,C语言入门程序,适合C语言课程入门的小练习。 程序实现希尔排序,C语言入门程序,适合C语言课程入门的小练习

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,430
精华内容 572
关键字:

练习希尔排序算法