黑马程序员技术交流社区

标题: 【优化】同样的选择排序，为什么效率可以提高到原来的160%+ [打印本页]
作者: 刘蕴学    时间: 2012-3-28 21:25
标题: 【优化】同样的选择排序，为什么效率可以提高到原来的160%+
本帖最后由 了无尘 于 2012-3-29 00:11 编辑

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

  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.         }
复制代码
但是最后这个改动，在这种亿次级别的情况下也仅是减少几毫秒的时间，不是很明显
作者: 罗杰    时间: 2012-3-28 22:52
本帖最后由 罗杰 于 2012-3-28 22:54 编辑

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

想要更高的效率可以考虑换用其他的排序算法
作者: 孙雪娇    时间: 2012-3-28 23:08
真是高手如云啊。。。 for(int j = i + 1; j < arr.length && arr[i] > arr[j]; j++)
这句话的执行过程，赋值j
如果 j < arr.length && arr[i] > arr[j]不为true则跳出整个循环。。
我想楼主想的是不为true 就执行j++然后再继续这个循环。。这是不对的哦

我测试了一下。。竟然排对了。。。自己都无语。。看来测试用例也是很关键的。。
作者: 葛尧    时间: 2012-3-28 23:30
sort2 结果是不对的啊
作者: 刘蕴学    时间: 2012-3-28 23:57
本帖最后由 了无尘 于 2012-3-29 00:12 编辑
罗杰 发表于 2012-3-28 22:52
简单选择排序的思想是每次选出一个最大（最小）的数据，放在最前（最后）一位，所以一次大循环能确定一位。 ...


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

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



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