Q004_让奶牛飞_solution

[atomiCat]

Question_ID: Q004

Language: java

Time Cost: 30-mins

Time Complexity: o(n)

Solution

My Code

    //第一个版本
   static void order(int [] in){
        boolean small=false;
        for(int i=1;i<in.length;i++){
            if(small){
                if(in[i]>in[i-1])
                    exchange(in,i,i-1);
            }else{
                if(in[i]<in[i-1])
                    exchange(in,i,i-1);
            }
            small=!small;
        }
    }
   //第二个版本
    static void order(int[] in) {
        for (int i = 1; i < in.length; i++) {
            if ((i & 1) == 0 ? in[i] > in[i - 1] : in[i] < in[i - 1])
                exchange(in, i, i - 1);
        }
    }
    static void exchange(int[] a,int x,int y){
        int t=a[x];
        a[x]=a[y];
        a[y]=t;
    }

Other

[atomiCat]

受palayutm启发，第二个版本的 if 还可以写成 ((i & 1) == 0) ^ (in[i] < in[i - 1])

[isaacpei]

来个思路和证明啥的呀~ 毕竟光放代码怎么证明正确性