黑马程序员技术交流社区

标题: 冒泡排序 ?有点小模糊 求助 [打印本页]
作者: 荣天    时间: 2012-5-14 16:45
标题: 冒泡排序 ?有点小模糊 求助
//冒泡排序
        public static void bubblesort(int[] arr){
                for(int x=0;x<arr.length-1;x++){
                        for(int y=0;y<arr.length-x-1;y++){ //-x:让每一次比较元素减1    -1：避免数组越界
                                if( arr[y]<arr[y+1]){
                                         /*
                                        int tmp=arr[y];
                                        arr[y]=arr[y+1];
                                        arr[y+1]=tmp;
                                        */
                                        swap(arr,y,y+1);
                                }
                        }
                }
               
        }

//y<arr.length-x-1   怎么解释呢  有点晕    求大家帮助下  谢谢
作者: 赵方明    时间: 2012-5-14 17:02
老师举的例子是用冒泡法使数组从小到大排列。arr.length表示的是数组元素的个数，对于7个数，它只需要比较6次，所以要用arr.length-1

第一次比较完以后，最后的数就是最大的了，那么第二次比较的时候就没有必要把它再进行比较，依此类推，所以在第二次比较时要-1，第三次比较时要-2,因此用到了-x

这个减x就表示最后x个数，已经是从小到大排列，那么这x个数就不必再和前面的数进行比较。
作者: 　夜风    时间: 2012-5-14 17:28
内循环控制次数，图中相邻的2个元素比较，外循环循环一次内循环参与比较的元素就在逐级减少，所以用-x.
int tmp=arr[y];
arr[y]=arr[y+1];
arr[y+1]=tmp;
如果5个数，最大角标是[4]，[Y]取到3，[y+1]就是[4]，如果不-1[y+1]就会取到[5]角标就越界了。

QQ截图20120514171231.png (13.12 KB, 下载次数: 20)

QQ截图20120514171231.png
作者: 小小企鹅    时间: 2012-5-14 18:07
if (arr[y] < arr[y + 1]) 中要调用arr的第y+1个元素，因此y<arr.length-x-1中arr.length-1是为了避免数据越界，
x每次循环都+1，-x让每次循环比较元素个数-1，就实现了冒泡排序
作者: 梁小波    时间: 2012-5-14 18:24
根据你的冒泡算法，。根据arr[y]<arr[y+1],是从大到小排列.所以当x=0的时候y从0到arr.length-1循环的时候，会把最小值放数组到最后，所以第二次，只要比较前arr.length-x-1即可。所以会是y<arr.length-x-1,你只要明白冒泡的思想，就明白了这个道理。我觉得这问题对楼主来说不是很难吧！
作者: 杨康    时间: 2012-5-14 19:27
这样解释下 看我说的你能听懂不 根据毕老师讲的 x美循环一次，每次到内循环都减少一次比较，也就是当x=0时，内循环每个都比较。当x=1时，内循环减少一次比较。依次推出y取值范围为 y<arr.length-x 。不管你内循环里给y怎样变量，y+1也好，y+2也好，y总是要满足他所处的循环体的条件，也就是
y<arr.length
y+1<arr.length
这两个不等式求交集，就得到y的取值范围了。
不知道我说的对不对，我自己的想法而已。说错了请谅解啊。
作者: 康大玮    时间: 2012-5-14 21:14
我感觉你并没有真的理解冒泡排序：
我是这么想的：
冒泡排序外层是趟数，内层是相邻两个数比较的次数。
给你画图看看明白不

2.png (158.67 KB, 下载次数: 25)

2.png

1.png (130.99 KB, 下载次数: 20)

1.png
作者: 荣天    时间: 2012-5-14 21:21
谢谢了{:soso_e100:}



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