一聚教程网:一个值得你收藏的教程网站

热门教程

java 算法之希尔排序详解及实现代码

时间:2022-06-29 01:34:34 编辑:袖梨 来源:一聚教程网

java 算法之希尔排序

一、思想

希尔排序:使数组中任意间隔为h的元素都是有序的。在进行排序的时候,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便。用这种方式,对任意以1结尾的h序列,我们都能够将数据排序; 

 二、概念

h有序数组:任意间隔为h的元素都是有序的数组; 

三、高效原因

对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一段;

  希尔排序更高效的原因:它权衡了子数组的规模和有序性,在排序之初,各个子数组都很短;在排序之后子数组都是部分有序的,这两种情况很适合插入排序;  

四、代码

 

 代码如下复制代码

/**

 * 希尔排序

 * 

 * @author pengcx

 * 

 */ 

publicclassShellextendsSort { 

  publicstaticvoidmain(String[] args) { 

    String[] a = {"d","a","w","b","q"}; 

    Shell.sort(a); 

    show(a); 

  } 

   

  /**

  * 排序数组a

  * 

  * @param a

  *      排序的数组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; 

    } 

  } 

}

 

热门栏目