1.数组基础

1.什么是数组：

          同一类型数据的集合，就是一个容器。

2.数组的好处：

          可以自动为数组中的元素从零开始编号，方便操作这些数据。

3.格式：  (一旦创建，必须明确长度)

         格式1：

             元素类型   [ ]  数组名  =  new  元素类型  [元素个数即数组的长度]；

             示例：int[] array = new int[5];

         格式2：

             元素类型 [ ]  数组名 =  new 元素类型 [ ]{元素1，元素2…}；

             示例：int[] array = new int[]{1,2,3,4,5};

                       int[] array = {1,2,3,4,5};

数组有默认值：（不用初始化也可以使用，因为数组new int[5]是堆内存中的实例，堆内存中的实例都有默认的初始值）

如int[] array = new int[5];

System.out.pritln(array[0]);        

结果为0。

常见错误：

1.数组下标越界异常

int[] arr = new int[3];

System.out.println(arr[3]);

说明：编译不会报错，运行时报错。ArrayIndexOutOfBoundsException

          当访问数组中不存在的下标时，就会报此异常。

2.空指针异常

int [] arr = new int[3];

arr = null;

System.ou.println(arr[0]);

说明：同样编译不会报错，运行时报错。NullPointeException

         空指针异常，当引用型变量没有任何实体指向时，如果访问该变量，就会报此异常。

 

2.数组的常见操作

1.遍历

打印数组中的所有元素

int[] arr = {43,6,645,43,3,2,1,54};

for (int i=0; i<arr.length; i++) {

    System.out.print("arr["+i+"]:"+arr[i]+";");

}

2.获取最值

获取最大值

public int getMax(int[] arr){

    int max = arr[0];//记录元素值

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

        if(arr[i]>max){

            max = arr[i];

        }

    }

    return max;

}

 

public static int getMax(int[] arr){

    int maxIndex = 0;//记录元素下标

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

        if(arr[i]>arr[maxIndex]){

            arr[maxIndex] = arr[i];

        }

    }

    return arr[maxIndex];

}

3.排序

java API提供了排序的方法：java.util.Arrays.sort(arr);

1.选择排序法

原理：

代码：

public void selectSort(int[] arr){

        int temp;

        for (int i = 0; i<arr.length-1; i++) {

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

                if(arr[i]>arr[j]){//交换

                    temp = arr[i];

                    arr[i] = arr[j];

                    arr[j] = temp;

                }

            }

        }

}

 

2.冒泡排序法

原理：

代码：

public static void bubblesort(int[] arr){

    int temp;

    for (int i = 0; i<arr.length-1; i++) {

        for (int j = 0; j<arr.length-1-i; j++) {

            if(arr[j]>arr[j+1]){

                temp = arr[j];

                arr[j] = arr[j+1];

                arr[j+1] = temp;

           }

       }

    }

}

*封装交换代码：

//交换数组中两个元素的位置

public static void swap(int[] arr, int a, int b){

    int temp = arr[a];

    arr[a] = arr[b];

    arr[b] = arr[a];

}

 

选择排序性能优化：

如上图所示，由于数组储存于堆内存中，重复多余的交换位置会带来多余的运算，所以想到定义中间变量来记录每次得到的最小值，再进行对应位置的交换，这样能减少交换的次数，提高效率。

代码：

public static void selectSort_2(int[] arr){

        for (int i = 0; i<arr.length-1; i++) {

            int num = arr[i];

            int index = i;

            for (int j = i; j<arr.length; j++) {//内循环负责查找余下元素中的最小元素

                if(num>arr[j]){

                    num = arr[j];//用num记录最小的元素

                    index = j;//用index记录最小元素的下标

                }

            }

            if(index!=i){

                swap(arr, i, index);//交换最新要要排序的元素和查找到的最小元素位置

            }

        }

    }

          

4.查找

1.查找某元素第一次出现的位置

代码：

public static int getIndex(int[] arr , int num){

        for (int i = 0; i<arr.length; i++) {

            if(num==arr[i]){

                return i;

            }

        }

        return -1;

    }

2.二分查找（折半查找）

**适用于有序数组

java API也提供了二分查找 。java.util.Arrays.binarySearch(int[],target);如果存在，返回下标，如果不存在，返回 -插入点-1

代码： 

1.递归法：

public static int find(int arry[], int target, int beginIndex, int endIndex) {

    if (beginIndex > endIndex) {

        return -1;

    }

    int middleIndex = (beginIndex + endIndex) / 2;

    if (arry[middleIndex] == target) {

        return middleIndex;

    } else if (arry[middleIndex] < target) {

        beginIndex = middleIndex + 1;

    } else

        endIndex = middleIndex - 1;

    return find(arry, target, beginIndex, endIndex);

}

2.while循环 

1.

public static int halfSearch(int[] arr, int target){

    int min = 0, max = arr.length-1, mid = (min + max)/2;

    while(arr[mid]!=target){//

        if(target>arr[mid])

            min = mid + 1;

        else if(target<arr[mid])

            max = mid - 1;

        if(max<min){

            return -1;

        }

        mid = (min + max)/2;

    }

    return mid;

}

 

2.

public static int halfSearch(int[] arr, int target){

    int min = 0, max = arr.length-1, mid;

    while(max>=min){

        mid = (min + max)/2;

        if(target>arr[mid])

            min = mid + 1;

        else if(target<arr[mid])

            max = mid - 1;

        else

            return mid;

    }

    return -1;

}

 

面试题：给定一个有序的数组，如果往数组中存储一个元素，并保证这个数组还是有序的，那么这个元素的存储的角标如何获取。

答案：直接使用上面的二分查找的函数，把返回-1改成返回min即可。

3.二维数组

格式1：int[][] arr = new int[3][2];

• 定义了名称为arr的二维数组
• 二维数组中有3个一维数组
• 每一个一维数组有2个元素
• 一维数组的名称分别是arr[0],arr[1],arr[2]
• 给第一个一维数组1下标位赋值为78的写法是：arr[0][1]=78;

格式2：int[][] arr = new int[3][];

• 二维数组中有3个一维数组
• 每一个一维数组都是默认初始化值null
• 可以对这3个一维数组分别进行初始化

       arr[0] = new int[3];

       arr[1] = new int[1];

       arr[2] = new int[2];

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

 

考虑如下代码：

int[][] arr = new int[3][2];

System.out.println(arr);//[[I@6dc57a92

System.out.println(arr[0]);//[I@3ff23f8b

System.out.println(arr[0][0]);//0

int[][] arr2 = new int[3][];

System.out.println(arr2);//[[I@3929df79

System.out.println(arr2[0]);//null

System.out.println(arr2[0][0]);//NullPointerException

说明：

第一种定义方式：在栈内存中保存一个arr的变量，用来记录二维数组在堆内存中的地址值。在堆内存中会创建一个二维数组，开辟三个连续的空间用来保存三个一维数组的首地址值。堆内存中还会有三个对应的一维数组的实体，每一个一维数组的每一个元素默认初始化值为0.

第二种定义方式：在栈内存中保存一个arr的变量，用来记录二维数组在堆内存中的地址值。在堆内存中会创建一个二维数组，开辟三个连续的空间默认初始化值为null。

 

二维数组的长度的获取：

二维数组的长度用arr.length获取，得到的是二维数组中一维数组的个数。如：

int [][] arr = new int[3][2];

arr.length的值为 3。

arr[0].length获取的是第一个一维数组的长度。

----------完----------

by_世界是我的床