Java算法排序之--希尔排序法

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

先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止初始：d=549 38 65 97 76 13 27 49* 55 0449 13|-------------------|38 27|-------------------|65 49*|-------------------|97 55|-------------------|76 04|-------------------|一趟结果13 27 49* 55 04 49 38 65 97 76d=313 27 49* 55 04 49 38 65 97 7613 55 38 76|------------|------------|------------|27 04 65|------------|------------|49* 49 97|------------|------------|二趟结果13 04 49* 38 27 49 55 65 97 76d=113 04 49* 38 27 49 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 16int *p, i, a[MAX];/*录入测试数据*//*p = a;printf("Input %d number for sorting :\n",MAX);for (i=0; i<MAX; i++){scanf("%d",p++);}*可以自己输入数据*/a[] = {503,17,512,908,170,897,275,653,462，154，509，612，677，765，703，94};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;beginwrite('input data:');for i:=1to n do read(a[i]);writeln;d:=n;while d>1 do begind:=d div 2;forj:=d+1 ton do begint:=a[j];i:=j-d;while(i>0) and (a[i]>t) do begina[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; }