黑马程序员技术交流社区

标题: 冒泡有点小问题，请指教。 [打印本页]
作者: 王勇文    时间: 2013-1-19 15:24
标题: 冒泡有点小问题，请指教。
本帖最后由 王勇文 于 2013-1-19 18:50 编辑
  1. **冒泡排序
  2. 原理：两个相邻元素进行比较，第一次比较完以后，最大值出现在了最大角标处。

  4. public static void bubbleSort(int[] arr)
  5. {
  6. //i<arr.length-1 n个数两两比，n-1次就能获得最值。
  7. for(int i=0; i<arr.length-1; i++)
  8. {
  9. //为了防止角标越界，j<arr.length-1
  10. //为了减少比较次数，j<arr.length-1-i
  11. for(int j=0; j<arr.length-1-i; j++)
  12. {
  13. if(arr[j]>arr[j+1])
  14. {
  15. int temp = arr[j];
  16. arr[j] = arr[j+1];
  17. arr[j+1] = temp;
  18. }
  19. }
  20. }
  21. }
复制代码
不明白的是，为什么第二个for里面j<arr.length-1-i
      为什么要减i？
作者: 柴乔军    时间: 2013-1-19 15:41
本帖最后由 柴乔军 于 2013-1-19 19:42 编辑

你首先要明白冒泡的原理，第二个for循环还可以写成如下代码：
  1. for(int i=0; i<arr.length; i++) {
  2.                         for(int j=i; j<arr.length; j++) {
  3.                                 if(arr[i]>arr[j]) {
  4.                                         temp = arr[i];
  5.                                         arr[i] = arr[j];
  6.                                         arr[j] = temp;
  7.                                 }
  8.                         }
  9.                 }
复制代码
楼主的算法是相邻的两个元素进行比较，比如2 3 5 1 2 当i=0时，排下来的结果就成为 2 3 1 2 5，可以看到5已经到了最高次，循环比较进行了4次，
当i=1时，就不需要再进行和5的比较，所以第二次的结果就是，2 1 2 3 5,这里3又到了次高位，循环比较了3次，所以为了提高比较运算的效率，第二个循环的次数是 <arr.length-1-i
我把运行过程给你写出来(j<arr.length-1-i)：
i=0时 2,3,1,2,5;for循环了4次；
i=1时 2 1 2 3 5 ;for循环了3次；
i=2时 1 2 2 3 5; for循环了2次；
....
当（j<arr.length-1）：
i=0时 2,3,1,2,5;for循环了4次；
i=1时 2 1 2 3 5 ;for循环了4次；
i=2时 1 2 2 3 5; for循环了4次；
...
结果是一样的，运算次数不一样罢了
作者: 范天成    时间: 2013-1-19 15:44
这样说吧，假设N个数排序，i=0的时候，里面循环是j从零一直到N-1，比较出最大的，放到arr[N-1];然后i=1,里面的循环是j=0开始，这个时候，还剩下N-1个数需要排序，这样j只要递增到（N-1）-1就可以比较出倒数第二大的数字，以此类推，可以发现，内循环j的最大取值正好是（N-1）-i。当然，因为你的代码是arr[j]和arr[j+1]比较，所以用的j<arr.length-1-i。表述的不好，希望你能看明白。
作者: 祝文丞    时间: 2013-1-19 16:16
建议在看下老毕画的图。。
作者: 张洪慊    时间: 2013-1-19 19:33
本帖最后由 张洪慊 于 2013-1-19 19:37 编辑

我写的,你应该可以理解,以5,3,7,9,1为例
冒泡排序(从小到大,从零趟开始为了操作方便)
         算法思想:
          相邻两个数比较,两两比较得到的较大数不断后移,
          最终每趟最大沉底.
          示例:下标 0 1 2 3 4
             i             5 3 7 9 1
                     
                         3 5 7 9 1      5>3交换
          第零趟:  3 5 7 9 1       5<7不动
                       3 5 7 9 1       7<9不动
                       3 5 7 1 9       9>1交换-->9为最大,arr[4]为9
                共比较4(arr.length-0(趟数)-1)次
          第一趟:  3 5 7 1   -->9不用在参与比较
                       3 5 7 1      3<5不动
                       3 5 7 1     5<7不动
                       3 5 1 7     7>1交换-->7为次大,arr[3]为7
                  共比较3(arr.length-1-1)次
          第二趟: 3 5 1       -->7不用再参与比较
                      3 5 1       3<5不动
                      3 1 5       5>1交换-->arr[2]为5
                     共比较2(arr.length-2-1)次
          第三趟: 3 1        -->5不用再参与比较
                      1 3        3>1交换-->arr[1]为3
                     共比较1(arr.length-3-1)次
              以上共走了4(arr.length-1)趟
          最后一定剩余一个数字1,不用再参与比较,肯定最小  
作者: 奋斗的小强29    时间: 2013-1-19 22:30
王勇文 发表于 2013-1-19 15:24:43
本帖最后由 王勇文 于 2013-1-19 18:50 编辑
**冒泡排序
原理：两个相邻元素进行比较，第一次比较完以后，最大值出现在了最大角标处。

public static void bub

内循环随着外循环的变化而变化，



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