黑马程序员技术交流社区

标题: 探究5种常见的数据排序效率分析【欢迎指正，补充~~】 [打印本页]
作者: 丁岩    时间: 2012-9-27 17:14
标题: 探究5种常见的数据排序效率分析【欢迎指正，补充~~】
今天下午闲的无聊，突然想起探究学过的排序方法的效率问题（冒泡、Arrays-sort、Collections-sort、选择、插入）我把关于输出的代码用斜杠注释了起来，如果想要获取他排序后的输出结果把注释取消即可，通过调整不同的样本数量，我发现他们的效率时间排名大概相似，下面我以样本数量为30000来展示一下我的运行结果，如果代码有不完善的地方或者还有别的排序方式可以比较的地方，欢迎大家指正，补充！！！
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.Iterator;
  5. import java.util.List;
  6. import java.util.Random;


  9. class ComMe
  10. {
  11. public static void main(String[]args)
  12. {

  14. int length=30000;//设置样本数量
  15. long ch;
  16. Number n=new Number(length);
  17. n.getRandom();
  18. System.out.println("第1种冒泡排序");
  19. comp(n,1,length);
  20. System.out.println("第2种Arrays-sort排序");
  21. comp(n,2,length);
  22. System.out.println("第3种Collections-sort排序");
  23. comp(n,3,length);
  24. System.out.println("第4种选择排序");
  25. comp(n,4,length);
  26. System.out.println("第5种插入排序");
  27. comp(n,5,length);
  28. System.out.println("第1种冒泡排序、第2种Arrays-sort排序、第3种Collections-sort排序、第4种选择排序、第5种插入排序");
  29. System.out.println();
  30. for(int i=1;i<6;i++)
  31. {
  32. System.out.println("第"+i+"种方法花费"+n.len[i]+"毫秒");
  33. }
  34. }

  36. public static void comp(Number n,int c,int l)
  37. {

  39. long start=System.currentTimeMillis();

  41. n.compare(c,l);
  42. System.out.println();
  43. long end=System.currentTimeMillis();
  44. n.setTime(end-start);
  45. if(c==3)
  46. {
  47. System.out.println();
  48. return;
  49. }

  51. /* for(int i=0;i<l;i++)
  52. {
  53. System.out.println(n.n[i]);
  54. }
  55. */



  59. }
  60. }

  62. class Number
  63. {
  64. public Integer[]n;
  65. private int l;
  66. public long[]len;
  67. private int t;
  68. Number(int l)
  69. {
  70. this.l=l;
  71. len=new long[6];
  72. t=1;
  73. }
  74. public void getRandom()//获取随机数
  75. {
  76. n=new Integer[l];
  77. Random r=new Random();
  78. for(int i=0;i<l;i++)
  79. {
  80. n[i]=r.nextInt(10000);

  82. }
  83. }

  85. public void compare(int choice,int l)//排序
  86. {
  87. if(choice==1)//冒泡排序
  88. {
  89. int temp;
  90. for(int i=0;i<l;i++)
  91. {
  92. for(int j=0;j<l-1;j++)
  93. {
  94. if(n[i]<n[j])
  95. {
  96. temp=n[i];
  97. n[i]=n[j];
  98. n[j]=temp;
  99. }
  100. }
  101. }
  102. }
  103. if(choice==2)//Arrays—sort排序
  104. {
  105. Arrays.sort(n);
  106. System.out.println();
  107. }

  109. if(choice==3)//Collections-sort排序
  110. {
  111. List list=new ArrayList();
  112. list=Arrays.asList(n);

  114. Collections.sort(list);
  115. //System.out.println(list.size());
  116. /* Iterator i=list.iterator();
  117. while(i.hasNext())
  118. {
  119. System.out.println(i.next());
  120. }
  121. */
  122. }

  124. if(choice==4)//选择排序
  125. {
  126. for(int i=0;i<n.length;i++)
  127. {
  128. int min=i;
  129. for(int j=i+1;j<n.length;j++)
  130. {
  131. if(min>n[j])
  132. min=n[j];
  133. }
  134. if(min!=i)
  135. {
  136. int temp=n[i];
  137. n[i]=n[min];
  138. n[min]=temp;
  139. }
  140. }

  142. }

  144. if(choice==5)//插入排序
  145. {
  146. for(int i=1;i<n.length;i++)
  147. {
  148. for(int j=i;j>0;j--)
  149. {
  150. if(n[j]<n[j-1])
  151. {
  152. int temp=n[j];
  153. n[j]=n[j-1];
  154. n[j-1]=temp;
  155. }
  156. else
  157. break;
  158. }
  159. }
  160. }


  163. }

  165. public void setTime(long time)
  166. {
  167. len[t]=time;
  168. t++;
  169. }


  172. }
复制代码

1.png (6.95 KB, 下载次数: 25)

Eclipse运行结果

Eclipse运行结果

2.jpg (22.58 KB, 下载次数: 36)

2.jpg
作者: 宫明星    时间: 2012-9-27 17:28
本帖最后由 宫明星 于 2012-9-27 17:45 编辑

很有耐心啊，呵呵。
我来陪楼主，刚刚花了10分钟帮楼主代码排版了一下。
原版太乱了，眼都花了。
在这样看起来就舒服多了。
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.Iterator;
  5. import java.util.List;
  6. import java.util.Random;


  9. class ComMe
  10. {
  11.         public static void main(String[]args)
  12.         {

  14.                 int length=30000;//设置样本数量
  15.                 long ch;
  16.                 Number n=new Number(length);
  17.                 n.getRandom();
  18.                 System.out.println("第1种冒泡排序");
  19.                 comp(n,1,length);
  20.                 System.out.println("第2种Arrays-sort排序");
  21.                 comp(n,2,length);
  22.                 System.out.println("第3种Collections-sort排序");
  23.                 comp(n,3,length);
  24.                 System.out.println("第4种选择排序");
  25.                 comp(n,4,length);
  26.                 System.out.println("第5种插入排序");
  27.                 comp(n,5,length);
  28.                 System.out.println("第1种冒泡排序、第2种Arrays-sort排序、第3种Collections-sort排序、第4种选择排序、第5种插入排序");
  29.                 System.out.println();
  30.                 for(int i=1;i<6;i++)
  31.                 {
  32.                         System.out.println("第"+i+"种方法花费"+n.len[i]+"毫秒");
  33.                 }
  34.         }

  36.         public static void comp(Number n,int c,int l)
  37.         {

  39.                 long start=System.currentTimeMillis();

  41.                 n.compare(c,l);
  42.                 System.out.println();
  43.                 long end=System.currentTimeMillis();
  44.                 n.setTime(end-start);

  46.                 if(c==3)
  47.                 {
  48.                         System.out.println();
  49.                         return;
  50.                 }

  52.                 /* for(int i=0;i<l;i++)
  53.                 {
  54.                         System.out.println(n.n[i]);
  55.                 }
  56.                 */
  57.         }
  58. }

  60. class Number
  61. {
  62.         public Integer[]n;
  63.         private int l;
  64.         public long[]len;
  65.         private int t;

  67.         Number(int l)
  68.         {
  69.                 this.l=l;
  70.                 len=new long[6];
  71.                 t=1;
  72.         }
  73.         public void getRandom()//获取随机数
  74.         {
  75.                 n=new Integer[l];
  76.                 Random r=new Random();

  78.                 for(int i=0;i<l;i++)
  79.                 {
  80.                         n[i]=r.nextInt(10000);
  81.                 }
  82.         }

  84.         public void compare(int choice,int l)//排序
  85.         {
  86.                 if(choice==1)//冒泡排序
  87.                 {
  88.                         int temp;
  89.                         for(int i=0;i<l;i++)
  90.                         {
  91.                                 for(int j=0;j<l-1;j++)
  92.                                 {
  93.                                         if(n[i]<n[j])
  94.                                         {
  95.                                                 temp=n[i];
  96.                                                 n[i]=n[j];
  97.                                                 n[j]=temp;
  98.                                         }
  99.                                 }
  100.                         }
  101.                 }

  103.                 if(choice==2)//Arrays—sort排序
  104.                 {
  105.                         Arrays.sort(n);
  106.                         System.out.println();
  107.                 }

  109.                 if(choice==3)//Collections-sort排序
  110.                 {
  111.                         List list=new ArrayList();
  112.                         list=Arrays.asList(n);

  114.                         Collections.sort(list);
  115.                         //System.out.println(list.size());
  116.                         /* Iterator i=list.iterator();
  117.                         while(i.hasNext())
  118.                         {
  119.                                 System.out.println(i.next());
  120.                         }
  121.                         */
  122.                 }

  124.                 if(choice==4)//选择排序
  125.                 {
  126.                         for(int i=0;i<n.length;i++)
  127.                         {
  128.                                 int min=i;
  129.                                 for(int j=i+1;j<n.length;j++)
  130.                                 {
  131.                                         if(min>n[j])
  132.                                                 min=n[j];
  133.                                 }
  134.                                 if(min!=i)
  135.                                 {
  136.                                         int temp=n[i];
  137.                                         n[i]=n[min];
  138.                                         n[min]=temp;
  139.                                 }
  140.                         }
  141.                 }

  143.                 if(choice==5)//插入排序
  144.                 {
  145.                         for(int i=1;i<n.length;i++)
  146.                         {
  147.                                 for(int j=i;j>0;j--)
  148.                                 {
  149.                                         if(n[j]<n[j-1])
  150.                                         {
  151.                                                 int temp=n[j];
  152.                                                 n[j]=n[j-1];
  153.                                                 n[j-1]=temp;
  154.                                         }
  155.                                         else
  156.                                                 break;
  157.                                 }
  158.                         }
  159.                 }
  160.         }

  162.         public void setTime(long time)
  163.         {
  164.                 len[t]=time;
  165.                 t++;
  166.         }
  167. }
复制代码
作者: 丁岩    时间: 2012-9-27 18:20
宫明星 发表于 2012-9-27 17:28
很有耐心啊，呵呵。
我来陪楼主，刚刚花了10分钟帮楼主代码排版了一下。
原版太乱了，眼都花了。

谢谢你啊。编辑器写的时候排版挺好的，一复制粘贴格式就乱了，刚才走的急没来得及排版
作者: 尤洋    时间: 2012-9-27 18:26
本帖最后由 尤洋 于 2012-9-27 18:56 编辑

弱弱 的问一句
你写的那个 真的是冒泡排序么
if(choice==1)//冒泡排序
{
                 code;
}

}

}


作者: 张文建    时间: 2012-9-27 19:57
87.if(choice==1)//冒泡排序

88.{

89.int temp;

90.for(int i=0;i<l;i++)//楼主这儿是不是有点问题呀？？

91.{

92.for(int j=0;j<l-1;j++)




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