黑马程序员技术交流社区

标题: 这两个排序程序，哪个更快？ [打印本页]

---

作者: librazeng    时间: 2013-5-18 11:40
标题: 这两个排序程序，哪个更快？


排序1：

1. public class FastSort {
   
2. 
   
3.         /**快速排序
   
4.          * @param args
   
5.          */
   
6. 
   
7.         public static void main(String[] args) {
   
8.                 long startTime=System.currentTimeMillis();
   
9.                 int[] arr={43,65,88,63,44,2,8,56,4,66,300,299,298,297,296,295,294,293,292,291,290,289,
   
10.                                 288,287,286,285,284,283,282,281,280,279,278,277,276,275,274,273,272,271,270,269,268,267,266,265,264,263,262,261,260,
    
11.                                 259,258,257,256,255,254,253,252,251,250,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,
    
12.                                 519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,
    
13.                                 548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,
    
14.                                 577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,
    
15.                                 606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,
    
16.                                 635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,
    
17.                                 664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,
    
18.                                 693,694,695,696,697,698,699};
    
19.                 fastSort(arr);
    
20.                 for(int i=0;i<arr.length;i++){
    
21.                         if(i!=arr.length-1)
    
22.                         System.out.print(arr[i]+" ");
    
23.                         else
    
24.                                 System.out.println(arr[i]);
    
25.                 }
    
26.                 long endTime=System.currentTimeMillis();
    
27.                 System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
    
28.         }
    
29. 
    
30.         private static void fastSort(int[] arr) {
    
31.                 for(int x=0;x<arr.length-1;x++){
    
32.                         int min=arr[x];
    
33.                         int Index=x;
    
34.                         for(int y=x+1;y<arr.length;y++){
    
35.                                         if(min>arr[y]){
    
36.                                                 min=arr[y];
    
37.                                                 Index=y;
    
38.                                         }
    
39.                         }
    
40.                         int temp=arr[x];
    
41.                         arr[x]=min;//
    
42.                         arr[Index]=temp;//注意，这里不能写成min=temp,因为这是给min赋值，并没有给数组里的arr[Index]赋值。
    
43.                 }
    
44.         }
    
45. }

复制代码

排序2

1. public class QuickSort {
   
2.         //给一个数组，快速排序
   
3.         //思路：1.将数组任意一个元素作为中间值，比它大的放在右边，比他小的放在左边，获取拍好后的中间值角标
   
4.         //2.将左边和右边都看成新的数组，重新执行步骤1，递归的排列。
   
5.         public static void main(String[] args){
   
6.         long startTime=System.currentTimeMillis();
   
7.         int[] arr={43,65,88,63,44,2,8,56,4,66,300,299,298,297,296,295,294,293,292,291,290,289,
   
8.                         288,287,286,285,284,283,282,281,280,279,278,277,276,275,274,273,272,271,270,269,268,267,266,265,264,263,262,261,260,
   
9.                         259,258,257,256,255,254,253,252,251,250,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,
   
10.                         519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,
    
11.                         548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,
    
12.                         577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,
    
13.                         606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,
    
14.                         635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,
    
15.                         664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,
    
16.                         693,694,695,696,697,698,699};
    
17.         quickSort(arr);
    
18.         for(int x=0;x<arr.length;x++){
    
19.                 if(x!=arr.length-1)
    
20.                 System.out.print(arr[x]+" ");
    
21.                 else
    
22.                         System.out.println(arr[x]);
    
23.                 }
    
24.                 //for(int num:arr){
    
25.                         //System.out.print(num);
    
26.         //        }
    
27.         long endTime=System.currentTimeMillis();
    
28.         System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
    
29.         }
    
30.         private static void quickSort(int[] arr) {
    
31.                 quickSort2(arr,0,arr.length-1);
    
32.         }
    
33.         private static void quickSort2(int[] arr,int low,int high) {
    
34.                 if(low<high){//获取排序一次后中间值的角标
    
35.                         int Index=getMiddleIndex(arr,low,high);
    
36.                         //将左边的数组排序;
    
37.                         quickSort2(arr,low,Index-1);
    
38.                         quickSort2(arr,Index+1,high);
    
39.                 }
    
40.         }
    
41. 
    
42.         private static int getMiddleIndex(int[] arr, int low,int high) {
    
43.                 //
    
44.                 int key=arr[low];
    
45.                 //int low=0;
    
46.                 //int high=arr.length-1;
    
47.                 while(low<high){
    
48.                         while(key<arr[high]&&low<high){
    
49.                                 high--;
    
50.                         }
    
51.                         arr[low]=arr[high];//比他小的，放左边
    
52.                         while(key>arr[low]&&low<high){
    
53.                                 low++;
    
54.                         }
    
55.                         arr[high]=arr[low];//比他大的放右边
    
56.                 }//跳出循环时low=high
    
57.                 arr[high]=key;
    
58.                 return high;
    
59.         }

复制代码

我的机器跑出来的结果，差不多，或者差异很大，请能帮我验证一下啊，你可以自己设置数组。

---

作者: 神之梦    时间: 2013-5-18 11:47
以前用汇编的时候是可以看运行需要的时间的，不知道java中有没有

---

作者: 曾大鹏    时间: 2013-5-18 11:55
快速排序效率快多了。。 时间是O(logn*n)
选择排序的时间是O(n*n)
以前搞acm的时候，弄过的

---

作者: 殇_心。    时间: 2013-5-18 12:22
楼主  这是因为你数据少了。。  
而你电脑cpu又那么强悍。  所以时间是差不了多少的
时间复杂度楼上的也说了。 第二个是要快的

---

作者: 殇_心。    时间: 2013-5-18 12:23

曾大鹏 发表于 2013-5-18 11:55
快速排序效率快多了。。 时间是O(logn*n)
选择排序的时间是O(n*n)
以前搞acm的时候，弄过的  ...

误入歧途啊！！！~ 有木有

---

作者: 曾大鹏    时间: 2013-5-18 12:49

殇_心。 发表于 2013-5-18 12:23
误入歧途啊！！！~ 有木有

其实还好了 搞了两年半的acm 拿了两个奖 挺不错了的。。

---

作者: 袁梦希    时间: 2013-5-18 12:53
如果问题已经解决了，那么大家请把帖子的类型改为“已解决”，在自己帖子的左下角点编辑，然后选择帖子的分类进行改正。{:soso_e163:}

---

作者: 殇_心。    时间: 2013-5-18 12:59

曾大鹏 发表于 2013-5-18 12:49
其实还好了 搞了两年半的acm 拿了两个奖 挺不错了的。。

拿区域赛金奖了么？
好可怜的我啊！！！！

---

作者: joker_chan    时间: 2013-5-18 13:22
快速排序当然更快咯

---

作者: 无妄无涯    时间: 2013-5-18 15:11
一般情况下都应该认为第二个快速排序是比第一个选择排序更优的。选择排序的最优时间复杂度是O(n*n)，快速排序只在最差时间复杂度时才是O(n*n)，最佳时间复杂度是O(nlogn)，平均时间复杂度也是O(nlogn)。楼主的数据样本不够庞大，自然很难看出效率差，此外推荐你使用System.nanoTime()，即获取毫微秒（纳秒）级的时间数据来比较，相对来说区别更明显些。

---

作者: librazeng    时间: 2013-5-18 18:20
谢谢大家的回答！{:soso_e179:}

---

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

黑马程序员IT技术论坛 X3.2