//数组打印，数组排序，折半查找。
class ShuZuPaiXu
{
        //选择排序
        public static void paiXu(int[] arr)
        {
                for(int x = 0;x < arr.length-1;x++)
                {
                        for(int y = x+1;y<arr.length;y++)
                        {
                                if(arr[x]<arr[y])
                                {
                                        /*
                                        int temp = arr[x];
                                        arr[x] = arr[y];
                                        arr[y] = temp;
                                        */
                                        swap(x,y);
                                }
                        }
                }       
        }
       
        //冒泡排序
        public static void maoPao(int[] arr)
        {
                for(int x = 0;x<arr.length-1;x++)
                {
                        for(int y = 0;y<arr.length-x-1;y++)//-x，让每一次的元素减少；-1，避免角标越界。
                        {
                                if(arr[y]>arr[y+1])
                                {
                                        /*
                                        int temp = arr[y];
                                        arr[y] = arr[y+1];
                                        arr[y+1] = temp;
                                        */
                                        swap(arr,y,y+1);
                                }
                        }
                }
        }
       
        //主函数，入口。
        public static void main(String[] args)
        {
        int[] arr = {3,6,2,7,4,9,1};       
                        daYin(arr);//打印输入数组
                        //paiXu(arr);选择排序
                        maoPao(arr);//冒泡排序
        /*
        int jiaoBiao = chaZhao(arr,9);
                System.out.println("jiaoBiao="+jiaoBiao);
        */
                        daYin2(arr,9);//打印要查找数字的角标
                        daYin(arr);//打印排序数组
               
        }
       
        //数组打印
        public static void daYin(int[] arr)
        {
                System.out.print("[");
                for(int x = 0;x<arr.length;x++)
                {
                        if(x==arr.length-1)
                                System.out.print(arr[x]+"]");
                        else
                                System.out.print(arr[x]+",");
                }
                System.out.println();
        }
       
        //简化代码
        public static void swap(int[] arr,int a,int b)
        {
                int temp = arr[a];
                        arr[a] = arr[b];
                        arr[b] = temp;
        }
       
        //打印要查找数字的角标
        public static void daYin2(int[] arr,int shuRu)
        {
                int jiaoBiao = chaZhao1(arr,shuRu);
                System.out.println("jiaoBiao="+jiaoBiao);
        }
       
        //对进行数组折半查找，但数组必须是有序的。
        public static int chaZhao1(int[] arr,int key)
        {
                int min,max,mid;
                min = 0;
                max = arr.length-1;
                mid = (min+max)/2;
                while(key!=arr[mid])
                {
                        if(key>arr[mid])
                        {
                                min = mid+1;
                        }
                        else if(key<arr[mid])
                        {
                                max = mid-1;
                        }
                        if(min>max)
                        {
                                return -1;
                        }       
                        mid = (min+max)/2;
                }
                return mid;
        }

        //折半查找的另一种方式
        public static int chaZhao2(int[] arr,int key)
        {
                int min,max,mid;
                min = 0;
                max = arr.length-1;
                while(min<=max)
                {
                        mid = (min+max)>>1;
                        if(key>arr[mid])
                                min = mid+1;
                        else if(key<arr[mid])
                                max = mid-1;
                        else
                                return mid;
                }
                return -1;
        }
       
        /*
        基于折半查找，在一个有序数组中插入一个数，还保证数组有序。
        如果这个数存在，就在位置上插入，如果不存在，返回最小角标的值。
        */
        public static int chaZhao3(int[] arr,int key)
        {
                int min = 0,max = arr.length-1,mid;
                while(min<=max)
                {
                        mid = (min+max)>>1;
                        if(key>arr[mid])
                        {
                                min = mid+1;
                        }
                        else if(key<arr[mid])
                        {
                                max = mid-1;
                        }
                        else
                                return mid;
                }
                return min;
        }
}

//数组打印，数组排序，折半查找。
class ShuZuPaiXu
{
        //选择排序
        public static void paiXu(int[] arr)
        {
                for(int x = 0;x < arr.length-1;x++)
                {
                        for(int y = x+1;y<arr.length;y++)
                        {
                                if(arr[x]<arr[y])
                                {
                                        /*
                                        int temp = arr[x];
                                        arr[x] = arr[y];
                                        arr[y] = temp;
                                        */
                                        swap(x,y);
                                }
                        }
                }       
        }
       
        //冒泡排序
        public static void maoPao(int[] arr)
        {
                for(int x = 0;x<arr.length-1;x++)
                {
                        for(int y = 0;y<arr.length-x-1;y++)//-x，让每一次的元素减少；-1，避免角标越界。
                        {
                                if(arr[y]>arr[y+1])
                                {
                                        /*
                                        int temp = arr[y];
                                        arr[y] = arr[y+1];
                                        arr[y+1] = temp;
                                        */
                                        swap(arr,y,y+1);
                                }
                        }
                }
        }
       
        //主函数，入口。
        public static void main(String[] args)
        {
        int[] arr = {3,6,2,7,4,9,1};       
                        daYin(arr);//打印输入数组
                        //paiXu(arr);选择排序
                        maoPao(arr);//冒泡排序
        /*
        int jiaoBiao = chaZhao(arr,9);
                System.out.println("jiaoBiao="+jiaoBiao);
        */
                        daYin2(arr,9);//打印要查找数字的角标
                        daYin(arr);//打印排序数组
               
        }
       
        //数组打印
        public static void daYin(int[] arr)
        {
                System.out.print("[");
                for(int x = 0;x<arr.length;x++)
                {
                        if(x==arr.length-1)
                                System.out.print(arr[x]+"]");
                        else
                                System.out.print(arr[x]+",");
                }
                System.out.println();
        }
       
        //简化代码
        public static void swap(int[] arr,int a,int b)
        {
                int temp = arr[a];
                        arr[a] = arr[b];
                        arr[b] = temp;
        }
       
        //打印要查找数字的角标
        public static void daYin2(int[] arr,int shuRu)
        {
                int jiaoBiao = chaZhao1(arr,shuRu);
                System.out.println("jiaoBiao="+jiaoBiao);
        }
       
        //对进行数组折半查找，但数组必须是有序的。
        public static int chaZhao1(int[] arr,int key)
        {
                int min,max,mid;
                min = 0;
                max = arr.length-1;
                mid = (min+max)/2;
                while(key!=arr[mid])
                {
                        if(key>arr[mid])
                        {
                                min = mid+1;
                        }
                        else if(key<arr[mid])
                        {
                                max = mid-1;
                        }
                        if(min>max)
                        {
                                return -1;
                        }       
                        mid = (min+max)/2;
                }
                return mid;
        }

        //折半查找的另一种方式
        public static int chaZhao2(int[] arr,int key)
        {
                int min,max,mid;
                min = 0;
                max = arr.length-1;
                while(min<=max)
                {
                        mid = (min+max)>>1;
                        if(key>arr[mid])
                                min = mid+1;
                        else if(key<arr[mid])
                                max = mid-1;
                        else
                                return mid;
                }
                return -1;
        }
       
        /*
        基于折半查找，在一个有序数组中插入一个数，还保证数组有序。
        如果这个数存在，就在位置上插入，如果不存在，返回最小角标的值。
        */
        public static int chaZhao3(int[] arr,int key)
        {
                int min = 0,max = arr.length-1,mid;
                while(min<=max)
                {
                        mid = (min+max)>>1;
                        if(key>arr[mid])
                        {
                                min = mid+1;
                        }
                        else if(key<arr[mid])
                        {
                                max = mid-1;
                        }
                        else
                                return mid;
                }
                return min;
        }
}