黑马程序员技术交流社区

标题: 关于冒泡排序优化的问题 [打印本页]
作者: 刚金波    时间: 2013-4-15 15:47
标题: 关于冒泡排序优化的问题
本帖最后由 刚金波 于 2013-4-17 00:03 编辑

      刚看视频时讲冒泡排序的优化问题，原本冒泡排序是将存放在堆内存中的数组元素的位置进行调换来完成排序，老师说堆内存中数据的调换会使用较多的资源，如果每次只在最后将这次排序的最大值取出与数组最后一位的值交换位置就可以优化冒泡排序。这块听着有些迷糊，哪位同学能帮忙给详细解释下
  1. public static void bubbleSort_1(int[]arr)
  2.         {
  3.                 int temp=arr.length;
  4.                 for(int x=0;x<temp;x++)
  5.                 {
  6.                         for(int y=x;y<temp-1;y++)
  7.                         {
  8.                                 if(arr[y]>arr[y+1])
  9.                                 {
  10.                                         int num=arr[temp-y];
  11.                                         arr[temp-y]=arr[y];
  12.                                         arr[y]=arr[temp-y];
  13.                                 }
  14.                         }
  15.                 }
  16.                 printArr(arr);
  17.         }
复制代码
上面是我自己写的优化后的冒泡排序的实现代码。
我是这么想的，每次外部循环一次，内部循环就就从数组中获取一个最大值并与数组最后一位交换位置，从而避免相邻两个数组之间的调换。
不知道这样做对不对，哪位给看看，给个意见
作者: 、__WSD吴少东    时间: 2013-4-15 16:05
大概意思就是说，定义一个临时容器，把比较后的最大值赋给该容器，然后第一轮比较后把这个容器的值赋给最后一个，依次类推。这样减少了数组内部对换次数。
大概意思就是这个样子了，
作者: 沈浩    时间: 2013-4-15 18:00
本帖最后由 沈浩 于 2013-4-15 18:11 编辑

你的思路是没错的
不过你的那个代码不行 还是一样每次都在换位置啊
我写的这个貌似可以   你可以参考哈   仅供参考哦
        public static void bubbleSort(int [] arr)
        {
                int tt=0;
                int num=0;
                for (int x=0;x<arr.length-1 ;x++ )
                {
                        for (int y=0;y<arr.length-1-x ;y++ )
                        {
                                //进行判断把最大的那个数的角标记住
                                if(arr[y]>arr[y+1]& arr[tt]<=arr[y])
                                {
                                        tt=y;                                                
                                }
                                else if(arr[y]<arr[y+1]& arr[tt]<=arr[y+1])
                                {
                                                tt=y+1;                                
                                }        
                        }
                        //判断完后才进行换位
                        num = arr[arr.length-x-1];
                        arr[arr.length-x-1]=arr[tt];
                        arr[tt]=num;
                        tt=0;
                }
        }



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