黑马程序员技术交流社区

标题: 关于冒泡排序的理解 [打印本页]

---

作者: 余宏    时间: 2012-5-17 13:37
标题: 关于冒泡排序的理解
public static void sort(int [] arr){
                for(int x=0;x<arr.length-1;x++){
                        for(int y = 0;y<arr.length-x-1;y++){//此处为什么是y<arr.length-x-1？
                                if(arr[y]>arr[y+1]){
                                        int temp = arr[y];
                                        arr[y] = arr[y+1];
                                        arr[y+1] = temp;
                                }
                        }
                }
        }

---

作者: 吴兆焕    时间: 2012-5-17 13:48


其实我比较习惯arr.length-1-x这样写。
arr.length-1 比如数组长度为6，只用循环5次就可以排列好,所以要-1。

因为每循环一次，减一就可以完成排序，而x每循环1次，就会加1，所以就可以写成arr.length-1-x

你先要 理解 冒泡排序 的原理，你可以看毕老师讲的，04天-05课，主要理解他画的那个图。理解那个图，就能理解为什么。

---

作者: 包晗    时间: 2012-5-17 13:51
冒泡是两两互换.
y<arr.length-x-1 中的 y<arr.length-1 是最后一个元素后没有比较了  所以-1
因为你的第一次循环...两两互换 就能找到数组中最大的  
第一找到最大的,第二次循环就能找到第2大的..第一次运行后 y<arr.length-1  第二次是y<arr.length-2 ,第3次是y<arr.length-3...
以此类推
X是次数 ...每次循环X会自己加1                  y<arr.length-x-1

---

作者: 潘东升    时间: 2012-5-17 13:57
如果不是y<arr.length-x-1，而是y<arr.length-x，就会造成角标越界，比如长度是5，当x=0的时候，y可以取4，然后下面有arr[y+1]，这样就会出现arr[5]了，就是角标越界了。

---

作者: 杨康    时间: 2012-5-17 13:59
冒泡选择的外循环每循环一次，内循环就少一次比较，也就是说当x=0时，通过比较厚确定出最后角标位。当x=1时，内循环比较的时候就不会再去跟最后一位去比较，比较次数-1.同理当x=2时，就-2......所以通过循环发现，外循环没减少一次，内循环也就随之相应的变化，故应该y<arr.length-x。然后看内循环的条件，因为y跟y+1都处于内循环，所以都要满足其所处的内部环境，即：
y<arr.length-x
y+1<arr.length-x
两个结果求交集，就得到y<arr.length-x-1.

---

作者: 李文富    时间: 2012-5-17 14:20
我想在这里分享下我对冒泡排序的理解：
1.冒泡即形象的描述气泡由于在水中受压强的影响，从下往上越来越大；
  故应用到编程中，一串泡，是由小到大排列的、
2。给一串无规律的数字；
  按冒泡思想：第一次就冒出最大的，找出来了，还要排序的总数减一
              第二次就冒出剩余的最大的，找出来了，还要排序的总数再减一

              ......
              最后一次就是那个，不用找了，还要排序的总数为0；
//此处为什么是y<arr.length-x-1？
     arr.length-1 ：因为最后那次不用找了
       再 - x ：是因为已经找出了x个了
这样能明白不？

---

作者: hongbo    时间: 2012-5-17 14:26
冒泡排序，看名字，就觉得和水泡一样，水泡距离水面越深，水泡越小，，水泡露出水面，你就可以想象它爆破了，没有了，
所以冒泡是先大的找出来排出来，最大的找出来后就不用再排了，
因为每次都是找一个排除，所以你排几次，就减几次，也就是i等于几的时候，你就认为排几次，！-1的原因是，数组下标从0开始取，所以最大下标为
arr.length-1.

---

作者: 古银平    时间: 2012-5-17 14:37


冒泡排序，是相邻两个元素相互比较，比如一个5元素的数组，然后符合条件就互换，
如果y<arr.length-x，外循环每循环一次，内循环条件y<arr.length-1,每次减1减2，减的就是外循环的x。外侧循环x=5时if(arr[y]>arr[y+1])，y+1=4， arr[y+1]就会越界，所以要减1。

---

作者: 彩虹    时间: 2012-5-18 01:56
      哥们,我用纯逻辑推理 的方式给你执行一下：
      比如：现有一个一维数组，其中存储有一列数，分别为：25,61,48,86,72,95 ，共6个数               
      冒泡排序的过程如下：
                 y=0:a[0]和a[1]比，即25和61比，不满足if条件，不进行交换
                 y=1:61与48比，满足if条件，交换，变为48  61
     x=0时  y=2:61与86比，不满足if条件，不进行交换  
                 y=3：86与72比，满足条件，交换，变为72  86
                 y=4:86与95比， 不满足if条件，不进行交换
                 y=5，不满足for循环条件，跳出循环
     由此，完成一趟冒泡排序，找到了最大数为95，冒泡排序其实就是大的数往下沉 ，没跑完一趟，找出一个相对最大数  
     接下来
     x=1时，进行第二趟排序，思想如同上面，一步一步推
     ........
    最终，可得出由小到大的一列有序数。即：25,48,61,72,86,95

---

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

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