黑马程序员技术交流社区

标题: 一个冒泡排序的问题 [打印本页]

作者: 吴扬 时间: 2012-6-19 20:04
标题: 一个冒泡排序的问题
本帖最后由吴扬于 2012-6-20 00:03 编辑

初学者，自己尝试着写了下冒泡排序的算法，但是还是出现了一点问题

public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[]{5,3,2,6,12,10,9,11};
bubbleSort(arr);
for(int i =0; i < arr.length; i++)
{
System.out.print(arr[i]+" ");
}
}
public static void bubbleSort(int[] arr)
{
for(int i = 0; i < arr.length; i++)
{
for(int j = i; j < arr.length-1; j++) //这里j的初始值应该是0，而不是i
{
if(arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}

复制代码

程序运行之后的结果是3 2 5 6 9 10 11 12，后面发现是自己在第二层循环的时候j的初始值错了，应该是从0开始
为什么如果j的初始值是i的话就会出现上面的运行结果呢？

作者: 余银桂 时间: 2012-6-19 20:10
本帖最后由余银桂于 2012-6-19 20:24 编辑

如果j的初始值是i的话第一次内层循环结束的时候，3已经排到第一位了
但是第一次内层循环结束的时候，由于i自增了
而此时3的角标是0，i自增之后从1开始
所以此时3就没有参内层循环的比较
没有参加内存循环的比较

帮楼主改了一下，供参考

public static void main(String[] args) {
int[] arr = new int[]{5,3,2,6,12,10,9,11};
bubbleSort(arr);
for(int i =0; i < arr.length; i++)
{
System.out.print(arr[i]+" ");
}
}
public static void bubbleSort(int[] arr)
{
for(int i = 0; i < arr.length-1; i++)
{
for(int j = i; j < arr.length; j++) //这里j的初始值应该是0，而不是i
{
if(arr[i] > arr[j])
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
}

复制代码

作者: 胡大强 时间: 2012-6-19 20:15
int temp,i,j;
for(i=0;i<a.length;i++) //一共要做a.length趟，每趟保证可一把最大的数放到最后
for(j=0;j<a.length-i-1;j++) //每趟将从0～a.length-i-1之间每两个数相互比较，共比较a.length-i次
{
}

作者: 唐辉辉 时间: 2012-6-19 20:19
j=i; 外部循环每循环一次，j的值都不一样。第一次是0，第二次是1，第三次2........

作者: 王晓新 时间: 2012-6-19 20:19

public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[]{5,3,2,6,12,10,9,11};
bubbleSort(arr);
for(int i =0; i < arr.length; i++)
{
System.out.print(arr[i]+" ");
}
}
public static void bubbleSort(int[] arr)//这才是冒泡排序
{
for(int i = 0; i < arr.length; i++)
{
for(int j =0; j < arr.length-i-1; j++)
{
if(arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}

复制代码

作者: 薄炳鑫 时间: 2012-6-19 20:25
D:\1111.jpg
这是运行的结果出现过程，他每次都是从自身开始往后比较。

1111.jpg (7.15 KB, 下载次数: 39)

作者: 张华廷 时间: 2012-6-19 20:36
public class diyitian {

public static void main(String[] args)
{
int[] arr = new int[]{5,3,2,6,12,10,9,11};
bubbleSort(arr);
for(int i =0; i < arr.length; i++)
{
         System.out.print(arr[i]+" ");
}
}

public static void bubbleSort(int[] arr)
{
for(int i = 0; i < arr.length-1; i++)
{
         for(int j = 0; j < arr.length-1; j++)  //这里j的值是0，不是j=i，结果错误。j=0后就排序正确。

                  if(arr[j] > arr[j+1])
                  {
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                  }
         }
}
}

}

作者: 王月 时间: 2012-6-19 20:40
本帖最后由王月于 2012-6-19 20:44 编辑

因为外循环控制的是整体循环的次数，内循环控制比较的次数，如果内循环for(int j = i; j < arr.length-1; j++) 这样写，
那么第二次循环就是从arr[1]和arr[2]开始比的，把arr[0]忽略了，所以循环结束后 3 肯定在首位置，因为他就参加了一次比较。

还有建议LZ把内循环中 j 的取值范围这样写，j<arr.length-1-i;可以减少比较的次数，提高效率，但是结果还是正确的。
LZ再理解一下冒泡排序的原理
在冒泡排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以每一轮循环后，会得到这一轮的最大数，从后向前从大到小排序。

作者: 李伟 时间: 2012-6-19 20:44
      public static void bubbleSort(int[] arr)
      {
            for(int i = 0; 改成i < arr.length-1; i++)//[b]这个是外循环，冒泡排序是相邻两个元素比较，循环次数是arr.length-1，应改成i<arr.length-1
         {
                     for(int j = i; 改成j < arr.length-1-i; j++)  //这里j的初始值应该是0，而不是i//这个是内循环，每次都要从0角标开始比较，所以是0
                     {
                              if(arr[j] > arr[j+1])
                              {
                                    int temp = arr[j];
                                    arr[j] = arr[j+1];
                                    arr[j+1] = temp;
                              }
                     }
            }
      }

}

作者: 郑冬 时间: 2012-6-19 20:55

      public static void sort(long[] arr) {

   for(int i = 0; i < arr.length - 1; i++) //这个for循环是外循环，冒泡排序是比较两个相邻的元素，比较的次数是arr.length-1    {
         for(int j = arr.length - 1; j > i; j--) //这个for循环就有很多表示方法了
         {
            if(arr[j] < arr[j - 1])
            {

               int tmp = arr[j];
                  arr[j] = arr[j - 1];
                  arr[j - 1] = tmp;
            }
         }
      }
}
}

作者: 李文龙 时间: 2012-6-19 21:12
楼上说的都对，但是想来楼主可能还没大搞懂冒泡是什么意思。
不知见过鱼吐泡泡没有，泡泡从下往上一点一点的飘到最上面。这算法是每次从最下面的记录开始，对每两个相邻的数据进行比较然后交换，进行下一次的排序。
for(int i = 0; i < arr.length; i++)
for(int j = i; j < arr.length-1; j++)
你的程序原先是这样，我直接用数组下标来表示，先是0和1,1和2,2和3,3和4.......一趟比较完后，数组元素变为3,2,5,6,9,10,11,12
第二趟，i值变为1，比较元素下标为1和2,2和3,3和4....... 这时你会发现，每个前边的元素都比后边要小，因为数组下标是从1开始的，所以不会发生替换，
第三趟，i值变为2，维持上述结果不变....直至循环结束.......
说到这里，不知楼主对于程序了解了不，冒泡的比较有点类似于找最值，每一次排序完成，要找到一个最大值或者最小值，放在数组的最前边，当然也可以是最后边，看你程序怎么写了，所以，内部循环j的值得从0开始

作者: 孙飞 时间: 2012-6-19 22:01
因为内循环的每一次比较都是从0角标开始的，每循环一次就会有一个最大的值跑到此次循环的最大角标位，所以j的初始值应该是0代表每一次从0开始，如果你j=i的话，当i=1时，内循环就是直接从角标为1的位置开始比较，就没有对0角标位上的值进行比较，还有因为每内循环一次就会有一个最大值在当次循环的最大角标上，下次还循环的时候就不用参与比较了，而且下面的if语句应该是
if(arr[j]>arr[j+1])
{
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
因为是arr[j]和arr[j+1]比较，所以应该是j<arr.length-x-1可以节省运算量

作者: 胡卿 时间: 2012-6-19 22:13

public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[]{5,3,2,6,12,10,9,11};
bubbleSort(arr);
for(int i =0; i < arr.length; i++)
{
System.out.print(arr[i]+" ");
}
}
public static void bubbleSort(int[] arr)
{
for(int i = 0; i < arr.length; i++)
{
for(int j = i; j < arr.length-1; j++) //这里如果j=i的话，那么外层循环i 的自增会影响到内层循环 J的值，从而是内层循环次数变少
{
if(arr[j] > arr[j+1]) /*例如，如果 i=arr.length-1时，那么j也就等于arr.length-1，那内层还怎么循环呢，所以楼主要仔细看看循环嵌套方面的知识点*/
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}

复制代码

作者: 吴扬 时间: 2012-6-20 00:02
谢谢大家的解答，我已经找到问题了，当j的初始值如果为i，第一次循环结束之后，3就排在角标位0的位置了，当i自增为1的时候，角标为0的元素就没有参加比较，所以3就排在第一位了。

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

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