A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 王勇文 中级黑马   /  2013-1-19 15:24  /  1472 人查看  /  5 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 王勇文 于 2013-1-19 18:50 编辑
  1. **冒泡排序
  2. 原理:两个相邻元素进行比较,第一次比较完以后,最大值出现在了最大角标处。

  3. public static void bubbleSort(int[] arr)
  4. {
  5. //i<arr.length-1 n个数两两比,n-1次就能获得最值。
  6. for(int i=0; i<arr.length-1; i++)
  7. {
  8. //为了防止角标越界,j<arr.length-1
  9. //为了减少比较次数,j<arr.length-1-i
  10. for(int j=0; j<arr.length-1-i; j++)
  11. {
  12. if(arr[j]>arr[j+1])
  13. {
  14. int temp = arr[j];
  15. arr[j] = arr[j+1];
  16. arr[j+1] = temp;
  17. }
  18. }
  19. }
  20. }
复制代码
不明白的是,为什么第二个for里面j<arr.length-1-i
      为什么要减i?

评分

参与人数 1技术分 +1 收起 理由
Rancho_Gump + 1 赞一个!

查看全部评分

5 个回复

倒序浏览
本帖最后由 柴乔军 于 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次;
...
结果是一样的,运算次数不一样罢了
回复 使用道具 举报
这样说吧,假设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 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:42
地板
王勇文 发表于 2013-1-19 15:24:43
本帖最后由 王勇文 于 2013-1-19 18:50 编辑
**冒泡排序
原理:两个相邻元素进行比较,第一次比较完以后,最大值出现在了最大角标处。

public static void bub

内循环随着外循环的变化而变化,来自: Android客户端
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马