java 算法之希尔排序详解及实现代码
java算法之希尔排序
一、思想
希尔排序:使数组中任意间隔为h的元素都是有序的。在进行排序的时候,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便。用这种方式,对任意以1结尾的h序列,我们都能够将数据排序;
二、概念
h有序数组:任意间隔为h的元素都是有序的数组;
三、高效原因
对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一段;
希尔排序更高效的原因:它权衡了子数组的规模和有序性,在排序之初,各个子数组都很短;在排序之后子数组都是部分有序的,这两种情况很适合插入排序;
四、代码
/** *希尔排序 * *@authorpengcx * */ publicclassShellextendsSort{ publicstaticvoidmain(String[]args){ String[]a={"d","a","w","b","q"}; Shell.sort(a); show(a); } /** *排序数组a * *@parama *排序的数组a */ protectedstaticvoidsort(Comparable[]a){ intN=a.length; inth=1; while(h<N/3){ h=3*h+1; } while(h>=1){ for(inti=0;i<N;i++){ for(intj=i;j>=h&&less(a[j],a[j-h]);j-=h){ exch(a,j,j-h); } } h=h/3; } } }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!