java基础知识4--数组，排序，二分查找

数组：

import java.io.*;
class Testdog 
{
    public static void main(String[] args) throws Exception
    {
        Dog dogs[] = new Dog[4];
        float sumWeight=0;
        //给狗赋值
        //从控制台输入各个狗的信息
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        for(int i=0;i<4;i++)
        {
            dogs[i]=new Dog();
            System.out.println("请输入第"+(i+1)+"只狗名：");
            String name = br.readLine();
            //将名字赋给对象
            dogs[i].setName(name);
            System.out.println("请输入狗的体重：");
            String s_weight=br.readLine();
            //将String转成float
            float weight=Float.parseFloat(s_weight);
            sumWeight+=weight;
            //将weight赋给对象；
            dogs[i].setWeight(weight);
        }
        //计算平均值
        System.out.println("总体重："+sumWeight+"  平均体重："+sumWeight/dogs.length);

    }
}
//定义一个狗类
class Dog
{
    private String name;
    private float weight;
    public void setName(String name)
    {
        this.name=name;
    }
    public void setWeight(float weight)
    {
        this.weight=weight;
    }
    public String getName(String name)
    {
        return name;
    }
    public float getWeight(float weight)
    {
        return weight;
    }

}

 字符串相等用equals，“==”比较的是地址。

排序：

1.内部排序：将要处理的所有数据都加载到内部存储器中进行排序。

   包括（交换式排序法，选择排序法和插入式排序法）；

import java.util.*;
class Sort 
{
    
    public static void main(String[] args) 
    {
        int len=10;
        int arr[]=new int[len];
        for(int i=0;i<len;i++)
        {
            arr[i]=(int)(Math.random()*10000);
        }

        SortFun bubble = new SortFun();

        Calendar cal = Calendar.getInstance();
        System.out.println("排序前："+cal.getTime());

        //bubble.bubblesort(arr);//复合对象,传简单对象不会改变
        //bubble.selectsort(arr);
        //bubble.insertsort(arr);
        bubble.quicksort(arr,0,arr.length-1);

        System.out.println("排序后："+cal.getTime());


        for(int i=0;i<arr.length;i++)
        System.out.println(arr[i]);
    }
}

class SortFun
{
    //冒泡排序  n*n
    public void bubblesort(int args[])
    {
        int temp=0;
        for(int i=0;i<args.length-1;i++)
        {
            for(int j=0;j<args.length-1-i;j++)
            {
                if(args[j]>args[j+1])
                {
                    temp=args[j];
                    args[j]=args[j+1];
                    args[j+1]=temp;
                }
            }
        }
    }
    //选择排序   n*n
    public void selectsort(int arr[])
    {
        int min=0;
        int t=0;
        for(int i=0;i<arr.length-1;i++)
        {
            min=i;
            //找到剩下数中最小数的下标
            for(int j=i+1;j<arr.length;j++)
            {
                if(arr[j]<arr[min])
                {
                    min=j;
                }
            }
            //不是同一个数则交换
            if(i!=min)
            {
                t=arr[min];
                arr[min]=arr[i];
                arr[i]=t;
            }
        }
    }

    //插入排序  n*n
    public void insertsort(int arr[])
    {
        int i=0;
        int j=0;
        for(i=1;i<arr.length;i++)
        {
            int temp=arr[i];
            for(j=i;j>0&&arr[j-1]>temp;j--)
            {
                arr[j]=arr[j-1];
            }
            arr[j]=temp;
        }
    }

    //快速排序  n*log2N
    public void quicksort(int arry[],int left,int right)
    {
        int i=left,j=right,key=arry[left];
        while(i<j)
        {
            while(i<j&&arry[j]>=key) j--;
            arry[i]=arry[j];
            while(i<j&&arry[i]<=key) i++;
            arry[j]=arry[i];
        }
        arry[i]=key;
        if(i-left>0) quicksort(arry,left,i-1);
        if(right-i>0) quicksort(arry,i+1,right);
    }
　　//堆排序
　　//shell排序
　　//二叉树排序
　　//合并排序（外部排序的常用方法）

}

 2.外部排序：数据量过大，需要借助外部存储进行排序，包括（合并排序和直接合并排序法）。

 各种排序的时间复杂度：

查找：

1.顺序查找

2.二分查找（配合排序）

import java.io.*;

class  binarySearch
{
    public static void main(String[] args) throws Exception
    {
        int arr[]=new int[]{1,3,5,7,9,10,11,12,16};
        Search se = new Search();
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        System.out.println("请输入要查找的值：");
        String s_ans = br.readLine();
        int ans = Integer.parseInt(s_ans);
        System.out.println(se.Fun(arr,ans));
    }
}

class Search
{
    public int Fun(int []arr,int ans)
    {
        int low=0;
        int high=arr.length-1;
        while(low<=high)
        {
            int middle=(low+high)/2;
            if(ans==arr[middle])
            {
                return middle;
            }
            else if(ans<arr[middle])//在前半段
            {
                high=middle-1;
            }
            else//在后半段
            {
                low=middle+1;
            }
        }
        return -1;
    }
}