希尔排序算法的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]--;  
  
} } } }