黑马程序员技术交流社区

标题: 冒泡排序 [打印本页]

作者: jagon    时间: 2014-3-13 11:29
标题: 冒泡排序
冒泡排序
public class BubbleSort {
    public static void main(String[] args) {
       int[] array={63,4,24,1,3,5};
       BubbleSort sorter=new BubbleSort();
       sorter.sort(array);
    }
    //冒泡排序
    public void sort(int[] array){
       for(int i=1;i<array.length;i++)      //为什么一定要是array.length,根本用不了判断那么多次,明明只判断了3次啊?
           for(int j=0;j<array.length-1;j++){
              if(array[j]>array[j+1]){
                  int temp=array[j];
                  array[j]=array[j+1];
                  array[j+1]=temp;
              }
           }
        showArray(array);   
    }
    //遍历数组,并输出数组的元素。
    public void showArray(int[] array){
       for(int i=0;i<array.length;i++){      
           System.out.print(array+"\t");
       }
       System.out.println();
    }
}
原排序:63,4,24,1,3,5
第一次排序:4 24  1  3  5 63
第二次排序:4 1  3  5  24 63
第三次排序:1 3  4  5  24 63
根本就用不了6次,3次就排完了!
为什么一定要是array.length,根本用不了判断那么多次,明明只判断了3次啊?

作者: 王浩龙    时间: 2014-3-13 11:49

  1.     //冒泡排序
  2.     //main函数是静态的,这里需要加上static
  3.     public static void sort(int[] array){

  4.        for(int i=0;i<array.length-1;i++)      
  5.             //这里是需要减去x的,因为每判断一次,最值已经出现在最右边了
  6.            for(int j=0;j<array.length-x-1;j++){

  7.               if(array[j]>array[j+1]){

  8.                   int temp=array[j];

  9.                   array[j]=array[j+1];

  10.                   array[j+1]=temp;

  11.               }

  12.            }  

  13.     }
复制代码
我看了一下你的代码,其中冒泡排序的地方写的有问题,我会在下面的代码中给出正确的。关于判断的次数的问题,这里是你给定的数组,排了三次你就可以看出数序排好了,但是当数组给的是不固定的时候你是不是就要需要那么多的判断次数了呢?

作者: l939    时间: 2014-3-13 12:01
咳咳,楼主,冒泡排序啊,你的那个之所以循环3次。。还是你的数组是固定的啊。
假设,定义个新的数组:{42,3,5,1,7,45,78,23,54,13}
使用冒泡排序:第一次: 3,5,1,7,42,45,23,54,13,78
                     第二次: 3,1,5,7,42,23,45,13,54,78
                     第三次: 1,3,5,7,23,42,13,45,54,78
                     第四次: 1,3,5,7,23,13,42,45,54,78
                     第五次: 1,3,5,7,13,23,42,45,54,78
结果,我需要5次才能完成,所以呢,楼主,当你不清楚定义的数组里的内容和长度的时候,你是不是需要获取一下数组的所有元素的值。然后再来进行判断啊?
作者: 2528870651    时间: 2014-3-13 17:57
l939 发表于 2014-3-13 12:01
咳咳,楼主,冒泡排序啊,你的那个之所以循环3次。。还是你的数组是固定的啊。
假设,定义个新的数组:{42, ...

说得好啊 !  你的数组太短了所以只执行了 3次!
作者: 一年_Hei    时间: 2014-3-13 19:26
楼主给的说法太牵强了吧。如果我用一个有循序的数组那就一次不用循环了,冒泡排序外循序的次数应该是array.length()-1次,因为最后一位就不用比了。
作者: Sage    时间: 2014-3-13 20:51
  1. public static void main(String[] args) {
  2.                 // 定义int类型的一维数组
  3.                 int[] array = { 63, 4, 24, 1, 3, 5 };
  4.                
  5.                 // 冒泡排序
  6.                 for (int i = 0; i < array.length - 1; i++) {
  7.                         for (int j = 0; j < array.length - 1 - i; j++) {
  8.                                 if (array[j] > array[j + 1]) {
  9.                                         array[j] = array[j + 1] - (array[j + 1] = array[j])
  10.                                                         + array[j];
  11.                                 }
  12.                         }
  13.                 }
  14.                 String arr = "["; // 数组字符串
  15.                
  16.                 // 循环遍历排序后的数组
  17.                 for (int i = 0; i < array.length; i++) {
  18.                         if (i < array.length - 1) {
  19.                                 arr += array[i] + ", ";
  20.                         } else {
  21.                                 arr += array[i];
  22.                         }
  23.                 }
  24.                 System.out.println(arr += "]");
  25.         }
复制代码

冒泡排序的中心在于每次循环,都会找到一个极值。
循环次数取决于数组长度和元素初始位置。
作者: 艮昕辶    时间: 2014-3-13 21:47
楼主冒泡排序的外层循环一定是排序数组的长度-1的
为什么
比如排序10 8 2 6 5 4 7 3 1 9
冒泡排序的思想就是先找到最大的10 把10放到第十的位置
然后在找第二大的9把9放到第九的位置
依次类推。。
找到第9大的2放到第2的位置
这个时候1就不用放了

整个的过程如同冒泡才叫冒泡排序
作者: nicholyx    时间: 2014-3-14 11:26
楼主的冒泡排序有点问题,改正之后我打印的结果是这样的:
[4, 24, 1, 3, 5, 63]
[4, 1, 3, 5, 24, 63]
[1, 3, 4, 5, 24, 63]
[1, 3, 4, 5, 24, 63]
[1, 3, 4, 5, 24, 63]
从结果可以看出,的确三次已经排序完了,但是第三次排序完成之后计算机并不知道后面的的数据是否已经排序好了,
所以还要进行比较,直到全部数据比较完成之后才算排序完成。举两个例子:
例子一:
原数组{6,5,4,3,2,1},排序结果如下
[5, 4, 3, 2, 1, 6]
[4, 3, 2, 1, 5, 6]
[3, 2, 1, 4, 5, 6]
[2, 1, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

例子二:原数组{1,2,3,4,5,6},排序结果如下
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

所以不管原来数组怎么样,在计算机中都是考虑最坏的情况的,就是例子一那样,所以比较次数都是arr.length-1次

修正后的代码如下:

  1. //冒泡排序
  2. public class BubbleSortDemo {
  3.     public static void main(String[] args) {
  4.        int[] array={63,4,24,1,3,5};
  5.        BubbleSortDemo sorter=new BubbleSortDemo();
  6.        sorter.bubbleSort(array);
  7.     }
  8.   
  9.         /*
  10.         给int数组进行冒泡排序
  11.         */
  12.         public  void bubbleSort(int[] arr) {
  13.                 for(int i = 0; i < arr.length-1; i++) {
  14.                         for(int j = 0; j < arr.length-i-1; j++) {
  15.                                 if(arr[j] > arr[j+1]) {
  16.                                         swap(arr, j, j+1);               
  17.                                 }                       
  18.                         }
  19.                         printArray(arr);
  20.                 }
  21.         }
  22.         /*
  23.         给int数组中元素进行位置的置换
  24.         */
  25.         private  void swap(int[] arr, int a, int b) {
  26.                 int temp = arr[a];
  27.                 arr[a] = arr[b];
  28.                 arr[b] = temp;
  29.         }

  30.         public void printArray(int[] arr) {
  31.                 System.out.print("[");
  32.                 for(int i = 0; i < arr.length; i++) {
  33.                         if(i < arr.length - 1) {
  34.                                 System.out.print(arr[i] + ", ");
  35.                         } else {
  36.                                 System.out.println(arr[i] + "]");
  37.                         }
  38.                                
  39.                 }
  40.         }
  41. }
复制代码

作者: 1014917278    时间: 2014-3-14 15:06
其实很简单的,冒泡的原理就是,每次选一个最大的放在最后面,这样再比较第二次,这次不用比较最后一个了,再找一个最大的,放到倒数第二位上,以此类推,就可以把数排好了
作者: daoyua    时间: 2014-3-14 17:25
搜索加判断和是否移动是两回事,你先要把所有的数字都和后面的对比判断,是否需要移动的,有些需要移动的,但是不移动的也要判断的,不判断怎么知道移动不移动




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