最快的是希尔算法，求详细代码。附注释最好

占楼。编辑代码中。。

1. public class Sort {
   
2. 
   
3.         /**
   
4.          * 希尔排序也是一种插入排序方法，实际上是一种分组插入方法
   
5.          * 先取一个小于n的整数d1作为一个增量，把表的全部记录分成d1个组，所有
   
6.          * 距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序，然后
   
7.          * ，取第二个增量d2(<d1),重复上述的分组和排序，直至所取的dt=1,即所有
   
8.          * 记录放在同一组中进行直接插入排序为止
   
9.          */
   
10.         public static int[] shellSort(int []R){
    
11.                
    
12.                 int gap = R.length/2;
    
13.                 int temp;
    
14.                 while(gap>0){
    
15.                         for(int i=gap;i<R.length;i++){
    
16.                                 temp = R[i];
    
17.                                 int j = i - gap;
    
18.                                 while(j>=0 && temp < R[j]){
    
19.                                         R[j+gap] = R[j];
    
20.                                         j = j - gap;
    
21.                                 }
    
22.                                 R[j+gap] = temp;
    
23.                         }
    
24.                         gap = gap/2;
    
25.                 }
    
26.                 return R;
    
27.         }
    
28.        
    
29.         public static void display(int[] R){
    
30.                 System.out.println();
    
31.                 for(int i=0;i<R.length;i++){
    
32.                         System.out.print(R[i]+" ");
    
33.                 }
    
34.         }
    
35.        
    
36.         public static void main(String[] args) {
    
37.                
    
38.                 final int M = 50;//定义数组大小为50
    
39.                 int []R = new int[M];
    
40.                 for(int i=0;i<M;i++){
    
41.                         R[i] = new Random().nextInt(100);//生成100以内的随机数
    
42.                 }
    
43.                 display(R);
    
44.                 R = shellSort(R);
    
45.                 display(R);
    
46. 
    
47.         }
    
48. 
    
49. }
    

复制代码

欢迎指教。

复杂度的计算好像有很多种说法。这个要深究数据库。。我回去研究下。。再来。。

尹桥印 发表于 2013-5-9 00:03
嘿嘿，我现在处于断网之中，用手机连的~网速不行，~~就让你沙发呐~~嘿嘿

我前面也是哦。。。

尹桥印 发表于 2013-5-9 00:06
加油加油。努力学知识。

恩啦。加油~~你准备进第几期？

尹桥印 发表于 2013-5-9 00:09
我早呢，非常早。

点点点。

研究研究

/**希尔排序是基于插入排序的一种算法，时间复杂度为 O(N*(logN)2)。
*下面的希尔排序要求待排序的数组必须实现Comparable接口
*/
public class ShellSort
{
       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;                    
                     //由步长位置开始

                     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 = gap[0];
                            exp[0]--;
                     }
                     else
                     {
                            increment = gap[1];
                            exp[1]--;
                     }
              }            
       }
}

排序的平均时间：快速排序、希尔排序、归并排序、堆排序都为O(N*(logN)2).其他的都是O(n^2),一个特殊的是基数排序，为O(d(n+R)).
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。[1]
比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比[1]较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
给定实例的shell排序的排序过程
假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：
5，2，1
希尔排序是最快的之一，算法并不稳定。

1. package sort;
   
2. 
   
3. public class ShellSortTest {
   
4. public static int count = 0;
   
5. 
   
6. public static void main(String[] args) {
   
7. 
   
8. int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; //定义数组
   
9. print(data); //打印排序前的数组元素
   
10. shellSort(data); //希尔排序
    
11. print(data); //打印排序后的数组元素
    
12. 
    
13. }
    
14. 
    
15. public static void shellSort(int[] data) {
    
16. // 计算出最大的h值
    
17. int h = 1;
    
18. while (h <= data.length / 3) {
    
19. h = h * 3 + 1;
    
20. }
    
21. while (h > 0) {
    
22. for (int i = h; i < data.length; i += h) {
    
23. if (data[i] < data[i - h]) {
    
24. int tmp = data[i];
    
25. int j = i - h;
    
26. while (j >= 0 && data[j] > tmp) {
    
27. data[j + h] = data[j];
    
28. j -= h;
    
29. }
    
30. data[j + h] = tmp;
    
31. print(data);
    
32. }
    
33. }
    
34. // 计算出下一个h值
    
35. h = (h - 1) / 3;
    
36. }
    
37. }
    
38. 
    
39. public static void print(int[] data) {
    
40. for (int i = 0; i < data.length; i++) {
    
41. System.out.print(data[i] + "\t");
    
42. }
    
43. System.out.println();
    
44. }
    
45. 
    
46. }
    

复制代码

运行结果：

1. 5   3   6   2   1   9   4   8   7     
   
2. 1   3   6   2   5   9   4   8   7     
   
3. 1   2   3   6   5   9   4   8   7     
   
4. 1   2   3   5   6   9   4   8   7     
   
5. 1   2   3   4   5   6   9   8   7     
   
6. 1   2   3   4   5   6   8   9   7     
   
7. 1   2   3   4   5   6   7   8   9     
   
8. 1   2   3   4   5   6   7   8   9  
   

复制代码