六、数组-Arrays类

一、数组的三种创建方式

 public static void main(String[] args){

    // 1.方式一  声明 分配空间并赋值，静态初始化
 
     int[] arr1 = {1,2,3};
 
    // 2.方式二 显示初始化，动态
 
     int[] arr2;
 
     arr2 =newint[]{1,2,3};

     // 3.方式三 显示初始化()，动态

     int[] arr3;
 
    arr3 =newint[3];

 }

它们的区别
方式一：在声明的时候直接就已经分配空间，并赋值，方式一是不能写成如下这种形式的。
int[] arr1;
arr1 = {1,2,3};//错误写法 编译不同过
方式二和方式三：声明和内存分配是分开的。

二、数组的内存图解

第一行代码 int[] x; 声明了一个变量x，该变量的类型为int[]，即一个int类型的数组。变量x会占用一块内存单元，它没有被分配初始值。内存中的状态如下图所示。

image

第二行代码 x = new int[100]; 创建了一个数组，将数组的地址赋值给变量x。在程序运行期间可以使用变量x来引用数组，这时内存中的状态会发生变化，如下图所示。

image

在上图中描述了变量x引用数组的情况。该数组中有100个元素，初始值都为0。

其实数组中根据元素类型的不同，默认初始化的值也是不一样的。具体如下表所示。

image

三、数组的访问与长度

数组中的每个元素都有一个索引(也可称为角标)，要想访问数组中的元素可以通过“x[0]、x[1]、……、x[98]、x[99]”的形式。需要注意的是，数组中最小的索引是0，最大的索引是“数组的长度-1”。

在Java中，为了方便我们获得数组的长度，提供了一个length属性，在程序中可以通过“数组名.length”的方式来获得数组的长度，即元素的个数。

四、数组遍历

在操作数组时，经常需要依次访问数组中的每个元素，这种操作称作数组的遍历。接下来通过一个案例来学习如何使用for循环来遍历数组，如下所示。

public class ArrayDemo04 {
 
  public static voidmain(String[] args) {

     int[] arr = { 1, 2,3, 4, 5 };// 定义数组

     // 使用for循环遍历数组的元素

      for(inti = 0; i < arr.length;i++) {
 
         System.*out*.println(arr[i]);// 通过索引访问元素
 
       }
 
    }
 
 }

五、数组元素的删除

    数组的特性是，一旦初始化，则长度确定，所以要删除数组中元素，并且长度也随着删除而改变，则要重新建立数组。

/** 
*删除方式1，index为数组需要删除的索引位
 */   
 public int[] delete(int index, int array[]) {
 
         //数组的删除其实就是覆盖前一位        int[] arrNew = new int[array.length - 1];
 
         for (int i = index; i < array.length - 1; i++) {
 
             array[i] = array[i + 1];
 
         }
 
         System.arraycopy(array, 0, arrNew, 0, arrNew.length);
 
         return arrNew;
 
     }
 
 /** 
 *删除方式2，index为数组需要删除的索引位 
 */    
 public int[] delete2(int index, int array[]) {
 
         //数组的删除其实就是覆盖前一位        int[] arrNew = new int[array.length - 1];
 
         for (int i = 0; i < array.length - 1; i++) {
 
             if (i < index) {

                 arrNew[i] = array[i];
 
             } else {
 
                 arrNew[i] = array[i + 1];
 
             }
 
         }
 
         return arrNew;
 
 }

六、获取数组最值

在操作数组时，经常需要获取数组中元素的最值。接下来通过一个案例来演示如何获取数组中元素的最大值，如下所示。

 publicclassArrayDemo05 {
 
    publicstaticvoidmain(String[] args) {
 
       int[] arr = { 4, 1,6, 3, 9, 8 };// 定义一个数组
 
 intmax = arr[0];//定义变量max用于记住最大数，首先假设第一个元素为最大值
 
       // 下面通过一个for循环遍历数组中的元素
 
       for(intx = 1; x < arr.length;x++) {
 
         if(arr[x] >max) {// 比较arr[x]的值是否大于max
 
            max = arr[x];// 条件成立，将arr[x]的值赋给max
 
         }
 
       }
 
       System.*out*.println("max="+ max);//打印最大值
 
    }
 
}

七、数组异常

1. 数组越界异常ArrayIndexOutOfBoundsException：

每个数组的索引都有一个范围，即0~length-1。在访问数组的元素时，索引不能超出这个范围，否则程序会报错。

int[] arr ={11,22};
System.out.println( arr[2] );//会产生数组越界异常

2. 空指针异常NullPointerException

在使用变量引用一个数组时，变量必须指向一个有效的数组对象，如果该变量的值为null，则意味着没有指向任何数组，此时通过该变量访问数组的元素会出现空指针异常。

int[] arr ={1,2,3};
arr = null;
System.out.println( arr[0] );//会产生空指针异常

八、二维数组

1.二维数组定义格式

第一种方式：

int[][] arr = newint[3][4];

上面的代码相当于定义了一个3*4的二维数组，即二维数组的长度为3，二维数组中的每个元素又是一个长度为4的数组，接下来通过一个图来表示这种情况，如下图所示。

image

第二种方式：

int[][] arr = newint[3][];

第二种方式和第一种类似，只是数组中每个元素的长度不确定，接下来通过一个图来表示这种情况，如下图所示。

image

第三种方式：

int[][] arr ={{1,2},{3,4,5,6},{7,8,9}};

上面的二维数组中定义了三个元素，这三个元素都是数组，分别为{1,2}、{3,4,5,6}、{7,8,9}，接下来通过一个图来表示这种情况。

image

2.二维数组元素遍历与数组元素累加和

class ArrayDemo09 {
 
    public static void main(String[] args){
 
      //一维数组的求累加和并遍历
 
       int[] arr = {10,20,30,40,50};
 
       int sum = 0;
 
       for (int i=0; i<arr.length;i++)
 
               //System.out.println(arr[i]);
 
        sum += arr[i];
 
       }
 
       System.out.println("sum= " + sum);
 
       System.out.println("---------------------");
 
        //二维数组的求累加和并遍历
 
       int[][] arr2 = { {1,2},{3,4,5},{6,7,8,9,10} };
 
       int sum2 = 0;
 
       for (int i=0; i<arr2.length;i++){
 
         for (int j=0; j<arr2[i].length;j++){
 
                 //System.out.println(arr2[i][j])
 
            sum2 += arr2[i][j];
 
         }

       }
 
       System.out.println("sum2= "+ sum2);
 
    }
  }

九、Arrays类

此类包含用来操作数组（比如排序和搜索）的各种方法。需要注意，如果指定数组引用为 null，则访问此类中的方法都会抛出空指针异常NullPointerException。

1. 常用方法

Arrays.png

• sort方法，用来对指定数组中的元素进行排序（元素值从小到大进行排序）

//源arr数组元素{1,5,9,3,7}, 进行排序后arr数组元素为{1,3,5,7,9}
int[] arr = {1,5,9,3,7};
Arrays.sort( arr );

• toString方法，用来返回指定数组元素内容的字符串形式

int[] arr = {1,5,9,3,7};
String str = Arrays.toString(arr); // str的值为[1, 3, 5, 7, 9]

• binarySearch方法，在指定数组中，查找给定元素值出现的位置。若没有查询到，返回位置为-1。要求该数组必须是个有序的数组。

int[] arr = {1,3,4,5,6};
int index = Arrays.binarySearch(arr, 4); //index的值为2
int index2= Arrasy.binarySearch(arr, 2); //index2的值为-1

2. 数组的排序与查找

例题：数组元素{13,46,22,65,3}进行排序

（1） 冒泡排序
冒泡排序最坏情况(即数组内数字完全按降序排列)下比较次数：n(n-1)/2

冒泡排序.png

题目分析：
通过观察发现，本题目要实现把数组元素{13,46,22,65,3}进行排序

1. 提到数组排序，就要进行元素值大小的比较，通过上图发现，我们想完成排序要经过若干次的比较才能够完成。
2. 上图中相邻的元素值依次比较，把大的值放后面的元素中，数组循环一圈后，则把最大元素值互换到了最后一个元素中。数组再循环一圈后，把第二大的元素值互换到了倒数第二个元素中。按照这种方式，数组循环多圈以后，就完成了数组元素的排序。这种排序方式我们称为冒泡排序。
   解题步骤：
3. 使用for循环（外层循环），指定数组要循环的圈数（通过图解可知，数组循环的圈数为数组长度 - 1）
4. 在每一圈中，通过for循环（内层循环）完成相邻的元素值依次比较，把大的值放后面的元素中
5. 每圈内层循环的次数，由第几圈循环来决定。如上图所示
   a) 进行第一圈元素比较时，内层循环次数为数组长度 - 1
   b) 进行第二圈元素比较时，内层循环次数为数组长度 - 2
   c) 依次类推，得出结论：进行第n圈元素比较时，内层循环次数为数组长度 -
   代码如下：

//冒泡排序
public static void bubbleSort(int[] arr) {
    //功能
    //外层循环用来控制数组循环的圈数
    for (int i = 0; i < arr.length-1; i++) {
        //j < arr.length-1 为了避免角标越界
        //j < arr.length-1-i 为了比较效率,避免重复比较
        //内层循环用来完成元素值比较，把大的元素值互换到后面
        for (int j = 0; j < arr.length-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

（2）选择排序

选择排序.png

题目分析：
通过观察发现，本题目要实现把数组元素{13,46,22,65,3}进行排序

1. 提到数组排序，就要进行元素值大小的比较，通过上图发现，我们想完成排序要经过若干次的比较才能够完成。
2. 上图中用每圈要比较的第一个元素与该元素后面的数组元素依次比较到数组的最后一个元素，把小的值放在第一个数组元素中，数组循环一圈后，则把最小元素值互换到了第一个元素中。
3. 数组再循环一圈后，把第二小的元素值互换到了第二个元素中。按照这种方式，数组循环多圈以后，就完成了数组元素的排序。这种排序方式我们称为选择排序。
   解题步骤：
4. 使用for循环（外层循环），指定数组要循环的圈数（通过图解可知，数组循环的圈数为数组长度 - 1）
5. 在每一圈中，通过for循环（内层循环）完成数组要比较的第一个元素与该元素后面的数组元素依次比较到数组的最后一个元素，把小的值放在第一个数组元素中
6. 在每一圈中，要参与比较的第一个元素由第几圈循环来决定。如上图所示
   a) 进行第一圈元素比较时，要比较的第一个元素为数组第一个元素，即索引为0的元素
   b) 进行第二圈元素比较时，要比较的第一个元素为数组第二个元素，即索引为1的元素
   c) 依次类推，得出结论：进行第n圈元素比较时，要比较的第一个元素为数组第n个元素，即数组索引为n-1的元素
   代码如下：

//选择排序
public static void selectSort(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]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

• 注意：

[冒泡排序]最少是1趟，最多才是n-1趟，最少比较n-1次（数组元素升序排列），最多才是n(n-1)/2（数组元素降序排列）；
[选择排序]一定是n-1趟排序，比较的次数永远是n(n-1)/2。

（3）二分查找

二分查找的前提是数组必须先排好序。

二分查找.png

题目分析：
通过观察发现，本题目要实现查找指定数值在元素有序的数组中存储的位置（索引），返回该位置（索引）。

1. 我们使用数组最中间位置的元素值与要查找的指定数值进行比较，若相等，返回中间元素值的索引
2. 最中间位置的元素值与要查找的指定数值进行比较，若不相等，则根据比较的结果，缩小查询范围为上次数组查询范围的一半；
   再根据新的查询范围，更新最中间元素位置，然后使用中间元素值与要查找的指定数值进行比较
    比较结果相等，返回中间元素值的索引
    比较结果不相等，继续缩小查询范围为上次数组查询范围的一半，更新最中间元素位置，继续比较，依次类推。
3. 当查询范围缩小到小于0个元素时，则指定数值没有查询到，返回索引值-1。
   解题步骤：
4. 定义3个用来记录索引值的变量，变量min记录当前范围最小索引值，初始值为0；变量max记录当前范围最大索引值，初始值为数组长度-1；变量mid记录当前当前范围最中间元素的索引值，初始值为(min+max) / 2
5. 使用循环，判断当前范围下，最中间元素值与指定查找的数值是否相等
    若相等，结束循环，返回当前范围最中间元素的索引值mid
    若不相等，根据比较结果，缩小查询范围为上一次查询范围的一般
    中间元素值 比 要查询的数值大，说明要查询的数值在当前范围的最小索引位置与中间索引位置之间，此时，更新查询范围为:
   范围最大索引值 = 上一次中间索引位置 -1；
    中间元素值 比 要查询的数值小，说明要查询的数值在当前范围的最大索引位置与中间索引位置之间，此时，更新查询范围为:
   范围最小索引值 = 上一次中间索引位置 +1；
    在新的查询范围中，更新中间元素值的位置，再次使用最中间元素值与指定查找的数值是否相等。
   中间索引值 = (范围最小索引值 +范围最大索引值) / 2;
6. 每次查询范围缩小一半后，使用if语句判断，查询范围是否小于0个元素，若小于0个元素，则说明指定数值没有查询到，返回索引值-1。

代码如下：

//二分查找法(折半查找法)
public static int halfSearch(int[] arr, int number) {
    //定义3个变量，用来记录min, min, mid的位置
    int min = 0;
    int max = arr.length-1;
    int mid = (min+max)/2;
    //判断mid位置上的原始与 number的值 是否相同
    while (arr[mid] != number) {
        //没找了， 更新范围，继续比较
        //更新范围
        if (arr[mid] > number) {
            //在左边
            max = mid-1;
        } else {
            //在右边
            min = mid+1;
        }
        //使用if语句判断，查询范围是否小于0个元素
        if ((max - min) < 0){
            //没有找到
            return -1;
        }
        //更新mid值
        mid = (min+max)/2;
    }
    //找到了 ，返回mid的位置
    return mid;
}