package jichuban;

//基础班001
public class d1 {



    //选择排序
    public static void selectsorted(int[]arr) {
        if(arr==null||arr.length<2) {
            return;
        }
        for(int i=0;i<arr.length;i++) {
            int min=i;

            for(int j=i+1;j<arr.length;j++) {
                min=arr[min]<arr[j]?min:j;
            }

            swap(arr,i,min);

        }
    }

    //冒泡排序
    public static void bubblesorted(int[]arr) {
        if(arr==null||arr.length<2) {
            return;
        }

        for(int i=arr.length-1;i>=0;i--) {
            for(int j=0;j<i;j++) {
                if(arr[j]>arr[j+1]) {
                    swap(arr,j,j+1);
                }
            }
        }
    }

    //插入排序
    public static void insertsorted(int[]arr) {
        if(arr==null||arr.length<2) {
            return;
        }
        for(int i=1;i<arr.length;i++) {
            for(int j=i;j>0;j--) {
                if(arr[j]<arr[j-1]) {
                    swap(arr,j-1,j);
                }
            }
        }
    }

    //二分查找一个数的位置：数组有序
    public static int erfenchazhao(int[]arr,int num) {
        int l=0;
        int r=arr.length-1;
        int mid=-1;
        while(l<=r) {
            mid=l+(r-l)>>1;
            if(arr[mid]>num) {
                r=mid-1;
            }else if(arr[mid]<num) {
                l=mid+1;
            }else {
                return mid;
            }
        }
        return mid;
    }

    //二分，找>=value最左的位置
    public static int getleft(int[]arr,int num) {

        int l=0;
        int r=arr.length-1;
        int left=-1;

        while(l<=r) {
            int mid=l+(r-l)>>1;
            if(arr[mid]>=num) {
                r=mid-1;
                left=mid;
            }else {
                l=mid+1;
            }
        }

        return left;
    }

    //二分，找<=value最右的位置
    public static int getright(int[]arr,int num) {
        int l=0;
        int r=arr.length-1;
        int right=-1;

        while(l<=r) {
            int mid=l+(r-l)>>1;
            if(arr[mid]<=num) {
                l=mid+1;
                right=mid;
            }else {
                r=mid-1;
            }
        }

        return right;
    }


    //二分，找局部最小
    /*
     局部最小问题：
1>  o位置的数比1位置小，0位置是局部最小

2> n位置数比n-1位置小，n位置是局部最小

3> i位置的数比i-1和i+1的位置小，i位置是局部最小

**无序数组，任意两个相邻的数不相等，返回一个局部最小的位置。**
     */
    public static int getjumin(int[]arr) {
        if(arr==null||arr.length<2)){
            return -1;
        }

        if(arr[0]<arr[1]) {
            return 0;
        }
        if(arr[arr.length-1]<arr[arr.length-2]) {
            return arr.length-1;
        }

        int l=1;
        int r=arr.length-2;
        while(l<=r) {
            int mid=l+(r-l)>>1;
            if(arr[mid]<arr[mid-1]&&arr[mid]<arr[mid+1]) {
                return mid;
            }else if(arr[mid]>arr[mid-1]) {
                r=mid-1;
            }else {
                l=mid+1;
            }
        }
        return l;
    }

    //异或运算:一种数出现了奇数次，找出这个数
    public static int getji(int[]arr) {
        int result=0;
        for(int i=0;i<arr.length;i++) {
            result^=arr[i];
        }
        return result;
    }

    //异或运算：提取最右边的1
    public static int getone(int num) {
        return num&(~num+1);
    }

    //异或运算：两种 数出现了奇数次,找出来
    public static void getji2(int[]arr) {
        int r1=0;
        for(int i=0;i<arr.length;i++) {
            r1=r1^arr[i];
        }
        //假设为a b 则 r=a^b  a b 不相等 r!=0
        //以最右边的1为标准将数组分开
        int rightone=r1&(~r1+1);    
        int r2=0;

        for(int i=0;i<arr.length;i++) {
            if((arr[i]&rightone)==0) {//这位上为0
                r2^=arr[i];
            }
        }
        //此时r2 是 a 或 b
        int r3=r1^r2;//找出另外一个数
        System.out.println(r2+" "+r3);
    }

    //异或运算：计算一个数二进制中1的个数
    public static int getyinum(int num) {

        int count=0;
        while(num!=0) {
            int rone=num&(~num+1);
            num^=rone;
            count++;
        }
        return count;
    }



    //交换1
        public static void swap(int[]arr,int l,int r) {
            if(l==r) {
                return;
            }
            arr[l]=arr[l]^arr[r];
            arr[r]=arr[l]^arr[r];
            arr[l]=arr[l]^arr[r];
        }
        //交换2
        public static void swap2(int[]arr,int l,int r) {
            if(l==r) {
                return;
            }
            arr[l]=arr[l]+arr[r];
            arr[r]=arr[l]-arr[r];
            arr[l]=arr[l]-arr[r];
        }
        //交换3
        public static void swap3(int[]arr,int l,int r) {
            if(l==r) {
                return;
            }
            int temp=arr[l];
            arr[r]=arr[l];
            arr[l]=temp;
        }

        //遍历数组
        public static void printarr(int[]arr) {
            for(int i=0;i<arr.length;i++) {
                System.out.println(arr[i]);
            }

        }

}