黑马程序员技术交流社区

标题: 冒泡排序问题 [打印本页]
作者: 王杰123    时间: 2013-3-24 23:26
标题: 冒泡排序问题
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的原因是每次y比较次数在减少
         if(arr[y]>arr[y+1]){
            int tmp=arr[y];
              arr[y]=arr[y+1];
              arr[y+1]=tmp;
          }
       }
   }
}


谁能解释一下，外循环x<arr.length-1 为啥减1，内循环y<arr.length-x-1 为什么减x，又为什么减1. 我听视频绕不过来，感觉有点困难。
作者: 孙百鑫    时间: 2013-3-24 23:39
外循环x<arr.length-1 ，是因为整个数组的长度。-1才是角标的长度。角标从0开始的。
内循环y<arr.length-x-1 ，也是这个原理，至于每次都-x是因为Y的次数在减少。
作者: 孙百鑫    时间: 2013-3-24 23:40
反正这里我也和你一样有这个问题。。后来我是这么理解的。 - -
作者: 曹玉龙    时间: 2013-3-24 23:51
这个问题是有点绕弯，给你做了个注释，看完应该能明白了。
  1. class Demo
  2. {
  3.    public static void main(String[] args)
  4.    {
  5.       //定义一个int类型的数组
  6.       int [] array = {32,2,0,687,3,76,-2};
  7.       //输出排序前的数组
  8.       System.out.print("排序前:");
  9.       printArr(array);
  10.       //调用冒泡排序法的方法
  11.       arrBubble(array);
  12.       //输出排序后的数组
  13.       System.out.print("排序后:");
  14.       printArr(array);
  15.    }
  16.    //遍历并输出数组
  17.    public static void printArr(int [] arr)
  18.    {
  19.       System.out.print( "[");
  20.       for (int x = 0;x < arr.length ;x++ )
  21.       {
  22.         if (x < arr.length - 1)
  23.         System.out.print(arr[x] + ",");
  24.         else
  25.         System.out.print(arr[x]);
  26.       }
  27.       System.out.println( "]");
  28.    }
  29.    //使用冒泡法排序数组的方法
  30.    public static void arrBubble(int [] array)
  31.    {
  32. //从0索引开始,共需要比较array.length - 2.
  33. //比如[0,1,2,3],这个数组有4个值,索引号是0,1,2,3,length长度是4
  34. //显然一共需要比较3次,当x从0开始,它的值变化是0,1,2也就是变化到length - 2
  35. //代码体现就是x<=length - 2或者x<length-1.
  36.       for (int x = 0;x < array.length - 1 ;x++ )
  37.       {
  38.         //这里减1的道理和上面一样,减x是因为它每次循环需要比较的次数恰好等于减去当次x的值
  39.                 //这个自己想一下,很容易懂
  40.         for (int y = 0;y < array.length - x - 1 ; y++)
  41.         {
  42.            //实现将较大的数排在后面
  43.            if (array[y] > array[y + 1])
  44.            {
  45.               //调用两个数组元素互换位置的函数
  46.               arrHuan(array,y,y+1);
  47.            }
  48.         }
  49.       }
  50.    }
  51.       //两个数组元素互换位置的函数
  52.       public static void arrHuan(int [] arr,int x,int y)
  53.    {
  54.       int temp = arr[x];
  55.       arr[x] = arr[y];
  56.       arr[y] = temp;
  57.    }
  58. }
复制代码
作者: 王杰123    时间: 2013-3-24 23:55
孙百鑫 发表于 2013-3-24 23:39
外循环x

比如数组 int arr[] = {2,23,6,7,44,33,98}  x<arr.length-1  减1 在听毕老师我觉得是冒泡排序是相邻的两个元素进行比较，在比后最大的值慢慢往右移动，最后剩下2，就是为了不用在多比较一次所以就减1.
作者: 莫道荣    时间: 2013-3-24 23:56
外循环x<arr.length-1是因为排序排到最后的时候不再循环自己跟自己比较,因为x已经到了最后.内循环y<arr.length-x-1 减1是因为内循环体中arr[y]是跟arr[y+1]比,没一次循环都是第一个角标跟第二个角标,第二跟第三角标依次循环比较下去,如果不减1就会越界,如果不减1arr.length循环因为是arr[y+1]所以到最后就会是arr.length+1,就会出现角标异常...又减x就是让他不再自己跟自己比较
作者: 柳 德 彬    时间: 2013-3-25 00:14
这个地方我想很多人都没有搞明吧，老师也讲的不太明白，，只有自己慢慢摸索。
作者: 王杰123    时间: 2013-3-25 00:17
莫道荣 发表于 2013-3-24 23:56
外循环x

高手在民间
作者: 柳 德 彬    时间: 2013-3-25 00:18
可以看看这个代码，希望对你有帮助。主要是要理解。
  1. package com.oo.sort;

  3. /**
  4. *         冒泡排序       
  5. *                         改进
  6. *        
  7. * @author evoline
  8. *
  9. */
  10. public class BubbleSortTest1 {

  12.         static void bubbleSort(int[] arr)
  13.         {
  14.                 for (int i = 0; i < arr.length; i++) {
  15.                         for (int j = 0; j < arr.length-i-1; j++) {
  16.                                 if (arr[j] > arr[j+1]) {
  17.                                         int tmp = arr[j];
  18.                                         arr[j] = arr[j+1];
  19.                                         arr[j+1] = tmp;
  20.                                 }
  21.                         }
  22.                         System.out.println("第"+(i+1)+"趟排序");
  23.                         for (int k = 0; k < arr.length; k++) {
  24.                                 System.out.print(arr[k]+" ");
  25.                         }
  26.                         System.out.println();
  27.                 }
  28.         }
  29.        
  30.         public static void main(String[] args) {
  31.                 int[] arr = {21,17,14,9,10,2};
  32.                 bubbleSort(arr);
  33.         }
  34. }
复制代码
作者: 王杰123    时间: 2013-3-25 00:24
孙百鑫 发表于 2013-3-24 23:40
反正这里我也和你一样有这个问题。。后来我是这么理解的。 - -

莫道荣  这位楼主说的有道理，你可以看一下。
作者: _王涛    时间: 2013-3-25 00:24

我刚写了一下冒泡排序原理：看后相信你已经一目了然了。
例如以下需要进行排序的数：
6 2  4  1
小----》大
第一趟（外循环）
第一次两两比较6>2（内循环）：
    2 6 4 1
第三次两两比较6>4:
    2 4 6 1
第三次两两比较6>1:
    2 4 1 6
第二趟 （外循环）
  第一次两两比较2<4不交换（内循环）：
    2 4 1 6
  第二次两两比较4>1
    2 1 4 6
  第三次两两比较4<6不交换
    2 1 4 6
第三趟 （外循环）
  第一次两两比较2>1（内循环）：
    1 2 4 6

完成排序！
对下面代码分析：
for(int x=0;x<arr.length-1;x++){
      for(int y=0;y<arr.length-x-1;y++){

可见由以上冒泡原理可知，
数组的长度为4 ，数学中表示0=<x<4， 根据下标判断外循环循环了0,1,2,3共四次，由以上步骤事实证明外循环真正循环了3次，所以arr.length-1外循环必须减1；
对于内循环，由事实证明，每当从数组中拿一个数跟其它数一一比较后，随着外循环的增加，这个数需要比较的次数在递减，所以内循环需要减去外循环x,由于外循环下标从0开始，所以为了避免数组角标越界，在此内循环需要减去1。

兄弟希望对你有帮助！！！


作者: 王杰123    时间: 2013-3-25 00:32
莫道荣 发表于 2013-3-24 23:56
外循环x

y<arr.length-x-1  减x 是因为，外循环每循环一次，内循环就按照相邻比较一遍，比较一遍以后就会定下一个最大值，下一次循环时候就少一个角标参与运算，所以减去的是循环次数。
作者: 康嘉    时间: 2013-3-25 00:44
标题: 好办,看着
本帖最后由 康嘉 于 2013-3-25 00:46 编辑

看你这个题我都不困了,呵呵===跟你分享下我自己的理解,看看是不是对你有帮助
这么跟你说 吧  其实这个一个数学问题  我给你举个例子  
===== 如果让你比较 2个数 A , B  的大小   你比较几轮几次? 答案 是 一轮一次  你可能没明白轮是啥意思
===== 我再问你,3个数 A,B ,C  比较,你比较几轮几次?  答案是  2轮 三次,貌似你看出点什么了 ...
===== 4个数比较呢  3轮六次
所以  你可以感觉到  n 个数比较 就要比较 N-1 轮  多少次呢 [这个结果跟你的题没有啥关系,当然结果是:N-1+ N-2 +...+1 次 也就是 N*(N-1)/2 次 ]

A B        1轮一次  
A.B.C    2轮三次
A.B.C.D 3轮六次.
N个数    N-1轮 那么些次...

背景结束  如果你明白了 轮数的意义 你就发现这就是  X 了吧...对 ,就是这个外循环...   你数组里面有arr.length个数,得比 arr.length-1 轮吧, 如果设置8位数的数组,只要循环8-1=7次就可以了 对吧, 可以这么说,跟arr.length没有绝对关系  但是 arr.length告诉你长度了 不用你查多少个数了吧(一个一万个数的数组你也查不过来,呵呵)  不用白不用  所以 就跟 arr.length 有关系了   什么关系呢? X就是比arr.length 小一的轮数
你自己查 如果arr.length 是8
int x =1  那就是x < arr.length  ,1~7是不是七个数
如果 int x =0 ,那就是 x<arr.length-1 ,0~6是不是也是七个数  
======.一样的 没区别.
那为什么要选 arr.length-1 呢 ,因为这么代码好记 为什么好记呢?
因为y 表示角标 相邻比较arr[y]和arr[y+1]比,这样y只能取到y<arr.length-1,如果x也取到arr.length-1,n你这这个代码多好记
public static void bubbleSort(int[] arr){               
                          for (int x = 0; x < arr.length-1 ;x++ ){
                        for (int y = 0; y < arr.length-1 ;y++ ){
                                if ( arr[y] < arr[y+1]){
                                        int temp = arr[y];
                                           arr[y]=arr[y+1];
                                           arr[y+1]=temp;
                }}}}    for里面的全一样,呵呵  而且还不用减什么X 啥的  你觉得呢?  哪不明白继续留言吧  睡了哈.....


作者: 刘焕新    时间: 2013-3-25 00:44
本帖最后由 幻@尋 于 2013-3-25 00:54 编辑

LZ你那种写法有些晦涩，而且算法的速度并不是最快的，其实 x<arry.length-1 是针对最末尾的取数，y在内层循环比过了，外层x就不必再比较一次了。
你可以看看我下面的这种冒泡排序，我测试了一下，貌似我这个计算耗时更小些，而且容易理解：
  1. public static void bubbleSort(int[] arry)
  2. {
  3.       //外层循环：取数是从数组的下标为0开始，下标值递增取数，取到最后倒数第二个即可
  4.       for(int x=0; x<arry.length-1; x++)
  5.       {
  6.             //内层循环：取数是从数组的最大下标值开始，下标值递减取数，直到与外层下标值最近的值
  7.             for(int y=arry.length-1; y>x; y--)
  8.             {
  9.                   //若两两比较的结果为：左边大于右边的数，则左右交换
  10.                   if(arry[x] > arry[y])
  11.                   {
  12.                         int temp = arry[x];
  13.                         arry[x] = arry[y];
  14.                         arry[y] = temp;
  15.                   }
  16.             }
  17.       }
  18. }
复制代码
算法的耗时比较：
long start = System.nanoTime();
bubbleSort(arry);
long end = System.nanoTime();
System.out.println("耗时：" + (end-start) + "纳秒.");
作者: 康嘉    时间: 2013-3-25 00:48
孙百鑫 发表于 2013-3-24 23:39
外循环x

冒泡循环是相邻的比较,所以角标变量只有 y 一个就够了 ,不用X , X 表示比较的轮数
作者: 康嘉    时间: 2013-3-25 00:54
// 直接运行 看结果
class  bubblesort{
        public static void main(String[] args) {
                int[] arr={3,6,98,5,3,7,9,54};
                printArr(arr);
                bubbleSort(arr);
                printArr(arr);
        }
        public static void bubbleSort(int[] arr){
                for (int x = 0; x < arr.length-1 ;x++ ){
                        for (int y = 0; y < arr.length-1 ;y++ ){
                                if ( arr[y] > arr[y+1]){
                                        int temp = arr[y];
                                           arr[y]=arr[y+1];
                                           arr[y+1]=temp;
        }}}}
        public static void printArr(int[] arr){
                System.out.print("[");
                for (int x = 0; x < arr.length ; x++ ){
                        if (x!=arr.length-1)
                                System.out.print(arr[x]+",");
                        else
                                System.out.println(arr[x]+"]");
                }
    }
}

作者: 曾祥旭    时间: 2013-3-25 08:14
所谓的冒泡排序就是相邻的两个数进行比较，如：0角标和1角标相比，判断58比14大那么置换位置；继续判断角标1和角标2，判断58比5大那么置换位置；以此循环，到最后一次比较就是角标5和角标6相比，判断58和9哪个大，发现角标5比角标6大，此时置换位置，角标6就不需要再比较了（这个时候，再第二次循环的时候就不需要和角标6相比了，我们就可以把它去掉）。如图1-1所示，第一次循环结束，那么循环的次数就是arr.length-1。
这时候的外循环就是： for(int x=0;x<arr.length-1;x++){}

所谓的冒泡排序就是相邻的两个数进行比较，如：0角标和1角标相比，判断58比14大那么置换位置；继续判断角标1和角标2，判断58比5大那么置换位置；以此循环，到最后一次比较就是角标5和角标6相比，判断58和9哪个大，发现角标5比角标6大，此时置换位置，角标6就不需要再比较了（这个时候，再第二次循环的时候就不需要和角标6相比了，我们就可以把它去掉）。如图1-1所示，第一次循环结束，那么循环的次数就是arr.length-1。
这时候的外循环就是： for(int x=0;x<arr.length-1;x++){}

33.png (15.44 KB, 下载次数: 35)

33.png

44.png (16.76 KB, 下载次数: 32)

44.png
作者: 钟佩桓    时间: 2013-3-25 10:52
我也是刚开始看视频 现在看到day06了  不过对于冒泡排序学过数学的就很容易理解了  首先你得明白它的原理：冒泡排序是相邻的两个元素进行比较，如果符合条件换位。你把你的代码给你分步解释下你就明白了。
/*
比如说你有一个数组{5，4,3,2,1,} 那么,5开始作为一个数去和后面的4比较如果小于4那么就和4进行换位。5不小于4，那么y++角标加1
又用4去和3比较，3和2比较，2和1比较。一共就只有比较4次。也就是说数组里有N个数，第一次只用比较N-1次就可以了。
第一次比较就可以得到最大的数排在数组的第一位，那么后面几次从数组的1角标开始进行比较也就是{4,3,2,1，}开始排序，只需要
3次比较就可以了。相当于毕老师说的脚尖朝下，
****
***
**
*
那么外循环控制行数，也就是4行，N-1次，所以这里要x<arr.length-1.
对于 y<arr.length-x-1   先给你说下为什么-1
y=0；arr.length=5；如果让y<arr.length  那么y最大可以取arr.length-1也就是4，arr[y+1]=5;
那你让arr[y]和arr[y+1]比较还有意义么。相当于这里的arr[y]就是1，让1再去和后面的比较？后面已经没有值了
所以这里要减1.避免角标越界。

-x的原因：  我们刚才第一次比较完得出了一个最大值排在最开始角标0处，那么第二次循环{4，3,2,1}只用比较
3次了 那么当y比较到最后一位2的时候就该停止了，因为2和1比较完就已经结束了 根本不用再拿1去比较。
所以-x让每一次比较的元素减少

*/
希望我的理解能对你有帮助  一起加油吧
作者: 罗平    时间: 2013-3-25 11:38
public static void swp(int[] arr,int a,int b)
        {
          int temp=arr[a];
          arr[a]=arr[b];
          arr[b]=temp;

        }
       
        //冒泡排序
        public static void bubbleSort(int[] arr)
        {
                for(int x=0;x<arr.length-1;x++)
                {
                       
                        for(int y=0;y<arr.length-1-x;y++)
                        {
                                if(arr[y]>arr[y+1])
                                {        swp(arr,y,y+1);
                               
                                }
                               
                        }
                }
               
        }

在实现排序功能的时候，如果一个java文件中有多个需要交换数据的时候，就把那个交换数据那部分单独做成一个函数
这样不仅显得排序模块里代码简练，还可以代码复用，这也算一种改良吧。
作者: 日三省    时间: 2013-3-25 21:45
罗平 发表于 2013-3-25 11:38
public static void swp(int[] arr,int a,int b)
        {
          int temp=arr[a];

public static void mp(int arr[])
{
  for(int x = 0;x < arr.length-1 ; x++ )
  {
   for(int y=arr.length-1;y>1;y--)   
   {
    if (arr[x] > arr[x+1])
    { int temp = arr[x];
     arr[x] = arr[x+1];
     arr[x+1] = temp;
    }   
   }
  }
}

这样写可以不?



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