黑马程序员技术交流社区

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

---

作者: 遮天    时间: 2014-4-1 10:41
标题: 关于冒泡排序问题


/*

        冒泡排序

*/

class Demo
{
        public static void main(String[] args)
        {
                int[] arr = {1,3,5,7,9,2,4,6,8};

                export(arr); //排序前输出
                sort(arr); //排序
                export(arr); //排序后输出
        }
               
        //排序函数
        public static void sort(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])
                                {        
                                                
                                        replace(arr, y, y+1);

                                }
                        }
                }
        }
               
        //输出函数
        public static void export(int[] arr)
        {
                for(int x=0; x<arr.length; x++)
                {
                        if(x!=arr.length-1)
                                System.out.print(arr[x]+",");
                        else
                                System.out.println(arr[x]);
                }
                        
        }
               
        //置换函数,设置第三方变量进行两个数的互换
        public static void replace(int[] arr, int x, int y)
        {
                int tem=arr[x];
                        arr[x]=arr[y];
                        arr[y]=tem;
        }
}


我想问的是在排序函数中
        
        //排序函数
        public static void sort(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])
                                {        
                                                
                                        replace(arr, y, y+1);

                                }
                        }
                }
        }




for(int x=0; x<arr.length-1; x++)

x<arr.length-1  为嘛要减 1  ？？？不减 1 也能运行啊？

求解释......

---

作者: 黄晓鑫    时间: 2014-4-1 10:45


因为最后一个不需要排序啊，排了就等于浪费资源。比如有六个人，小的人都往前面走，最后一个肯定就是最大的了，还需要排吗？

---

作者: MK_Chan    时间: 2014-4-1 11:38


为了让楼主更容易理解，我结合一下算法的步骤来解析一下吧。
冒泡排序的原理我就不用多讲了吧，楼主给出的“//排序函数”就是属于冒泡排序算法了。

第一个问题：x<arr.length-1  为嘛要减 1  ？
我们假设两种情况：
一、x<arr.length；
以开始的数组 int[] arr = {1,3,5,7,9,2,4,6,8};为例。
数组有9个元素，所以arr.length=9,所以x能达到的最多值为8。
当算法进行最后一次比较的时候：
我们看代码int y=0; y<arr.length-x-1;x取到最大值为8。
所以这个代码为y=0;y<0。显然这个循环条件是不成了的，所以不会进入循环里面的判断。
所以当y=0的时候：if(arr[y]>arr[y+1])也就是if(arr[0]>arr[1])是没有被执行的，也就是说这个冒泡排序是不完整的。

二、x<arr.length-1；
以开始的数组 int[] arr = {1,3,5,7,9,2,4,6,8};为例。
数组有9个元素，所以arr.length=9,所以x能达到的最多值为7。
当算法进行最后一次比较的时候：
我们看代码int y=0; y<arr.length-x-1;x取到最大值为7。
所以这个代码为y=0;y<1。显然这个循环条件成立，所以会进入循环里面的判断。
所以当y=0的时候：if(arr[y]>arr[y+1])也就是if(arr[0]>arr[1])被执行，算法完整，冒泡排序完成。

第二个问题：不减 1 也能运行啊？
程序是可以运行的，只是冒泡排序不完整，看第一种情况最后那里的解析。

【求加技术分 T 。T】

---

作者: victorsun    时间: 2014-4-1 18:05
这么解释吧，因为冒泡排序是数组中的前一个元素和后一个元素进行比较，那么，就如你刚刚所说，x<arr.length-1 ,首先，length是数组的长度，也就是数组中有效的参与排序比较的元素的个数，如果当x<arr.length，那么循环条件仍然满足，而x是从0开始计算，那么下一次比较的时候是不是就到了arr[length-1]和arr[length]比较？又因为数组下标最大值就是arr.length-1，那么此时，arr[length]编译系统就不认识了，就会出现角标越界异常。

---

作者: ╰青青子佩ˊゝ    时间: 2014-4-1 18:27
因为最后面就只剩一个了，一个跟自己比啊？没必要啊，所以最后那一个比较省了，所以减1

---

作者: z1342802487    时间: 2014-4-1 22:10
arr.length返回数组arr元素个数，而数组下标是从0开始的，所以数组arr最后一元素是数组元素个数减1，如果不减一的话会造成数组下标越界，很危险，因为编译器不检查数组下标时否越界，所以要注意这一点哦！

---

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

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