一维数组

Java语言中的数组是一种引用数据类型。不属于基本数据类型。数组的父类是Object。

数组实际上是一个容器，可以同时容纳多个元素。（数组是一个数据的集合）

数组当中可以存储基本数据类型的数据，也可以存储引用数据类型的数据。

数组因为是引用类型，所以数组对象是堆内存当中。（数组是存储在堆当中的）

数组当中如果存储的是“java对象”的话，实际上存储的是对象的“引用（内存地址）”。

数组一旦创建，在java中规定，长度不可变。（数组长度不可变）

数组的分类：一维数组（常用）、二维数组（很少）、三维数组、多维数组......

所有的数组对象都有length属性（java自带的），用来获取数组中元素的个数。

java中的数组要求数组中的元素类型统一。比如int类型的数组只能存储int类型。

数组在内存方面存储的时候，数组中的元素内存地址（存储的每一个元素都是有队则的挨着排列的）是连续的。内存地址连续。这是数组存储元素的特点（特色）。数组实际上是一种简单的数据结构。

所有的数组都是拿“第一个小方框的内存地址”作为整个数组对象的内存地址。（数组中首元素的内存地址作为整个数组对象的内存地址。）

数组中每一个元素都是有下标的，下标从0开始，以1递增。最后一个元素的下标是：length-1。下标非常重要，因为我们对数组中元素进行“存取”的时候，都需要通过下标来进行。

数组这种数据结构的优点和缺点是什么？
优点：
查询/查找/检索某个下标上的元素时效率极高。可以说时查询效率最高的一个数据结构。
为什么检索效率高？
第一：每一个元素的内存地址在控件存储上是连续的。
第二：每一个元素类型相同，所以占用空间大小一样。
第三：知道第一个元素的内存地址，知道每一个元素占用空间的大小，又知道下标，所以通过一个数学表达式就可以计算出某个下标上元素的内存地址。直接通过内存地址定位元素，所以数组的检索效率是最高的。

数组中存储100个元素，或者存储100万个元素，在元素查询/检索方面，效率是相同的，因为数组中元素查找到时候不会一个一个找，是通过数学表达式计算出来的。（算出一个内存地址，直接定位的。）

缺点：
第一：由于为了保证数组中每个元素的内存地址连续，所以在数组上随即删除或者增加元素的时候，效率较低，因为随机增删元素会设计到后面元素统一向前或向后位移的操作。
第二：数组不能存储大数据量，因为很难在内存控件上找到一块特别大的连续的内存空间。

数组的内存结构.png

注意：对于数组中最后一个元素的增删，是没有效率影响的。

怎么声明/定义一个一维数组？
语法格式：
int[] array1；
double[] array2；
boolean[] array3；
String[] array4；
Object[] array5；

怎么初始化一个一维数组呢？
包括两种方式：静态初始化一维数组，动态初始化一维数组。
静态初始化语法格式：
int[] array = {100，200，300，55};
动态初始化语法格式：
int[] array = new int[5];//这里的5表示数组的元素个数。
初始化一个5个长度的int类型数组，每个元素默认值0。
String类型的，默认值是null。

访问数组中的元素，变量名[]
取（读）
第一个元素：变量名[0]
最后一个元素：变量名[变量名.length - 1]
存（改）
把第一个元素改为111：变量名[0] = 111;
把最后一个元素改为0： 变量名[变量名.length - 1] = 0;

怎么遍历一维数组呢？
for(int i = 0; i < 变量名.length; i++){
System.out.println(变量名[i]);
}

数组下标越界会出现：ArrayIndexOutOfBoundsException

如果从最后一个元素遍历到第一个元素
for(int i = 变量名.length - 1 ; i >= 0 ; i--)
System.out.println(变量名[i]);
}

当你创建数组的时候，确定数组中存储哪些具体d 元素时，采用静态初始化方式。
当你创建数组的时候，不确定将来数组中存储哪些数据，你可以采用动态初始化的方式，预先分配内存空间。

如果直接传递一个静态数组的话，语法必须这样写：
new int[]{1，2，3}
不能直接把数组放进去

main方法上面的“String[] args”有什么用？
JVM负责调用main方法，JVM调用main方法的时候，会自动传一个String数组过来。
JVM默认传过来的数组对象的长度，默认是0。
这个数组时留给用户的，用户可以在控制台上输入参数，这个参数自动会被转换为“String[] args”

在java开发中，数组长度一旦确定不可变，那么数组满了怎么办？
数组满了，需要扩容。
java中对数组的扩容是：先新建一个大容量的数组，然后将小容量的数组中的数据一个一个拷贝到大数组当中。

数组扩容效率较低。因为涉及到拷贝的问题。所以在以后的开发中请注意：尽可能少的进行数组的拷贝。
可以在创建数组对象的时候预估计一下多长合适，最好预估准确，这样可以减少数组的扩容次数。提高效率。

java中的数组是怎么进行拷贝的呢？
System.arraycopy();
5个参数：拷贝源，源起始下标，目标，目标下标，拷贝长度

二维数组

二维数组其实是一个特殊的一维数组，特殊在这个一维数组当中的每一个元素是一个一维数组。

三维数组是一个特殊的二维数组，特殊在这个二维数组中每一个元素是一个一维数组。

二维数组的静态初始化
int[][] array = {{1,2,3},{4,5,6},{7,8,9}};

二维数组中元素的访问
变量名[二维数组中的一维数组的下标][一维数组的下标]
a[0][0]：表示第1个一维数组中的第1个元素。
a[3][100]：表示第4个一维数组中的第101个元素。

注意：对于 a[3][100]来说，其中a[3]是一个整体。[100]是前面a[3]执行结束的结果然后再下标100。

遍历二维数组

遍历二维数组.png

动态初始化二维数组
int[][] array = new int[3][4];

new int[][]{{1,2,3,4},{5,6,7,8},{9,10,15,111}}

Array工具类

工具类当中的方法都是静态的。

java.util.Arrays
Arrays是一个工具类，其中有一个sort()方法，可以排序，静态方法，直接使用类名调用就行。

主要使用的是两个方法：二分法查找、排序

java.util.Arrays;工具类中有哪些方法，我们开发到时候要参考API帮助文档，不要死记硬背

排序：Arrays.sort(arr);
二分法：Arrays.binarySearch(arr，参数);

算法

算法在以后的开发中我们不需要使用。因为java已经封装好了，直接调用就行。只不过以后面试的时候可能会有机会碰上。

冒泡排序算法

冒泡排序0.png 冒泡排序1.png

public class MaoPao {
    public static void main(String[] args) {
        int[] arr = {9,8,10,7,6,0,11};
        int count = 0;

        for (int i = arr.length - 1; i > 0; i--){
            for (int j = 0; j < i; j++){
                //不管是否需要交换位置，总之是要比较一次的。
                count++;
                if (arr[j] > arr[j+1]){
                    //交换位置
                    int temp;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        
        //输出比较次数
        System.out.println("比较次数:" + count);
        //输出结果
        for (int i = 0; i < arr.length; i++){
            System.out.println(arr[i]);
        }
    }

}

选择排序算法

选择排序：每一次从这堆“参与比较的数据”当中找出最小值，拿着这个最小值和“参与比较的这堆最前面的元素”交换位置。

选择排序比冒泡排序好在：每一次的交换位置都是有意义的。

选择排序比冒泡排序的效率高。
高在交换位置的次数上。
选择排序的交换位置是有意义的。
循环一次，然后找出参加比较的这堆数据中最小的，拿着这个最小的值和最前面的数据交换位置。

选择排序.png

public class XuanZePaiXu {
    public static void main(String[] args) {
        //int[] arr = {3,1,6,2,5};
        int[] arr = {9,8,10,7,6,0,11};
        int count = 0;
        int count2 = 0;

        //选择排序
        //5条数据循环四次。（外循环四次）
        for (int i = 0;i < arr.length - 1; i++){
            //i的值是0，1，2，3
            //i正好是“参加比较的这堆数据中”最左边的那个元素的下标
            //i是一个参与比较的这堆数据中的起点下标。
            //假设起点i下标位置上的元素是最小的。
            int min = i;

            for (int j = i+1; j< arr.length;j++){
                count++;
                if (arr[j] < arr[min]){
                    min = j;//最小值的元素下标是j
                }
            }

            //当i和min相等时，表示最初猜测是对的。
            //当i和min不相等时，表示最初猜测是错的。有比这个元素更小的元素。
            //需要拿着这个更小的元素和最左边的元素交换位置。
            if (min != i){
                //表示存更小的数据
                //arr[min] 最小的数据
                //arr[i] 最前面的数据
                int temp;
                temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
                count2++;
            }
        }

        //冒泡排序和选择排序实际上比较的次数没变。
        //交换的次数减少了。
        System.out.println("比较次数:" + count);
        System.out.println("交换位置的次数:" + count2);

        //排序之后遍历
        for (int i = 0;i < arr.length; i++){
            System.out.println(arr[i]);
        }
    }
}

数组的元素查找

有两种方式：
第一种方式：一个一个挨着找，直到找到为止。
第二种方式：二分法查找（算法），这个效率较高。
第一种方式：

public class ChaZhao {
    public static void main(String[] args) {
        int[] arr = {4,5,6,87,8};
        //需求：找到87的下标。
        //一个一个挨着找
        /* for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 87) {
                System.out.println("87元素下标为：" + i);
            }
        }
        //程序执行到此处，表示没有87
        System.out.println("87元素不存在！");
        */

        //最好将以上的程序封装一个方法，思考：传什么参数？返回什么值？
        //传什么：第一个参数时数组，第二个参数时被查找的元素。
        //返回值：返回被查找的这个元素的下标。如果找不到返回-1
        int index = arraySearch(arr,87);
        //可以先定义这个方法报红没事，光标放上alt + 回车，自动生成。
        System.out.println(index == -1 ? "该元素不存在" : "该元素下标是：" + index);
    }

    /*
    * 从数组中检索某个元素的下标（如果有相同的元素，返回的是第一个元素的下标）
    * @param arr 被检索的数组
    * @param ele 被检索的元素
    * @return 大于等于0的数表示元素的下标，-1表示该元素不存在。
    * */
    public static int arraySearch(int[] arr, int ele) {
        for (int i = 0; i < arr.length; i++) {
            if (ele == arr[i]) {
                return i;
            }
        }
        return -1;
    }
}

第二种方式：二分法查找（折半查找）
第一：二分法查找算法是基于排序的基础之上。（没有排序的数据是无法查找的。）
第二：二分法查找效率要高于一个挨着一个的这种查找方式。
第三：二分法查找原理

二分法查找.png

二分法查找到终止条件：一直折半，直到中间的哪个元素恰好是被查找的元素。

public class ErFenFa {
    public static void main(String[] args) {

        int[] arr = {100,200,230,600,1000,2000,9999};

        //找出这个数组中200所在的下标
        //调用方法
        int index = binarySearch(arr,200);
        System.out.println(index == -1 ? "该元素不存在" : "该元素下标为：" + index);
    }
    /*从数组中查找目标元素的下标。
    arr 被查找的数组（这个必须是已经排序的。）
    *dest 目标元素
    return -1 表示该元素不存在，其他表示返回该元素的下标
    * */

   public static int binarySearch(int[] arr, int dest) {
       //开始下标
       int begin = 0;
       //结束下标
       int end = arr.length - 1;
       //开始元素的下标只要在结束元素下标的左边，就有机会继续循环。
       while(begin <= end) {
           //中间元素下标
           int mid = (begin + end) / 2;
           if (arr[mid] == dest) {
               return mid;
           } else if (arr[mid] < dest) {
               //目标在中间的右边
               //开始元素下标需要发生变化(开始元素的下标需要重新赋值)
               begin = mid + 1;//一直增
           } else {
               //arr[mid] > dest
               //目标在中间的左边
               //修改结束元素的下标
               end = mid - 1;//一直减
           }
       }
        return -1;
    }
}