黑马程序员技术交流社区

标题: 排序算法时间复杂度的计算 [打印本页]
作者: Super_Class    时间: 2013-5-8 23:54
标题: 排序算法时间复杂度的计算
本帖最后由 Super_Class 于 2013-5-9 14:57 编辑

最快的是希尔算法，求详细代码。附注释最好
作者: Jacky_Chen1990    时间: 2013-5-8 23:59
本帖最后由 Jacky_Chen1990 于 2013-5-9 00:00 编辑

占楼。编辑代码中。。
  1. public class Sort {

  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);

  47.         }

  49. }
复制代码
欢迎指教。
作者: Jacky_Chen1990    时间: 2013-5-9 00:03
复杂度的计算好像有很多种说法。这个要深究数据库。。我回去研究下。。再来。。
作者: Jacky_Chen1990    时间: 2013-5-9 00:03
尹桥印 发表于 2013-5-9 00:03
嘿嘿，我现在处于断网之中，用手机连的~网速不行，~~就让你沙发呐~~嘿嘿

我前面也是哦。。。
作者: Jacky_Chen1990    时间: 2013-5-9 00:07
尹桥印 发表于 2013-5-9 00:06
加油加油。努力学知识。

恩啦。加油~~你准备进第几期？
作者: Jacky_Chen1990    时间: 2013-5-9 00:11
尹桥印 发表于 2013-5-9 00:09
我早呢，非常早。

点点点。
作者: 潘贵    时间: 2013-5-9 00:20
研究研究
作者: long    时间: 2013-5-9 01:05
/**希尔排序是基于插入排序的一种算法，时间复杂度为 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]--;
                     }
              }            
       }
}

作者: Chelsea_Lampard    时间: 2013-5-9 10:26
排序的平均时间：快速排序、希尔排序、归并排序、堆排序都为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;

  3. public class ShellSortTest {
  4. public static int count = 0;

  6. public static void main(String[] args) {

  8. int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; //定义数组
  9. print(data); //打印排序前的数组元素
  10. shellSort(data); //希尔排序
  11. print(data); //打印排序后的数组元素

  13. }

  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. }

  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. }

  46. }
复制代码
作者: Chelsea_Lampard    时间: 2013-5-9 10:28
运行结果：
  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  
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2