黑马程序员技术交流社区

标题: 关于BubbleSort和SelectSort的效率问题 [打印本页]

---

作者: love~陌    时间: 2014-6-5 20:07
标题: 关于BubbleSort和SelectSort的效率问题
数组排序到了现在才讲，开课都过了15天了，时间过去一多半了，培训期马上结束了，班里人还没认识几个···

1. package practice;
   
2. 
   
3. public class ArrayDemo {
   
4. 
   
5.         /**
   
6.          * @param args
   
7.          */
   
8.         int [] arr={1,2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,
   
9.                         12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,2,15,
   
10.                         16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,
    
11.                         89,41,2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,
    
12.                         1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,
    
13.                         12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,
    
14.                         5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,
    
15.                         4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,2,15,
    
16.                         16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,2,
    
17.                         15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
18.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
19.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
20.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
21.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
22.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
23.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
24.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
25.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
26.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
27.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
28.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
29.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
30.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
31.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
32.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
33.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
34.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
35.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
36.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
37.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
38.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
39.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
40.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
41.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
42.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
43.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
44.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
45.                         2,15,16,4879,5454,12564,1165,12,89,41,2,15,16,4879,5454,12564,1165,12,89,41,
    
46.                         2,15,16,4879,5454,12564,1165,12,89,41};
    
47.         public static void main(String[] args) {
    
48.                
    
49.                 Time t1=new ArrayDemo().new Time1();
    
50.                 System.out.println(t1.getTime());
    
51.                 Time t2=new ArrayDemo().new Time2();
    
52.                 t2.getTime();
    
53.                 System.out.println(t2.getTime());
    
54.         }
    
55.         class Time1 extends Time{
    
56. 
    
57.                 @Override
    
58.                 public void runCode() {
    
59.                         // TODO Auto-generated method stub
    
60.                         ArrayDemo.selectSort(new ArrayDemo().arr);
    
61.                 }
    
62.                
    
63.         }
    
64.         class Time2 extends Time{
    
65.                
    
66.                 @Override
    
67.                 public void runCode() {
    
68.                         // TODO Auto-generated method stub
    
69.                         ArrayDemo.selectSort(new ArrayDemo().arr);
    
70.                 }
    
71.                
    
72.         }
    
73.        
    
74.         //选择排序
    
75.         public static int[] selectSort(int [] arr){
    
76.                 for (int i = 0; i < arr.length; i++) {
    
77.                         for (int j = 0; j < arr.length; j++) {
    
78.                                 if (arr[i] < arr[j]) {
    
79.                                         swap(arr, j, i);
    
80.                                 }
    
81.                         }
    
82.                 }
    
83.                 return arr;
    
84.         }
    
85.        
    
86.        
    
87.         //冒泡排序
    
88.         public static int[] bubbleSort(int[]arr){
    
89.                 for (int i = 0; i < arr.length; i++) {
    
90.                         for (int j = 0; j < arr.length-i-1; j++) {
    
91.                                 if (arr[j] > arr[j+1]) {
    
92.                                         swap(arr, j, j+1);
    
93.                                 }
    
94.                         }
    
95.                 }
    
96.                 return arr;
    
97.         }
    
98.        
    
99.         //位置互换
    
100.         private static void swap(int[] arr,int m,int n){
     
101.                 if (arr[m] > arr[n]) {
     
102.                         int temp=arr[m];
     
103.                         arr[m]=arr[n];
     
104.                         arr[n]=temp;
     
105.                 }
     
106.         }
     
107. 
     
108. }
     
109. 
     
110. abstract class Time{
     
111.        
     
112.         public  abstract void runCode();
     
113.         public  final long getTime(){
     
114.                 long beginTime=System.currentTimeMillis();
     
115.                 runCode();
     
116.                 return System.currentTimeMillis()-beginTime;
     
117.         }
     
118. }
     

复制代码

这个数组有点牛逼，一顿疯狂复制粘贴，为了区分二者效率，没办法。

哥们复制一下代码。运行一下就知道了。

数组比较大的时候，BubbleSort确实要比SelectSort效率高，比如我现在的是数组，从运行结果就能明显看出来

冒泡和选择的效率问题.png (65.11 KB, 下载次数: 44)

下载附件

2014-6-5 20:07 上传

---

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

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