5、数组

为什么要有数组？

在生活当中，比如一箱牛奶有12包，你是整箱买还是单独买12包？一般情况下都是整箱购买，便于携带。
可以将数组理解为一个箱子，在数组里面可以存储同种数据类型的多个值，这样便于数据的使用。比如在进行方法的参数传递时，需要传递10个int类型的参数，如果没有数组的话，需要写10个参数非常麻烦，使用数组后，传递一个数组即可。

什么是数组？

• 数组是存储同一种数据类型多个元素的集合。也可以看成是一个容器。
• 数组里面既可以存储基本数据类型，也可以存储引用数据类型，但是只能存储同一种数据类型。
• 数组是一种简单的数据结构，线性的结构
• 数组一旦创建其长度是不可变的
• 数组是引用数据类型

数组的分类

• 一维数组
• 二维数组
• 三维数组
• 多维数组

如何定义数组？

示例：静态初始化一维数组

package com.sutaoyu.array;

public class array_01 {

    public static void main(String[] args) {
        int[] i = {64,128,216,512,1024,2048}; 
        String[] str = {"Java","Python","C++"};
        
        Object o1 = new Object();
        Object o2 = new Object();
        Object o3 = new Object();
        
        Object[] obj = {o1,o2,o3}; 
    }
}

1、一维数组

静态初始化数组

数组初始化就是为数组开辟连续的内存空间，并为每个数组元素赋予值。知道数组的首元素的内存地址，要查找的元素只要知道下标就可以快速的计算出偏移量，通过首元素内存地址加上偏移量可以快速计算出要查找元素的内存地址，通过内存地址快速定位该元素， 所以数组查找元素的效率较高。
注意：数组下标是从0开始的
下面代码演示了静态初始化一维数组，通过下标定位元素

package com.sutaoyu.array;

public class array_02 {
    public static void main(String[] args) {
        //静态初始化一个int类型的一维数组
        int[] Array = {2,4,8,16,32};
        
        //取得第一个元素，数组下标是从0开始的
        System.out.println(Array[0]);
        System.out.println(Array[1]);
        System.out.println(Array[2]);
        System.out.println(Array[3]);
        System.out.println(Array[4]);
        //ArrayIndexOutOfBoundsException，超出了数组的下标范围
        //System.out.println(intArray[5]);
        System.out.println("-------------------------");
        
        //取得元素个数
        System.out.println(Array.length);
        
        System.out.println("-------------------------");
        
        //遍历一维数组
        for(int i = 0;i < Array.length; i++) {
            System.out.println(Array[i]);
        }
        
        System.out.println("-------------------------");
        
        //将第2个元素修改成1024
        Array[1] = 1024;
        for(int i = 0;i < Array.length; i++) {
            System.out.println(Array[i]);
        }
        
    }
}

动态初始化数组

动态初始化数组,会先在堆内存中分配这个数组，并且数组中每一个元素都采用默认值。

package com.sutaoyu.array;

public class array_03 {
    public static void main(String[] args) {
        
        //动态声明一个int类型的数组，最多可以存储4个元素.
        int[] array = new int[4];
        
        for(int i = 0; i < array.length;i++) {
            System.out.println(array[i]);
        }
        
        System.out.println("---------------------");
        array[0] = 1024;
        array[1] = 1025;
        array[2] = 1026;
        array[3] = 1027;
        
        //遍历
        for(int i = 0; i < array.length;i++) {
            System.out.println(array[i]);
        }
        System.out.println("---------------------");
        
        //引用类型的数组
        Object[] obj = new Object[4];
        
        for(int j = 0;j < obj.length; j++) {
            Object o = obj[j];
            System.out.println(o);
        }
    }
}

如何选择数组的初始化方式？

• 如果在创建数组的时候，知道数组中应该存储什么数据，这个时候当然采用静态初始化方式。
• 如果在创建数组的时候，无法预测到数组中存储什么数据，只是先开辟空间，则使用动态初始化方式。

两者最终的内存分布都是一样的。

方法调用传递数组

package com.sutaoyu.array;

public class array_04 {
    public static void main(String[] args) {
        int[] i = {2,4,8,16,32};
        m1(i);
    }
    
    public static void m1(int[] a) {
        for(int i = 0;i < a.length; i ++) {
            System.out.println(a[i]);
        }
        
    }
}

 小练习：

1.获取一个int类型数组中的最大值

package com.sutaoyu.array;

public class array_05 {

    public static void main(String[] args) {
        int[] i = {1,3,34,53,23,14};
        int max = i[0];
        max = Max(i, max);
        System.out.println(max);
    }

    public static int Max(int[] i, int max) {
        for(int j = 1;j < i.length; j++) {
            if(max<i[j]) {
                max=i[j];
            }
        }
        return max;
    }

}

2.自己随意定义一个int类型的数组，然后进行循环数组完成对调

package com.sutaoyu.array;

public class array_06 {

    public static void main(String[] args) {
        int[] i = {1,2,3,4,5,6,7,8};
        for(int j = 0;j < i.length/2; j++) {
            int arg;
            arg = i[j];
            i[j] = i[i.length - 1 -j];
            i[i.length - 1 -j] = arg ;
        }
        for(int k = 0;k < i.length;k++) {
            System.out.print(i[k]);
            System.out.print(",");
        }

    }

}

2、main方法中String数组参数的作用

main方法中的String[] args是专门用来接收命令行参数的。

 public class MainTest01 {
        public static void main(String[] args){
            for(int i=0; i<args.length; i++){
                System.out.println(args[i]);
            }
        }

    }

上面程序编译好之后可以在执行时输入参数

• 在命令提示符里面使用java命令时，在类名后面可以输入多个参数：java MainTest01 monkey 1024 hello
• 在eclipse里面，右键run as—>Run configurations，选择Arguments，在program arguments里面输入monkey 1024 hello

小练习：

实现一个用户登录的功能，接收用户输入的用户名和密码，如果正确，则登录成功，否则登录失败。
用户名：admin
密码：sutaoyu01

package com.sutaoyu.array;

public class String_args {

    public static void main(String[] args) {
        if(args.length != 2) {
            System.out.println("请重新输入用户名和密码！");
            return;
        }
        String name = args[0];
        String password = args[1];
        if("admin".equals(name) && "sutaoyu01".equals(password)) {
            System.out.println("输入正确");
        }else {
            System.out.println("请重新输入");
        }
    }
}

3、二维数组

二维数组简介

一维数组里面只需要一个下标即可定位数组中的元素，二维数组需要两个下标才能够定位到数组中的元素。可以将我们平时使用的excel理解为是一个二维数组。

静态初始化二维数组

package com.sutaoyu.array;

public class array_07 {
    public static void main(String[] args) {
        int[][] a= { 
                {1,2,3,4},
                {2,3,4,5},
                {3,4,5,6},
                {4,5,6,7},
                    };
        
        System.out.println(a.length);
        System.out.println("------");
        for(int i=0;i<a.length;i++) {
            for(int j=0;j<a[i].length;j++) {
                System.out.print(a[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
        
        
            }
        }

动态初始化二维数组

package com.sutaoyu.array;

public class array_08 {
    public static void main(String[] args) {
        int[][] a= new int[4][4];
        for(int i = 0;i < a.length;i++) { // 代表行数
            for(int j = 0;j < a[i].length;j++) {
                System.out.print(a[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
        System.out.println("--------------");
        a[1][2] = 2;
        a[2][3] = 3;
        a[3][1] = 4;
        for(int i = 0;i < a.length;i++) { // 代表行数
            for(int j = 0;j < a[i].length;j++) {
                System.out.print(a[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
        
    }
}

如何获取用户输入的数据

package com.sutaoyu.array;

import java.util.Scanner;

public class Input {

    public static void main(String[] args) {
        Scanner s= new Scanner(System.in);
        String input = s.next();
        System.out.println("您输入的是：" + input);
    }
}

小练习：

酒店房间管理系统需求

有家酒店一共有5层，每层有10个房间，其中：
1，2层是标准间
3，4层是双人间
5层是豪华间
根据以前所学习的知识实现一个酒店房间管理系统，需要提供房间状态查看，房间预定、退房的功能。
在编写该系统之前先来学习一个新知识，如何获取用户的输入？

package com.sutaoyu.array;

import java.util.Scanner;

public class array_09 {
    
    public static void main(String args) {
        Scanner s = new Scanner(System.in);
        System.out.println("欢迎使用酒店管理系统，酒店房间列表如下所示：");
        
        //初始化酒店
        Hotel h = new Hotel();
         //输出房间列表
        h.print();
        while(true) {
            System.out.println("请输入预定或者退房");
            String order = s.next();
            if("预定".equals(order)){
                System.out.print("请输入预订房间的编号：");
                String id = s.next();
                //预订房间
                h.order(id);
            }else if("退房".equals(order)){
                System.out.print("请输入退房房间的编号：");
                String id = s.next();
                h.checkout(id);
            }else {
                System.out.print("请输入预定或者退房");
            }

            //打印酒店列表
            h.print();
        }
    }
}

class Room{
    private String id;
    private String type;
    private boolean isUse;
    
    public void setId(String id) {
        this.id = id;
    }
    public String getId() {
        return id;
    }
    public void setType(String type) {
        this.type = type;
    }
    public String getType() {
        return type;
    }
    public void setIsUse(boolean isUse) {
        this.isUse = isUse;
    }
    public boolean getIsUse() {
        return isUse;
    }
    
    //无参构造方法
    public Room() {}
    
    //有参构造方法
    public Room(String id,String type,boolean isUSE) {
        this.id = id;
        this.type = type;
        this.isUse = isUse;
    }
    
    public String toString() {
        return "[" + id +"," + type + "," + (isUse?"占用":"空闲") + "]";
    }
}

class Hotel {
/*
    酒店里面是一个挨着一个房间，需要将这些房间体现出来，
    酒店中的房间个数是固定的，在Java中数组的长度是固定的，这里可以使用数组来存储这些房间对象。
    酒店有多层，所以使用二维数组
    定义房间类型的数组，该数组中用来存储房间对象
*/

    private Room[][] rooms;
//无参构造方法，用来初始化房间对象数据

    Hotel(){
        //酒店的房间是共有5层，每层10个房间
        rooms= new Room[5][10];
        //赋值，初始化房间号
        //1,2 标准间:101,102 ... 110,201,202 ... 210
        //3 4 双人间
        //5 豪华间
        for(int i = 0;i < rooms.length;i++) {
            for(int j = 0;j < rooms[i].length;j++) {
                if(i == 0 || i == 1) {
                    rooms[i][j] = new Room(((i+1)*100)+j+1+"","标准间",false);
                }
                if(i==2 || i == 3) {
                    rooms[i][j] = new Room(((i+1)*100)+j+1+"","双人间",false);
                }
                if(i==4) {
                    rooms[i][j] = new Room(((i+1)*100)+j+1+"","豪华间",false);
                }
            }
        }
    }
    
    //在使用酒店管理系统时需要查看每个房间的状态，是否已被占用
    //对外提供一个打印酒店房间列表的方法
    public void print() {
        for(int i = 0;i < rooms.length;i++) {
            for(int j = 0;i < rooms[i].length;j++) {
                System.out.print(rooms[i][j] + " ");
            }
        }
    }
    
    //当用户预订时，需要将房间状态改为占用
    //对外提供一个预订酒店的方法
    public void order(String id) {
        for(int i = 0;i < rooms.length;i++) {
            for(int j = 0;i < rooms[i].length;j++) {
                //根据传入的房间编号去数组中查找与之对应的房间
                if(rooms[i][j].getId().equals(id)) {
                    //将该房间的状态改成占用
                    rooms[i][j].setIsUse(true);
                    //此时后面就没有必要再继续循环了，所以直接return
                    return;
                }
            }
        }
    }
    
     //对外提供一个退房酒店的方法
    public void checkout(String id) {
        for(int i = 0;i < rooms.length;i++) {
            for(int j = 0;i < rooms[i].length;j++) {
                //根据传入的房间编号去数组中查找与之对应的房间
                if(rooms[i][j].getId().equals(id)) {
                    //将该房间的状态改成占用
                    rooms[i][j].setIsUse(false);
                    //此时后面就没有必要再继续循环了，所以直接return
                    return;
                }
            }
        }
    }
}

4、数组的扩容

通过拷贝进行扩容

在java语言里面，数组一旦创建好之后，长度是不可变的，倘若数组的长度不够使用了，装不下数据之后需要对数组进行扩容，那该如何扩容呢？可以再重新创建一个长度更大的数组，然后将之前的旧数组拷贝到新的数组里面，通过这种方式来进行扩容。相信你能够自己写出这样的方法，不过java已经为开发者提供了这样的方法，我们直接使用即可。

package com.sutaoyu.array;

public class array_10 {

    public static void main(String[] args) {
        
        int[] a = {1,2,3,4};
        int[] b = {5,6,7,8,9};
        
        System.arraycopy(a, 0, b, 1, 4);
        
        for(int i = 0; i < b.length;i++) {
            System.out.println(b[i]);
        }
    }
}
结果：
5
1
2
3
4

5、排序

选择排序原理

将要排序的一组数字进行遍历。
第一次遍历，将第一个位置上的数字与后面的数字进行比较，如果后面的数字比第一个位置上的元素小，则将两个数字的位置进行交换。
第二次遍历，将第二个位置上的数字与后面的数字进行比较，如果后面的数字比第二个位置上的元素小，则将两个数字的位置进行交换。
依次进行遍历、位置交换，直到这组数字排序完成。
比如要排序的数字是4,2,7,3,6

第一次遍历，将最小的2筛选出来：2,4,7,3,6
剩下数字：4,7,3,6
第二次遍历，将最小的3筛选出来：3,7,4,6
剩下数字：7,4,6
第三次遍历，将最小的4筛选出来：4,7,6
剩下数字：7,6
第四次遍历，将最小的6筛选出来：6,7
排序完成。
假设要遍历数字的个数是n，则需要遍历的次数是n-1

代码实现   

public class SelectSort{

    public static void main(String[] args){

        int[] a = {4 ,2 ,7 ,3 ,6};

        //选择排序
        for(int i=0;i<a.length-1;i++){

            //假设第一个数据是最小值
            //记录最小值元素的下标
            int min = i;

            for(int j=i+1;j<a.length;j++){

                if(a[min]>a[j]){
                    //给min重新赋值
                    min = j;
                }
            }

            //交换位置
            if(min != i){
                int temp;
                temp = a[i];
                a[i] = a[min];
                a[min] = temp;
            }

        }

        //输出
        for(int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }

}

冒泡排序原理

将要排序的一组数字进行遍历。
第一次遍历，将相邻的两个数字进行比较，直到这组数字全部比较完成，如果前面比后面的数字大，则进行交换位置，此时可以将最大的数字筛选出来，放到最后的位置上。
第二次遍历，将相邻的两个数字进行比较，直到这组数字全部比较完成，如果前面比后面的数字大，则进行交换位置，将这组数字里面第二大的数字筛选出来，放到倒数第二的位置上。
依次进行遍历，交换位置，直到排序完成。
比如要排序的数字是4,2,7,3,6

第一次遍历：4,2,7,3,6

第一个位置上的数字和第二个位置上的数字进行比较，4大于2，交换位置：
2,4,7,3,6
第二个位置上的数字和第三个位置上的数字进行比较，4小于7，不用交换：
2,4,7,3,6
第三个位置上的数字和第四个位置上的数字进行比较，7大于3，交换位置：
2,4,3,7,6
第四个位置上的数字和第五个位置上的数字进行比较，7大于6，交换位置：
2,4,3,6,7

第二次遍历：2,4,3,6

第一个位置上的数字和第二个位置上的数字进行比较，2小于4，不用交换：
2,4,3,6
第二个位置上的数字和第三个位置上的数字进行比较，4大于3，交换位置：
2,3,4,6
第三个位置上的数字和第四个位置上的数字进行比较，4小于6，不用交换：
2,3,4,6

第三次遍历：2,3,4

第一个位置上的数字和第二个位置上的数字进行比较，2小于3，不用交换
2,3,4
第二个位置上的数字和第三个位置上的数字进行比较，3小于4，不用交换
2,3,4

第四次遍历：2,3

第一个位置上的数字和第二个位置上的数字进行比较，2小于3，不用交换
2,3

排序完成
假设要遍历数字的个数是n，则需要遍历的次数是n-1

代码实现

/*
    冒泡排序算法：


*/
public class BubbleSort{

    public static void main(String[] args){

        int[] a = {4,2,7,3,6};

        //开始排序
        for(int i=a.length-1;i>0;i--){
            for(int j=0;j<i;j++){
                if(a[j]>a[j+1]){
                    //交换位置
                    int temp;
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }

        //遍历
        for(int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }

    }
}

二分法查找原理

使用二分法查找时需要以下两个条件：

• 没有重复元素
• 已经排好顺序

假设给定一组排好序且没有重复元素的数字，要从这些数字中快速找到x所在的位置，可以从这组数字的中间位置开始找，如果当前值与x相等，则查找成功，如果小于x则从后半段的中间位置继续找，如果大于x则从前半段的中间位置继续寻找，直到找到x所在的位置

例如一个数组里面的元素有：1,5,8,15,18,23,30
快速找到23对应的下标值
第一次：取得数组的中间位置的值15,15小于23，所以继续从后半段开始找，后半段的元素是18,23,30
第二次：取得数组后半段元素中间位置的值23,23等于23，即找到23对应的下标值5

代码实现

public class MyArrays{

    public static void main(String[] args){

        int[] a = {1,5,8,15,18,23,30};

        int destElement = 23;

        //要求从a数组中查找23这个元素的下标
        int index = binarySearch(a,destElement); 
        //如果找到则返回元素的下标，如果找不到统一返回 -1

        System.out.println((index==-1)? destElement + "元素不存在！":destElement + "在数组中的下标是：" + index);

    }


    //二分法查找的核心算法
    public static int binarySearch(int[] a,int destElement){

        int begin = 0;
        int end = a.length-1;



        while(begin <= end){

            int middle = (begin + end)/2;    

            if(a[middle]==destElement){
                return middle; 
            }else if(a[middle]>destElement){
                end = middle - 1;
            }else if(a[middle] < destElement){
                begin = middle + 1;
            }
        }

        return -1;

    }

}