黑马程序员技术交流社区

标题: 冒泡排序 [打印本页]

作者: 张聪珉 时间: 2013-8-9 19:17
标题: 冒泡排序

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++)//这里为什么arr.length-x之后还要再减去1啊，脑袋转不过来。。。。。
{
if(arr[y]>arr[y+1])
{
swap(arr,y,y+1);
}
}
}
}

复制代码

问题在代码注释里

作者: xuaner0719 时间: 2013-8-9 19:50
本帖最后由 xuaner0719 于 2013-8-9 21:08 编辑

骚年好好看下面的图图，相信你会明白的。加油

（j）vs (j+1).而0角标的元素每次都要参与比较，故每循环一圈后j=0这时，循环比较后，最值出现在末位，故，第二次循环比较就相应地减少一位元素。依此类推，就有减2，减3，…… 因此，j<arr.length-x。当j得变量取值为6时，y+1=7就会造成角标越界，因此，只有当j+1=6，即j=5时，元素才有可比性。那么，j的取值范围为j<arr.length-x-1.

作者: 饭后小笼包 时间: 2013-8-9 19:51
你可以用假设法
假如这个数组有6个元素
x的范围就是0<=x<arr.length-1 即0-4也就是比较5次轮回
如果y的范围是0<=y<arr.length-x
当x=0的时候
y就是0-5
当y循环到5的时候
在if语句里面会出现arr[5]>arr[6] 但是arr数组只有6个元素 arr[6]是第七个

作者: 吴光新 时间: 2013-8-9 19:55
防止数组角标越界

作者: 夜写意 时间: 2013-8-9 20:16
arr[]的角标最大只能是arr.length-1。所以arr[y+1]中y+1<arr.length。即：y<arr.length-1。
每次比较都会忽略后面 x 个元素，因为后 x 个元素已经排好序。所以 y< arr.length-1-x。
这里必须还要减掉1就是这样来的。

作者: 影响力147753321 时间: 2013-8-9 20:36
冒泡排序是这样的，因为最后一个元素不需要排。所以外循环要减一。对于内循环减1。是因为在每一次比较时，也不用比arr.length次，而是少比一次。就好比我们三个人比身高，你说要比几次呢?显然要少比一次。所以要减1。这不是重点，重要的是哥们，你这样会报数组越界异常。在外层徨x=0的时。如果不减1。内层循环条件变为y<arr.length 而执行语句却有arr[y+1],角标y+1，当内层循环运行y自增到y刚好等于arr.length-1,此时y+1就等于arr.length.也就是下标等于数组的长度。显然不行。

作者: 黑马王晓明 时间: 2013-8-9 21:52
外层循环控制的是比较的轮数内层循环控制的是每轮比较的次数假如有7个元素两两比较只需要比较6次就可以比较出一个最大的值
之后每轮比较的次数减一因为上一轮比较出的最大值已经不用再参与比较了这样说不知道楼主明白否？
楼主可以在纸上亲自一步一步画一画相信会很容易就理解了的
需要注意的就是记住外层控制的是大的次数而内层循环每次都会从0角标开始比较所以一次比一次得少一个吧
仔细想想不是很难理解的

作者: 张玉建 时间: 2013-8-9 21:59
冒泡排序
它的原理是数组中的相邻的两个元素进行比较，比较出现大小，根据是升序还是降序交换位置，
比较完一次就可以把数组的最后一位就确定（最大值或最小值）这样最后一位就不用参与比较，
这样依次就可以排出数组顺序，

/冒泡排序！
public static void maoPao(int[] arr)
{
//外循环x控制的是比较的范围。角标不能自己跟自己比，所以想x<arr.length-1
for (int x= 0;x<arr.length-1 ;x++ )
{
//内循环时，相邻的角标比，比出大小，交换位置,比完一次后，最值就出现在了最后一个角标上，
//当第二次比较时y的范围就要缩小x，所以y<arr.length-x-1,每次的最值都会出现在被比较的最后一个角标上了
//以此类推，一个有序的数组就出来了，
for (int y=0;y<arr.length-x-1 ;y++ )
{
//比较相邻角标位上的值。
if (arr[y]>arr[y+1])
{
//定义第三方变量，交换值。
int temp = arr[y];
arr[y]= arr[y+1];
arr[y+1]=temp;
}
}
}
}

作者: 垂天云 时间: 2013-8-10 07:00
可以简单举个例子，反着想一想，数组里只有三个数，排序···OK···

作者: 如果我长大了。 时间: 2013-8-11 10:24
这个是冒泡排序，如果你不-1，那么就会抛出数组下标越界异常（ArrayIndexOutofBoundexception）你可以看看。因为你始终都是和自己的下一在比较，如果不-1，那么到了最后一个数组下标不久越界了吗？所以必须要-1.

作者: 心灵之歌 时间: 2013-8-11 10:38
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++)//这里为什么arr.length-x之后还要再减去1啊，脑袋转不过来。。。。。
                                                                           //////减1是因为下面有y+1.如果不减1的话，这个数组算到最后那个角标的时候，再加一就会越界！
                     {
                              if(arr[y]>arr[y+1])
                              {
                                    swap(arr,y,y+1);
                              }
                     }
            }
      }

作者: 赵乐 时间: 2013-8-11 10:42
简单点说你可以这样理解 arr.length-1-x 首先length-1不用说了，肯定是防止角标越界，因为你冒泡是前一个跟后一个比较，不-1后面的y+1肯定越界，
其次-x就是说每排序成功一个就需要把比较的次数-去1个，而x就是控制总的比较次数，所以-x

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

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