黑马程序员技术交流社区

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

作者: 踏雪风暴    时间: 2014-6-24 16:35
标题: 有关冒泡排序法的
本帖最后由 踏雪风暴 于 2014-6-24 17:18 编辑

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.         public static void main(String[] args) {
  5.                 int arr[] = { 6, 2, 9, 3, 12, 1 };
  6.                 System.out.println("原数组:");
  7.                 printArray(arr);
  8.                 System.out.println();
  9.                 System.out.println("排序过程:");
  10.                 bubbleSort(arr);
  11.                 System.out.println("排序结果:");
  12.                 printArray(arr);
  13.         }

  14.         // 冒泡排序算法
  15.         public static void bubbleSort(int[] arr) {
  16.                 for (int x = 0; x < arr.length; x++) {
  17.                         for (int y = 0; y < arr.length - x - 1; y++) {
  18.                                 if (arr[y] > arr[y + 1]) {
  19.                                         swap(arr, y, y + 1);
  20.                                 }
  21.                         }
  22.                         printArray(arr);
  23.                         System.out.println();
  24.                 }
  25.         }

  26.         // 数组元素交换位置
  27.         public static void swap(int[] arr, int x, int y) {
  28.                 arr[x] = arr[x] ^ arr[y];
  29.                 arr[y] = arr[x] ^ arr[y];
  30.                 arr[x] = arr[x] ^ arr[y];
  31.         }

  32.         // 打印数组
  33.         public static void printArray(int[] arr) {
  34.                 System.out.print("[");
  35.                 for (int x = 0; x < arr.length; x++) {
  36.                         if (x != arr.length - 1)
  37.                                 System.out.print(arr[x] + ",");
  38.                         else
  39.                                 System.out.print(arr[x] + "]");
  40.                 }
  41.         }
  42. }
复制代码


运行下看看`
作者: 踏雪风暴    时间: 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