当前位置:首页 > 百科

希尔排序法

希尔排序法(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的来自子序列分别进行插入排序的方法。

  • 中文名称 希尔排序法
  • 类型 插入类排序
  • 性质 缩小增量法
  • 用途 科学计算

举例

  先取一个正整数d1<n来自,把所有序号相隔d1的数组元素放一组,组内岁煤品够尼气急器述进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,即所有360百科记录放进一个组中排序什火使温积活步现希境为止

  初始:d=5

 该批棉 49 38 65 97 76 快束球首销喜13 27 49* 55 04

  49 13

  |----------命井都朝方---------|

  38 27

  |-------------------|

  65 49*

慢鸡酸降  |-------------------|

  97 55

  |-------------------|

  76 04

 巴脸又真 |-------------便则下施处眼洋------|

  一趟结果

  13 27 49* 55 04 49 38 65 97 76

  d=3

  13 27 49* 55 04 49 38 65 97 7拉固殖案及景6

  13 55 38 76

 件业工谓运 |------企切雷传除------|--------的集修汽灯子乱解----|------------|

  27 04 65

  |------------|------------|

  49* 49 97

  |------------|------------|

  二趟结果

  13 04 49* 38 27 49 55 65 97 76

  d=1

  13 04 49* 38 27 4得离帮渐转其议女过愿9 55 65 97 76

  |-革还新效乐振医---|----|----|----|----|----|----|----|----|

  三趟结果

  04 13 27 38 49* 49 55 65 76 97

  算法思想简单描

  在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,

  并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为

  增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除

  多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现

  了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组块丝因治

  记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量

  对它进行,在每组中再进行排序。当增量民着里亚州班减到1时,整个要排序城律源的数被分成

  一组,排序完成。

  下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,

  以后每次减半,直到增量为1。

  希尔排序是不稳定的。

实现方法

功能

  希尔排序

输入内容

  数组名称(也就是数组首地址)、数组中元素个数

代码

  例如对503,17,512,908,170,897,275,653,462,154,509,612,677,765,703,94排序的C语言算法如下:

  void shell_sort(int *x, int n)

  {

  int h, j, k, t;

  for (h=n/2; h>0; h=h/2) /*控制增量*/

  {

  for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/

  {

  t = *(x+j);

  for (k=j-h; (k>=0 && t<*(x+k)); k-=h)

  {

  *(x+k+h) = *(x+k);

  }

  *(x+k+h) = t;

  }

  }

  }

  void main()

  {

  #define MAX 16

  int *p, i, a[MAX= {503,17,512,908,170,897,275,653,462,154,509,612,677,765,703,94}];

  /*录入测试数据*/

  /*

  p = a;

  printf("Input %d number for sorting :\n",MAX);

  for (i=0; i<MAX; i++)

  {

  scanf("%d",p++);

  }

  *可以自己输入数据

  */

  printf("\n");

  //503,17,512,908,170,897,275,653,462,154,509,612,677,765,703,94

  /*测试排序*/

  p = a;

  shell_sort(p,MAX);

  /**/

  for (p=a, i=0; i<MAX; i++)

  {

  printf("%d ",*p++);

  }

  printf("\n");

  system("pause");

  }

  pascal算法程序:

  program xepx;

  const n=7;

  type

  arr=array[1..n] of integer;

  var

  a:arr;

  i,j,t,d:integer;

  bool:boolean;

  begin

  write('input data:');

  for i:=1to n do read(a[i]);

  writeln;

  d:=n;

  while d>1 do

  begin

  d:=d div 2;

  forj:=d+1 ton do

  begin

  t:=a[j];

  i:=j-d;

  while(i>0) and (a[i]>t) do

  begin

  a[i+d]:=a[i];

  i:=i-d;

  end;

  a[i+d]:=t;

  end;

  end;

  write('output data:');

  fori:=1ton dowrite(a:6);

  writeln;

  end.

  C++示例代码:

  template<typename RandomIter, typename Compare>void shell_sort(RandomIter begin, RandomIter end, Compare cmp) { typedef typename std::iterator_traits<RandomIter>::value_type value_type; typedef typename std::iterator_traits<RandomIter>::difference_type diff_t; diff_t size = std::distance(begin, end); diff_t step = size / 2; while(step >= 1) { for(diff_t i=step; i<size; ++i) { value_type key = *(begin+i); diff_t ins = i; while(ins>=step && cmp(key, *(begin+ins-step)) ) { *(begin+ins) = *(begin+ins-step); ins -= step; } *(begin+ins) = key; } if(step == 2) step = 1; else step = static_cast<diff_t>(step / 2.2); } } template<typename RandomIter>void shell_sort(RandomIter begin, RandomIter end) { typedef typename std::iterator_traits<RandomIter>::value_type value_type; shell_sort(begin, end, std::less<value_type>() );}

  Java代码实现:

  //shell排序

  /*

  * 基本思想:将序列分成几类,在类里将它分成几个小组,再让它在小组内进行排序,依次重复直至排序成功

  * 1,找出间距gap(分类)最后间距分类必须为1, 第一重循环

  * 2, 找出各组 ,组间循环,第二重循环

  * 3,找出组内元素,第三重循环,并对转储

  */

  public static int[] ShellInsertSort(int[] data)

  {

  int[] temp=new int[data.length];//存储结果

  for(int gap=data.length/2;gap>=1;gap-- )//gap间距

  {

  System.out.println("gap="+gap);

  int iter=0;//对存储结果的数组进行遍历;

  for(int i=0;i<gap;i++)//i是对提取相同组进行遍历

  {

  boolean IsHead=true;//标明是否是每组的开头

  int groupItemC=0;//用于标明每组所含有的元素

  for(int j=i;j<data.length&&iter<temp.length;j=j+gap,iter++)//转存循环

  if(IsHead) //判断是否是组的开始

  {

  groupItemC=0;

  temp[iter]=data[j];

  IsHead=false;

  groupItemC++;

  }

  else

  {

  for(int groupiter=iter-groupItemC;groupiter<iter;groupiter++)

  {

  if(data[j]<=temp[groupiter])

  {

  for(int tempiter=iter;tempiter>groupiter;tempiter--)

  {

  temp[tempiter]=temp[tempiter-1];

  }

  temp[groupiter]=data[j];

  break;//存完之后跳出循环开始存下一个元素

  }

  if(groupiter==iter-1&&data[j]>temp[groupiter])

  {

  temp[iter]=data[j];

  }

  }

  groupItemC++;

  }

  }

  data=temp;

  for(int x:data)

  {

  System.out.print(x+" ");

  }

  System.out.println();

  temp=new int[data.length];

  }

  return data;

  }

声明:此文信息来源于网络,登载此文只为提供信息参考,并不用于任何商业目的。如有侵权,请及时联系我们:fendou3451@163.com
标签:

  • 关注微信
上一篇:孙颖

相关文章