黑马程序员技术交流社区

标题: 一个数组元素排序问题，看看谁能找出原因 [打印本页]

---

作者: EYE_SEE_YOU    时间: 2013-8-23 21:02
标题: 一个数组元素排序问题，看看谁能找出原因

1. 
   
2. public class haha
   
3. {
   
4.         public static void main(String[]args)
   
5.         {
   
6.                 int []arr={3,1,6,4,8,2,9,65,1,24,61};
   
7.                 maopao(arr);
   
8.                 dayin(arr);
   
9.         }
   
10.         public static void maopao(int [] arr)
    
11.         {
    
12.                 for (int x=0;x<arr.length-1 ;x++ )
    
13.                 {
    
14.                         int temp=0;
    
15.                         for (int y=0; y<arr.length-x-1;y++ )
    
16.                         {
    
17.                                 if (arr[temp]<arr[y+1])
    
18.                                 {temp=y+1;
    
19.                                        
    
20.                                 }
    
21.                         }
    
22.                         zhihuan(arr,temp,arr.length-x-1);
    
23.                 }
    
24.         }
    
25.         public static void dayin(int[]arr)
    
26.         {
    
27.                 for (int x=0;x<arr.length ;x++ )
    
28.                 {
    
29.                                 System.out.println(arr[x]);
    
30.                 }
    
31.         }
    
32.         public static void zhihuan(int[]arr,int x,int y)
    
33.         {
    
34.                 arr[x]=arr[x]^arr[y];
    
35.                 arr[y]=arr[x]^arr[y];
    
36.                 arr[x]=arr[x]^arr[y];
    
37.         }
    
38. }

复制代码

这算是冒泡排序吧，试试看你们打印的时候会不会出现0

---

作者: gulup    时间: 2013-8-23 21:33


        public static void zhihuan(int[]arr,int x,int y){
                    if(arr[x] != arr[y]){
                            arr[x]=arr[x]^arr[y];   
                            arr[y]=arr[x]^arr[y];
                            arr[x]=arr[x]^arr[y];
                    }
        }

异或运算的陷阱，你数组里面有两个1，1 ^ 1得0.所以就有0咯。

---

作者: 行如止水    时间: 2013-8-23 22:22
为什么不用类集或是Collections类呢？

---

作者: litaojisuanji    时间: 2013-8-23 22:49
可用通过异或运算交换两个数，而不需要任何的中间变量。 如下面:

void exchange(int &a, int &b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}

然而，这里面却存在着一个非常隐蔽的陷阱。

通常我们在对数组进行操作的时候，会交换数组中的两个元素，如exchang(&a[i], &b[j]), 这儿如果i==j了（这种情况是很可能发生的)，得到的结果就并非我们所期望的。

void main()
{
   int a[2] = {1, 2};
   exchange(a[0], a[1]); //交换a[0]和a[1]的值
   printf("1---a[0]=%d a[1]=%d\n", a[0], a[1]);
   exchange(a[0], a[0]); //将a[0]与自己进行交换
   printf("2---a[0]=%d a[1]=%d\n", a[0], a[1]);
}
上面那段测试代码的输出是：
1---a[0]=2 a[1]=1
2---a[0]=0 a[1]=1
很意外吧，第一次的交换正确的执行了，但是第二次调用exchange的时候却将a[0]置为了0. 仔细分析，不难发现，这正是我们在exchange里面用异或实现交换所造成的。如果输入a和b是同一个数，exchange里面代码相当于：

a ^= a;
a ^= a;
a ^= a;
成了a做了3次于自己的异或，其结果当然是0了。

既然这样，我们就不能够在任何使用交换的地方采用异或了，即使要用，也一定要在交换之前判断两个数是否已经相等了，如下：

    void exchange(int &a, int &b)
    {
        if(a == b) return; //防止&a，&b指向同一个地址；那样结果会错误。
        a ^= b;
        b ^= a;
        a ^= b;
    }

---

作者: gulup    时间: 2013-8-23 22:54
楼上的代码。。。不是JAVA的吧？

---

作者: 熊纪达    时间: 2013-8-23 22:56
仅对于该代码来说，应该 是x=y=2的这次交换，导致arr【2】=0

---

作者: 杨增坤    时间: 2013-8-24 09:43


我感觉是：
public static void maopao(int[] arr) {
                for (int x = 0; x < arr.length - 1; x++) {
                        int temp = 0;
                        for (int y = 0; y < arr.length - x - 1; y++) {
                                if (arr[y] < arr[y + 1]) {
                                        temp = y + 1;
                                        zhihuan(arr, temp, y);
                                }
                        }

                }
        }


你写的是，不管符不符合条件，都要置换，必须是符合条件的话，才可以置换，
对于冒泡的话，比较的是相邻的两个元素，而不是永远和第一比较，所以交换的话，也是交换的是相邻元素，
运行结果：65
61
24
9
8
6
4
3
2
1
1
我这样理解可以吗？？

---

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

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