黑马程序员技术交流社区

标题: 有关冒泡排序法的 [打印本页]

---

作者: 踏雪风暴    时间: 2014-6-24 16:35
标题: 有关冒泡排序法的


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++)     //  这个条件的没有看懂
                        {
                                if(arr[y]>arr[y+1])
                                {                                
                                        int temp = arr[y];
                                        arr[y] = arr[y+1];
                                        arr[y+1] = temp;                        
                                }
                        }
                }
        }
有两处没明白：
一处：
以  arr={3,1,4,6,2}； 为例，它这个是怎么冒泡排序的，是这样的：
1.    1,3,4,2,6
2.     1,3,2,4,6
3.     1,2,3,4,5,6     三步这样吗？
另一处：for(int y=0; y<arr.length-x-1; y++)     //  这个条件的没有看懂   
求解答。。

---

作者: 踏雪风暴    时间: 2014-6-24 16:51
怎么没人呢，高手呢？

---

作者: dispensable    时间: 2014-6-24 17:07
arr[]={3 ,1, 4 ,6, 2}
第一步： x=0  进入for内循环  Y=0  进入内循环 因为3>1  所以调换成： 1 3 4 6 2
第二步： Y++  Y=1 < 4  内循环仍然满足条件 循环继续  变成     ：         1 3 4 6 2
第三步：     ………………………………………………………………………………      1 3 4 6 2
第四步：   ……………………………………………………………………………………       1 3 4 2 6
此时第一次内循环结束（最大值6被排到了最后）
X = 1   进入循环  y=0 <3  进入内循环 执行结果为：         1 3 4 2 6
  第2步：                                                                  1 3 4 2 6
  第3步：                                                                  13 2 4 6
此时第二次内循环结束第二轮的最大值4被排到了最后

冒泡排序的含义是：相邻两个元素比较 ，每一轮内循环结束，最大的一个泡泡被排到最后
y<arr.length-x-1 这个条件是因为，每次X++之后 代表一轮内循环结束了，也就是说有N个最大的泡泡被排到了最后既然已经被排到了最后，那最后几个就不用排了，所以arr.length -x-1 ，代表第X轮后，只排前面的arr.length-x-1个元素 ，你看一下依次下来，第一次需要排4次，第二次就只用排3次，第三次只用排2次了，理解了吗？
而且不要说高手什么的，没人是专门为你回答的问题，平时多点耐心，况且你这个问题视频里讲得更清楚，建议你多看几遍。

---

作者: pengyu    时间: 2014-6-24 17:10
进来学习下

---

作者: 踏雪风暴    时间: 2014-6-24 17:18

dispensable 发表于 2014-6-24 17:07
arr[]={3 ,1, 4 ,6, 2}
第一步： x=0  进入for内循环  Y=0  进入内循环 因为3>1  所以调换成： 1 3 4 6 2  ...

视频学习中。。。谢谢回答，先投你一票

---

作者: 汉谟拉比    时间: 2014-6-24 17:44
就以你说的为例吧

---

作者: 汉谟拉比    时间: 2014-6-24 18:48
快速回复点快了！！！
以你说的为例arr={3,1,4,6,2}      
第一步 x=0，y=0    3和1比较   3比1大  所以调换成        1,3,4,6,2
第二部 x=0，y=1    3和4比较   3比4小  所以不用调换     1,3,4,6,2
第三部 x=0，y=2    4和6比较   4比6小  所以不用调换     1,3,4,6,2
第四部 x=0，y=3    6和2比较   6比2大  所以调换位置     1,3,4,2,6
这样就比较好了一趟，由于if语句中有arr[y+1]，所以y的最大值为arr.length-1;
每比较好一趟之后就有一个大数沉到最下面，这个大数就不用参与到我们后面的比较当中，所以y<arr.length-1-x,另外告诉你其实y的范围也可以用y<arr.length-1,对于结果没有影响，你自己可以思考一下哦！

---

作者: 汉谟拉比    时间: 2014-6-24 18:49
可以的话帮我加个分吧，谢谢啦，有什么问题在提，，，大家相互学习

---

作者: 踏雪风暴    时间: 2014-7-12 22:44
大家相互学习

---

作者: 韩天雷    时间: 2014-7-12 22:46

1. //冒泡排序
   
2. public class BubbleSort {
   
3. 
   
4.         // 主函数
   
5.         public static void main(String[] args) {
   
6.                 int arr[] = { 6, 2, 9, 3, 12, 1 };
   
7.                 System.out.println("原数组:");
   
8.                 printArray(arr);
   
9.                 System.out.println();
   
10.                 System.out.println("排序过程:");
    
11.                 bubbleSort(arr);
    
12.                 System.out.println("排序结果:");
    
13.                 printArray(arr);
    
14.         }
    
15. 
    
16.         // 冒泡排序算法
    
17.         public static void bubbleSort(int[] arr) {
    
18.                 for (int x = 0; x < arr.length; x++) {
    
19.                         for (int y = 0; y < arr.length - x - 1; y++) {
    
20.                                 if (arr[y] > arr[y + 1]) {
    
21.                                         swap(arr, y, y + 1);
    
22.                                 }
    
23.                         }
    
24.                         printArray(arr);
    
25.                         System.out.println();
    
26.                 }
    
27.         }
    
28. 
    
29.         // 数组元素交换位置
    
30.         public static void swap(int[] arr, int x, int y) {
    
31.                 arr[x] = arr[x] ^ arr[y];
    
32.                 arr[y] = arr[x] ^ arr[y];
    
33.                 arr[x] = arr[x] ^ arr[y];
    
34.         }
    
35. 
    
36.         // 打印数组
    
37.         public static void printArray(int[] arr) {
    
38.                 System.out.print("[");
    
39.                 for (int x = 0; x < arr.length; x++) {
    
40.                         if (x != arr.length - 1)
    
41.                                 System.out.print(arr[x] + ",");
    
42.                         else
    
43.                                 System.out.print(arr[x] + "]");
    
44.                 }
    
45.         }
    
46. }

复制代码

运行下看看`

---

作者: 踏雪风暴    时间: 2014-7-12 23:59
大家相互学习

---

作者: 泛小型    时间: 2014-7-14 09:33
  最好是画图看看

---

作者: 導ぷ仙″兲蕐    时间: 2014-7-14 11:03
冒泡排序法是从数组第一位开始比较,a[0]>a[1]换位a[1]>a[2]换位这样一直换,到最后一位将是最大的那个数,然后再从头比较 ,因为最后一位已经是最大的了那么它不用再进行比较,所以-x-1,再交换出第二个大的,然后一直循环直到所有的数据排完序.

---

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

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