刚才看数组排序那，老毕说了一句话，我相信很多人都应该没注意，就是效率，怎么减少堆内存中置换次数来提高性能，这句话我没理解什么意思，不过自己想了下，其实有些时候没必要进入循环的，所以我就做了点改动，改完之后发现效率提高到惊人的66%。。。。

我的问题是，这样改动之后提高效率的根源具体在底层内会造成什么效果

这个只能先拿这个数组演示下了，至于乱序数组排序是不正确的，不过这里就是看下是否会有提升效率

下边是代码

1. public class Sort
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                 int[] arr = {8,7,6,5,4,3,2,1};
   
6.                 long taken = System.currentTimeMillis();
   
7.                 for(int i = 0; i < 100000000; i++)
   
8.                 {
   
9.                         arr = new int[]{8,7,6,5,4,3,2,1};
   
10.                         selectSort(arr);
    
11.                 }
    
12.                 taken = System.currentTimeMillis() - taken;
    
13.                 System.out.println("selectSort方法耗时："+taken+" 毫秒");
    
14.                
    
15.                 taken = System.currentTimeMillis();
    
16.                 for(int i = 0; i < 100000000; i++)
    
17.                 {
    
18.                         arr = new int[]{8,7,6,5,4,3,2,1};
    
19.                         selectSort2(arr);
    
20.                 }
    
21.                 taken = System.currentTimeMillis() - taken;
    
22.                 System.out.println("selectSort2方法耗时："+taken+" 毫秒");
    
23.         }
    
24. 
    
25.         public static void selectSort(int[] arr)
    
26.         {
    
27.                 for(int i = 0; i < arr.length - 1; i++)
    
28.                 {
    
29.                         for(int j = i + 1; j < arr.length; j++)
    
30.                         {
    
31.                                 if(arr[i] > arr[j])
    
32.                                 {
    
33.                                         swap(arr, i, j);
    
34.                                 }
    
35.                         }
    
36.                 }
    
37.         }
    
38.        
    
39.         public static void selectSort2(int[] arr)
    
40.         {
    
41.                 for(int i = 0; i < arr.length - 1; i++)
    
42.                 {
    
43.                         for(int j = i + 1; j < arr.length && arr[i] > arr[j]; j++)
    
44.                         {
    
45.                                 swap(arr, i, j);
    
46.                         }
    
47.                 }
    
48.         }
    
49.        
    
50.         public static void swap(int[] arr, int i, int j)
    
51.         {
    
52.                 int temp = arr[i];
    
53.                 arr[i] = arr[j];
    
54.                 arr[j] = temp;
    
55.         }
    
56. }

复制代码

1. selectSort方法耗时：4119 毫秒
   
2. selectSort2方法耗时：2473 毫秒

复制代码

我又想了想，内循环每次都要创建一个j变量，那么果断的把他拿到外循环定义

1. public static void selectSort3(int[] arr)
   
2.         {
   
3.                 for(int i = 0,j = i + 1; i < arr.length - 1; i++)
   
4.                 {
   
5.                         for(j = i + 1; j < arr.length && arr[i] > arr[j]; j++)
   
6.                         {
   
7.                                 swap(arr, i, j);
   
8.                         }
   
9.                 }
   
10.         }

复制代码

这样比原来还能提高3%左右，但是还有个地方可以优化，外循环的j=i+1，实际上只需要执行一次，那么就是常量1

1. public static void selectSort3(int[] arr)
   
2.         {
   
3.                 for(int i = 0,j = 1; i < arr.length - 1; i++)
   
4.                 {
   
5.                         for(j = i + 1; j < arr.length && arr[i] > arr[j]; j++)
   
6.                         {
   
7.                                 swap(arr, i, j);
   
8.                         }
   
9.                 }
   
10.         }

复制代码

但是最后这个改动，在这种亿次级别的情况下也仅是减少几毫秒的时间，不是很明显

简单选择排序的思想是每次选出一个最大（最小）的数据，放在最前（最后）一位，所以一次大循环能确定一位。
小循环就是遍历所有数，找出最大（小）的一个（用冒泡的方法），如果是事先是无序的 arr > arr[j] 不能作为不进入循环的条件
selectSort2没有排完 结果可以看出来
selectSort1：2,3,5,6,6,8,8,11
selectSort2：5,6,6,2,3,8,8,11

想要更高的效率可以考虑换用其他的排序算法

真是高手如云啊。。。 for(int j = i + 1; j < arr.length && arr[i] > arr[j]; j++)
这句话的执行过程，赋值j
如果 j < arr.length && arr[i] > arr[j]不为true则跳出整个循环。。
我想楼主想的是不为true 就执行j++然后再继续这个循环。。这是不对的哦

我测试了一下。。竟然排对了。。。自己都无语。。看来测试用例也是很关键的。。

sort2 结果是不对的啊

罗杰 发表于 2012-3-28 22:52
简单选择排序的思想是每次选出一个最大（最小）的数据，放在最前（最后）一位，所以一次大循环能确定一位。 ...

呵呵，就是这么个想法，其实还是有可能的，至少还是排了后3位出来，还是有地方有问题，我原来用的那个数组是倒叙的54321，跑了一遍没问题，然后改第二个的时候才把数组变成这样的忘记打印了

但是如果是54321这样的数组，还是会发现效率确实高了，但是不能这么连着算时间，每次单独测试一个方法的话，会发现这2种办法确实有效，暂时先不考虑第一种的跳出循环问题，其实如果必定跳出循环的判断，综合进for里边还是会有显著效率提升的，但是应用范围比较小