数组及常见操作

我会带着你远行 2022-08-21 05:51 177阅读 0赞

class ArrayDemo 
    {
        public static void main(String[] args) 
        {
       //格式1：不明确具体数据
            int [] arr=new int [3];
            //arr=null;//原本指向数组的arr指向空，切断地址联系
            System.out.println(arr);//显示[I@2a139a55 
            //@为分界线，左边[表示数组型，I表示Int，2a139a55表示其在内存里的哈希值，用于在不知对象类型时，测试其类型
    
            //格式2
            int [] arr2 = new int [] {
       1,2,3,4};
            int [] arr3 = {
       21,35,56,2,48,101};
            printArr(arr2);//输出数组
            System.out.println("Max = "+maxArray(arr3));//输出最大值
            printArr(arr3);
            System.out.println(getIndex(arr3,2));//顺序查找
            System.out.println(getIndex(arr3,3));// 输出-1
    
            //sortChose(arr3);//选择排序
    
            //sortBubble(arr3);//冒泡排序
    
            sortSelect_2(arr3);//改良选择排序
            printArr(arr3);
            System.out.println(binarySearch(arr3,35));//折半查找
            System.out.println(binarySearch(arr3,36));//折半查找无此元素输出-1
            System.out.println(halfSearch(arr3,35));
            System.out.println(halfSearch(arr3,36));
        }
    
    //数组查找_顺序查找，效率低，但对数据无要求
    public static int getIndex(int [] arr, int key)
    {
        for (int i = 0;i<arr.length ;i++ )
        {
            if (key==arr[i])
            {
                return i;
            }
        }
        return -1;//查找无此元素
    }
    
    //折半查找（二分查找），要求数组有序
    public static int binarySearch(int [] arr,int key)
    {
        int right = 0,left = arr.length-1,mid ;
        while (right<=left)
        {
            mid = (right+left)>>1;
            if (key<arr[mid])
                left = mid - 1;
            else if (key>arr[mid])
                right = mid +1;
            else 
                return mid;
        }
        return -1;//没找到
    }
    
    //折半查找的另一种写法
    public static int halfSearch( int [] arr, int key )
    {
        int right = 0,left = arr.length-1,mid = (right + left)>>1  ;
        while (key!=arr[mid])
        {
            if (key<arr[mid])
                left = mid - 1;
            else if (key>arr[mid])
                right = mid +1;
            if(right>left)
                return -1;
            mid = (right + left)>>1  ;
        }
        return mid;
    }
    
    
    //chose排序2，改良版选择排序
    public static void sortSelect_2(int [] arr)
        {
        for (int i = 0;i<arr.length -1;i++ )
        {
    
            int index=i;//记录一轮比较下来的最小值的下标
            for (int  j = i+1;j <arr.length ;j++ )
            {
                if(arr[index]>arr[j])
                {
                    index=j;//记录最小值下标
                }
            }
            //一轮结束时交换
            if (index!=i)
            {
                swap(arr,index,i);
            }   
        }
    }
    
    
        //冒泡排序
        public static void sortBubble(int [] arr)
    {
            //方法一
            for (int i = 0;i<arr.length-1 ;i++ )//-1最后一个不用比
            {
                for (int j = 0; j<arr.length-1-i ;j++ )//-1避免最后一个比较时超出下标范围
                {
                    if (arr[j]>arr[j+1])//相邻的比较,不能用j++,也不能用++j
                    {
                        swap(arr,j,j+1);
                    }
    
                }
            }
    
            /* //方法二 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 sortChose(int [] arr)
            {
            for (int i = 0 ;i<arr.length-1 ;i++)
            {
                for (int j = i+1;j<arr.length ;j++ )
                {
                    if (arr[i]>arr[j])
                    {
                        swap(arr,i,j);
                    }
                }
            }
            }
    
        //遍历输出数组
        public static void printArr( int [] arr)
            {
            System.out.print("[ ");
    
            for (int i = 0;i<arr.length ;i++ )
            {
                if (i==arr.length-1)
                    System.out.println(arr[i]+" ]");
                else 
                    System.out.print(arr[i]+", ");
            }
            }
    
        //输出数组中最大值
    public static int maxArray (int [] arr){
        //方法一，记录最大数据
        int maxElement = arr[0];
        for (int i = 0;i<arr.length ;i++ )
            {
            if( arr[i]>maxElement)
                maxElement=arr[i];
            }
            return maxElement;
    //方法二，记录下标
    /* int maxIndex=0; for (int i = 0;i<arr.length ;i++ ) { if(arr[i]>arr[maxIndex]) maxIndex=i; } return arr[maxIndex]; */
          }
    
        //swap函数.交换
          public static void swap(int [] arr,int a,int b)
        {
              int temp = arr[a];
              arr[a] = arr[b];
              arr[b] = temp;
         }
    }