跪求一个希尔排序的算法

Question

请各位大哥大姐帮忙

Answer 1

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

Answer 2

希 尔 排 序基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般采用：ht=2t-1,1≤t≤[log2n]，其中n为待排序序列的长度。
 
    C函数如下：  void prshl(p,n)
 
  int n;double p[];
 
  {
 
   int k,j,i;
 
   double t;
 
   k=n/2;
 
   while(k>0)
 
   {
 
    for(j=k;j<=n-1;j++)
 
    {
 
      t=p[j];i=j-k;
 
      while((i>=0)&&(p[i]>t))
 
        {
 
         p[i+k]=p[i];i=i-k;
 
         }
 
       p[i+k]=t;
 
      }
 
      k=k/2;
 
     }
 
   return;
 
  }
 
 

Answer 3

public void shellSort{ 
int inner, outer; 
long temp; 
int h = 1; 
while(h <= nElems/3) 
h = h*3 + 1; 
while(h > 0){ 
for(outer = h; outer < nElems; outer++){ 
temp = theArray[outer]; 
inner = outer; 
while(inner > h - 1 && theArray[inner - h] >= temp){ 
theArray[inner] = theArray[inner - h]; 
inner -= h; 
} 
theArray[inner] = temp; 
} 
h = (h - 1)/3; 
} 
}

Answer 4

上面的代码复制时候有问题
给你看个链接
http://hi.baidu.com/comasp/blog/item/5846a90125804b01738da5bc.html