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)  


{