黑马程序员技术交流社区

标题: 关于老师视频中冒泡排序的问题 [打印本页]

---

作者: 张明    时间: 2012-8-16 22:03
标题: 关于老师视频中冒泡排序的问题

1. 
   
2. class Paixu
   
3. {
   
4. public static void sop(int[] arr)
   
5. {
   
6.   for(int x=0;x<arr.length;x++)
   
7.   {
   
8.    System.out.print(arr[x]+"\t");
   
9.   }
   
10.   System.out.println();
    
11. }
    
12. public static void maopao(int[] arr)
    
13. {
    
14.   for(int x=0;x<arr.length-1;x++)
    
15.   {
    
16.    for(int y=0;y<arr.length-x-1;y++)//减X让每一次比较的元素减少，-1是避免角标越界
    
17.    {
    
18.     if(arr[y]>arr[y+1])
    
19.     {
    
20.      int temp=arr[y];
    
21.      arr[y]=arr[y+1];
    
22.      arr[y+1]=temp;
    
23.     }
    
24.     sop(arr);
    
25.    }
    
26.   }
    
27. }
    
28. public static void main(String[] args)
    
29. {
    
30.   int[] arr={1,2,3,4,5,6,7,8,9};
    
31.   //排序前
    
32.   sop(arr);
    
33.   System.out.println("-------------");
    
34.   //排序后
    
35.   maopao(arr);
    
36. }
    
37. }
    

复制代码

这是根据老师的冒泡排序写出来的，我做了一点改进，让冒泡排序的具体过程体现出来
如代码所示如果arr已经是这种排列好的，还要执行的话，就会出现这种情况

效率十分低下啊，不管arr是否排列好，所要经历的步骤确实相同的，这个只与arr元素个数有关，有没有一种更好的方法呢？

---

作者: 曹恒业    时间: 2012-8-16 22:22
楼主对于算法效率的问题挺敏感的。原始的冒泡排序确实遇到这种极端情况，效率会显得比较低。但是还有改进的冒泡算法。我在楼主的代码中改一下，你就明白这种改进冒泡算法的思想核心了。见下面的红色字体。
class Paixu
{
        public static void sop(int[] arr)
       {
              for(int x=0;x<arr.length;x++)
             {
                    System.out.print(arr[x]+"\t");
             }
             System.out.println();
       }

       public static void maopao(int[] arr)
       {
               boolean swap;//定义一个标志位，来判断冒泡一次各元素的位置是否发生变化
               for(int x=0;x<arr.length-1;x++)
              {
                        swap = false; //新的冒泡开始前，要先赋值为false
                        for(int y=0;y<arr.length-x-1;y++)//减X让每一次比较的元素减少，-1是避免角标越界
                        {
                                  if(arr[y]>arr[y+1])
                                  {
                                       int temp=arr[y];
                                       arr[y]=arr[y+1];
                                       arr[y+1]=temp;
                                       swap = true; //如果发生了元素交换，swap赋值为true，意为发生swap
                                  }
                                  sop(arr);
                         }
                         if(!swap)      //如果冒泡一次都没有发生交换，证明数组顺序已经确定，这里判断后函数直接返回
                                 return;
              }
      }

      public static void main(String[] args)
      {
                 int[] arr={1,2,3,4,5,6,7,8,9};
                 //排序前
                 sop(arr);
                 System.out.println("-------------");
                 //排序后
                 maopao(arr);
      }
}

---

作者: 张明    时间: 2012-8-16 22:24

曹恒业 发表于 2012-8-16 22:22
楼主对于算法效率的问题挺敏感的。原始的冒泡排序确实遇到这种极端情况，效率会显得比较低。但是还有改进的 ...

OK,我懂了，就是定义一个标记变量即可，soga，soga

---

作者: 张明    时间: 2012-8-16 22:27

曹恒业 发表于 2012-8-16 22:22
楼主对于算法效率的问题挺敏感的。原始的冒泡排序确实遇到这种极端情况，效率会显得比较低。但是还有改进的 ...

对了，布尔类型的变量，默认初值就是false吧，定义的时候已经初始化了

---

作者: 曹恒业    时间: 2012-8-16 22:46

张明 发表于 2012-8-16 22:27
对了，布尔类型的变量，默认初值就是false吧，定义的时候已经初始化了

默认初值是false，为了代码的易读性，建议不要刻意省一些影响理解的关键步骤。
而且这一题中，如果你认为可以省略，证明你还没理解这个判断标记的原理。
建议你再仔细想想。

---

作者: 张明    时间: 2012-8-16 23:14

曹恒业 发表于 2012-8-16 22:46
默认初值是false，为了代码的易读性，建议不要刻意省一些影响理解的关键步骤。
而且这一题中，如果你认为 ...

恩，我不是可以省略，只是要在用的时候知道他是有初值还是没有初值的，这个在变量中也是比较重要的啊

---

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

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