当前位置:七道奇文章资讯编程技术Java编程
日期:2011-03-22 16:16:00  来源:本站整理

java中实现希尔排序算法[Java编程]

赞助商链接



  本文“java中实现希尔排序算法[Java编程]”是由七道奇为您精心收集,来源于网络转载,文章版权归文章作者所有,本站不对其观点以及内容做任何评价,请读者自行判断,以下是其具体内容:

package Utils.Sort;

/**
 

*希尔排序,要求待排序的数组必须实现Comparable接口
 

*/
 

public class ShellSort implements SortStrategy
 

{
 

private int[] increment;

/**
 

*操纵希尔排序算法对数组obj举行排序
 

*/
 

public void sort(Comparable[] obj)
 

{
 

if (obj == null)
 

{
 

throw new NullPointerException("The argument can not be null!");
 

}
 

//初始化步长
 

initGap(obj);
 

//步长顺次改变(递减)
 

for (int i = increment.length - 1 ;i >= 0 ;i-- )
 

{
 

int step = increment[i];
 

//由步长位置开始
 

for (int j = step ;j < obj.length ;j++ )
 

{
 

Comparable tmp;
 

//假如背面的小于前面的(相隔step),则与前面的交换
 

for (int m = j ;m >= step ;m = m - step )
 

{
 

if (obj[m].compareTo(obj[m - step]) < 0)
 

{
 

tmp = obj[m - step];
 

obj[m - step] = obj[m];
 

obj[m] = tmp;
 

}

//因为之前的位置一定已经对比过,所以这里直接退出循环
 

else
 

{
 

break;
 

}
 

}
 

}
 

}
 

}
 

/**
 

*按照数组的长度肯定求增量的公式的最大指数,公式为pow(4, i) - 3 * pow(2, i) + 1和9 * pow(4, i) - 9 * pow
 

2, i) + 1
 

*@return int[] 两个公式的最大指数
 

*@param length 数组的长度
 

*/
 

private int[] initExponent(int length)
 

{
 

int[] exp = new int[2];
 

exp[0] = 1;
 

exp[1] = -1;
 

int[] gap = new int[2];
 

gap[0] = gap[1] = 0;
 

//肯定两个公式的最大指数
 

while (gap[0] < length)
 

{
 

exp[0]++;
 

gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);
 

}
 

exp[0]--;
 

while (gap[1] < length)
 

{
 

exp[1]++;
 

gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);
 

}
 

exp[1]--;
 

return exp;
 

}

private void initGap(Comparable[] obj)
 

{
 

//操纵公式初始化增量序列
 

int exp[] = initExponent(obj.length);
 

int[] gap = new int[2];
 

increment = new int[exp[0] + exp[1]];
 

//将增量数组由大到小赋值
 

for (int i = exp[0] + exp[1] - 1 ;i >= 0 ;i-- )
 

{
 

gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);
 

gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);
 

//将大的增量先放入增量数组,这里实际上是一个归并排序
 

//不需求考虑gap[0] == gap[1]的情形,因为不大概呈现相等.
 

if (gap[0] > gap[1])
 

{
 

increment[i] = gap[0];
 

exp[0]--;
 

}
 

else
 

{
 

increment[i] = gap[1];
 

exp[1]--;
 

}
 

}
 

}
 

}


  以上是“java中实现希尔排序算法[Java编程]”的内容,如果你对以上该文章内容感兴趣,你可以看看七道奇为您推荐以下文章:
  • 利用Javascript实现网页水印(非图片水印)
  • Java开辟环境的搭建
  • Ubuntu java安装与配置
  • 办理Ubuntu 10.04 Firefox3.6 Java浏览器插件不工作的问
  • Ubuntu重装后Java环境的设置
  • Sun Java进入Ubuntu 10.10软件中央
  • Ubuntu 10.10配置Java开辟环境
  • 在Ubuntu 10.10中配置Java环境变量的办法
  • Ubuntu下Java环境的搭建
  • Ubuntu 10.04 下安装 Java, JRE
  • Ubuntu 10.04下的搭建SUN JAVA开辟环境
  • Ubuntu 12.04安装java7
  • 本文地址: 与您的QQ/BBS好友分享!
    • 好的评价 如果您觉得此文章好,就请您
        0%(0)
    • 差的评价 如果您觉得此文章差,就请您
        0%(0)

    文章评论评论内容只代表网友观点,与本站立场无关!

       评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论
    Copyright © 2020-2022 www.xiamiku.com. All Rights Reserved .