当前位置:天才代写 > tutorial > JAVA 教程 > java中实现希尔排序算法

java中实现希尔排序算法

2017-11-13 08:00 星期一 所属: JAVA 教程 浏览:490

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]–;
 

}
 

}
 

}
 

}

 

    关键字:

[contact-form-7 id="17097" title="form2"]天才代写-代写联系方式