【算法】希尔排序算法Shell Sort

- 日理万妓 2022-11-01 04:26 206阅读 0赞

原理

基本思想：希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便终止。
在这里插入图片描述
在这里插入图片描述

代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void print_sort(int arr[],int n)
  4. {
  6.     int i;
  7.     for(i=0;i<n;i++)
  8.     {
  10.         cout<<arr[i]<<" ";
  11.      }
  12. }
  13. void shell_sort(int arr[],int n)
  14. {
  16.     int i,j,inc,key;//inc初始增量 
  17.     //初始增量是n/2，每一趟之后除以2
  18.     for(inc=n/2;inc>0;inc/=2) 
  19.     {
  21.         //每一趟采用插入排序
  22.         for(i=inc;i<n;i++)
  23.         {
  25.             key=arr[i];
  26.             for(j=i;j>=inc&&key<arr[j-inc];j-=inc)
  27.             {
  29.                 arr[j]=arr[j-inc];
  30.             }
  31.             arr[j]=key;
  32.         } 
  33.     }
  34. } 
  35. int main()
  36. {
  38.     int arr[]={
  39.     15,5,2,7,12,6,1,4,3,9,8,10};
  40.     shell_sort(arr,12);
  41.     print_sort(arr,12);
  42.     return 0;
  43. }

基本都是插入排序，只不过变成了缩小增量来排序

发表评论

表情：
评论列表 （有 0 条评论，206人围观）

还没有评论，来说两句吧...

相关阅读