希尔排序

实现排序算法——希尔排序12345678910115284961103117希尔排序3528428549611010196311771132134611958710第一趟排序的结果：希尔排序421346119587101234567891011以间隔d=3取元素分组，对各组排序：以间隔d=2取元素分组：第一组：23651110第二组：14798Next…希尔排序52356101114789对各组排序：2134576811910希尔排序62134576811910以间隔d=1取元素，进行终极排序！=直接插入排序……1234567891011希尔排序方法总结：☆以d=3取元素分成三组，对各小组进行直接插入排序；☆三合一，第一趟完成☆以d=2取元素分成两组，对各小组进行直接插入排序☆二合一，第二趟完成☆以d=1取元素分组,完成程序实现（一）：usingSystem;namespaceforpractice{classProgram{publicstaticvoidShellSort(int[]R,intd1,intd2,intd3){intd,i,j,temp;int[]increment={d1,d2,d3};for(intm=0;mincrement.Length;m++){d=increment[m];for(i=d;iR.Length;i++){if(R[i]=R[i-d]){temp=R[i];j=i-d;do{R[j+d]=R[j];j=j-d;}while(j=0&&temp=R[j]);R[j+d]=temp;}}}foreach(inteleminR)Console.Write(elem+);}程序实现（一）：staticvoidMain(string[]args){while(true){Console.WriteLine(Entertheincrementarray:);intd1=int.Parse(Console.ReadLine());intd2=int.Parse(Console.ReadLine());intd3=int.Parse(Console.ReadLine());int[]R={5,9,3,2,6,11,8,1,7,4,10};Console.WriteLine(“排序结果:);Program.ShellSort(R,d1,d2,d3);Console.WriteLine(\n\n);}}}}程序实现（一）：☆增量序列尚未有一种固定的取法，本例中的增量3,2,1也不是唯一的。增量序列的选取原则：☆应使增量序列中的值没有除1之外的公因子，即避免相互形成倍数关系,如8，4，2。☆最后一个增量值必须等于1。21,......15,7,3,1k31,......13,4,12k程序实现（二）：publicclassProgram{publicstaticvoidShellSort(int[]myarray){intd;for(d=1;d=myarray.Length/9;d=3*d+1);Console.WriteLine(d);for(;d0;d/=3){for(inti=d+1;i=myarray.Length;i+=d){intt=myarray[i-1];intj=i;while((jd)&&(myarray[j-d-1]t)){myarray[j-1]=myarray[j-d-1];j-=d;}myarray[j-1]=t;}}}publicstaticvoidMain(){int[]myarrary=newint[]{5,9,3,2,6,11,8,1,7,4,10};Program.ShellSort(myarrary);foreach(intresultinmyarrary)Console.Write(result+);Console.ReadKey();}}程序实现（二）：评价：随d的不同而不同。1971年JamesPeterson和DavidL.Russell在大量实验的基础上推导出希尔排序的时间复杂度为O(n1.3)，另一种说法O(n1.25-1.6n1.25).时间复杂度：正确性：依赖于直接插入排序。