科技行者

行者学院 转型私董会 科技行者专题报道 网红大战科技行者

知识库

知识库 安全导航

至顶网软件频道JAVA基础应用: 如何实现希尔排序算法

JAVA基础应用: 如何实现希尔排序算法

  • 扫一扫
    分享文章到微信

  • 扫一扫
    关注官方公众号
    至顶头条

JAVA基础应用: 如何实现希尔排序算法

作者:cyber3 来源:赛迪网技术社区 2007年11月18日

关键字: 希尔排序 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]--;

}

}

}

}

查看本文来源
    • 评论
    • 分享微博
    • 分享邮件
    邮件订阅

    如果您非常迫切的想了解IT领域最新产品与技术信息,那么订阅至顶网技术邮件将是您的最佳途径之一。

    重磅专题
    往期文章
    最新文章