数组（超详细）

一，数组

1.1数组的概念

    数组在内存当中是一块连续的空间，可以保存相同类型的多个数据的容器

1.2数组的特点

    ①数组中保存的数据必须是相同的数据类型

    ②数组是定长的（数组一旦定义 那么长度是不可改变的）

** 二，数组的创建**

2.1动态初始化

    语法1：数据类型[ ] 数组名 = new 数据类型 [长度]

    语法2：数据类型 数组名 = new 数据类型 [长度]       

例子：

public class demo {
    public static void main(String[] args) {
        //数据类型[ ] 数组名 = new 数据类型 [长度]
        int[] arr = new int[4];

        //存数据
        arr[0] = 11;
        arr[1] = 12;
        arr[2] = 13;
        arr[3] = 14;
        //数据
        System.out.println("第一个元素"+arr[0]);
        System.out.println("第二个元素"+arr[1]);
        System.out.println("第三个元素"+arr[2]);
        System.out.println("第四个元素"+arr[3]);
        //获取数组长度
        System.out.println("数组的长度："+arr.length);
        //ArrayIndexOutOfBoundsException 数组下标越界
        System.out.println("第四个元素(会报错数组下标越界)"+arr[4]);
    }
}

2.2静态初始化

    语法1：数据类型[ ]  数组名 = {数据1，数据2，数据3，.......};

    语法2：数据类型  数组名[ ] = {数据1，数据2，......}; 

    语法3：数据类型[ ]  数组名 = new  数据类型[ ]{数据1，数据2，.......};

    注意：数组静态初始化必须在一起，不能分开；

    注意：数组直接输出到内存地址，基本类型在栈中，引用类型在堆中

例子：

public class demo2 {
    public static void main(String[] args) {
        String[] names = new String[]{"cxk","尼古拉斯","赵四","王五"};
        //直接打印数组names  地址：[Ljava.lang.String;@4554617c
        System.out.println(names);
        //存数据
        names[0]="基尼太美";
        names[0]="赵六";

        //取数据
        System.out.println("第一位元素："+names[0]);
        System.out.println("第二位元素："+names[1]);
        System.out.println("第三位元素："+names[2]);
        System.out.println("数组地址不变:"+names);

        //获取数组的长度
        System.out.println("获取到数组的长度："+names.length);
    }
}

2.3数组使用的细节

    ① 数组中每一个数据都称之为数组元素

    ② 数组中每一个元素都有对应的下标

    ③ 数组的下标范围是0~数组的长度-1

    ④ 数组的长度：通过数组名.length获取

    ⑤ 数组的长度如果超过边界会报错（ArrayIndexOutOfBoundsException 数组下标越界）   

** 三，数组的遍历**

遍历: 获取，保存数组中每一个元素（循环）

import java.util.Scanner;

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

        //定义一个数组
        int[] arr1 = {10,12,7,8,4,5};
        //遍历出数组中的元素
        for (int i = 0; i < arr1.length ; i++) {
            //arr[i]表示数组中每一个元素
            System.out.println(arr1[i]);
        }
        System.out.println("-------------------------------------");

        Scanner sc = new Scanner(System.in);
        //创建长度为4的int类型的数组
        int[] arr = new int[4];
        //遍历
        for (int i = 0; i < arr.length; i++) {
            //数组的下标从0开始，那么就需要i+1来表示
            System.out.println("请输入第"+(i+1)+"个元素");
            //存数据
            arr[i] = sc.nextInt();
        }
        //取值
        for (int i = 0; i < arr.length; i++) {
            System.out.println("数组的第"+(i+1)+"元素为："+arr[i]);
        }

    }
}

** 四,数组的默认值**

   ** 数组在创建的时候没有赋值的话是有默认值的**

            整数型数组的默认值：0；

            浮点型数组的默认值：0.0；

            布尔型数组的默认值：false；

            字符型数组的默认值：0  ，'  '，"\u000"

            引用数据类型数组默认值：null （赋值之后存的是地址，没有值的时候就是null ，"  "只是表示空字符串，但还是有地址的）

            ① null是一种特殊的值，表示当前对象在内存当中没有指向任何地址

            ② " "表示空字符串，在内存当中，是有对应的地址    

** 五，数组的扩容**

5.1，实现数组的扩容和缩容

    1，扩容和缩容

            步骤一：定义一个数组，然后新数组的长度要比原数组增加和减少

            步骤二：将原来的数组和元素拷贝到新数组当中

            步骤三：将原来数组的变量指向新数组

例子：数组的扩容

public class demo8 {
    public static void main(String[] args) {
        //定义数组 长度要比原数组长（短）
        int[] oldArr = {1,4,5,6,};
        //创建新数组长度比原来数组加1
        int[] newArr = new int[oldArr.length+1];
        //将原来数组的元素拷贝到新数组
        for (int i = 0; i < oldArr.length; i++) {
            newArr[i]=oldArr[i];
        }
        //将数组指向新数组的地址
        oldArr=newArr;
        for (int i = 0; i < oldArr.length; i++) {
            System.out.println(oldArr[i]);
        }
    }
}

例子：数组的缩容

public class demo9 {
    public static void main(String[] args) {
        //定义原数组
        int[] arr1={1,2,3};
        //定义新数组
        int[] arr2 = new int[arr1.length-1];
        //数组拷贝
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = arr1[i];
        }
        //将原数组地址指向新地址
        arr1 = arr2;

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

5.2数组拷贝

    数组拷贝有三种方式

            ①通过自定义将原数组的元素拷贝到新数组当中

            ②System类中提供了一个数组拷贝方式

            ③Arrays类中提供了数组拷贝的方式

System类提供的方式

public class demo11 {
    public static void main(String[] args) {
        int arr1[] = {1,2,3,4,5,6};
        int arr2[] = new int[arr1.length+5];

        /*
        * 参数1：原数组
        * 参数2：原数组起始位置
        * 参数3：目标数组
        * 参数4：目标数组起始位置
        * 参数5：数组拷贝长度
        *
        * */
        System.arraycopy(arr1,2,arr2,3,arr1.length-2);
        for (int i = 0; i < arr2.length; i++) {
            System.out.println(arr2[i]+"\t");
        }
    }
}

Arrays类中提供数组拷贝的方式

import java.util.Arrays;

public class demo10 {
    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5,6};
        //Arrays提供的数组拷贝方法
        //第一个参数，原数组 第二个参数：新数组长度
        arr = Arrays.copyOf(arr,arr.length+1);

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

六，数组的排序

6.1冒泡排序

1，冒泡排序的思想

   ①将相邻的两个元素进行比较，如果前面一个元素比后面一个元素大，就交换位置（一轮一轮比较）直到比较完整的数组。

                    在这一轮可以将最大元素交换到最后

    ②以上操作完成数组的长度-1     

例子：基本实现

public class MaoPao {
    public static void main(String[] args) {
        int arr[] = {1,99,2,44,5,22,45};
        sort1(arr);
    }

    public static void sort1(int[] arr){
        //比较轮数 length-1
        for (int i = 0; i < arr.length-1; i++) {
            //比较次数，每一轮的次数length-1 最后的元素已经没有相邻的了
            for (int j = 0; j < arr.length-1; j++) {
                if (arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        //遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]+"\t");
        }
    }
}

优化1：减少次数的对比（优化次数）

public class MaoPao {
    public static void main(String[] args) {
        int arr[] = {1,99,2,44,5,22,45};
        sort1(arr);
        sort2(arr);
    }
    //冒泡排序的优化实现
    /*
    * 4    3   2   1        3
    * 3    2   1   4        2
    * 2    1   3   4        1
    * 1    2   3   4        0
    * */

    public static void sort2(int[] arr){
        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]){
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }

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

优化2：优化轮数

package com.qfedu;

public class MaoPao {
    public static void main(String[] args) {
        int arr[] = {1,99,2,44,5,22,45};
        sort3(arr);
    } 
public static void sort3(int[] arr){
     for (int i = 0; i < arr.length-1; i++) {
         //假设当前这一轮已经排序完成
         boolean flag = true;

         for (int j = 0;j<arr.length-i-1;j++){
             if (arr[j]>arr[j+1]){
                 int temp = arr[j];
                 arr[j]=arr[j+1];
                 arr[j+1]=temp;
                 flag=false;
             }
         }
         //
         System.out.println("第"+(i+1)+"轮的结果：");
         for (int j = 0; j < arr.length; j++) {
             System.out.println(arr[j]+"\t");
         }
         System.out.println();
         if (flag){
             break;
         }
     }
 }
}

6.2选择排序

   1， 选择排序升序思想

            ①将当前这个位置上的元素与后面每一个元素进行比较，如果有比当前位置小的元素就先记录下来，等所有的元素比较完成之后，进行交换，这个过程可以将最小的值交换到当前位置

            ②以上操作可以将最小的，选择到指定位置，循环以上操作，进行每一个位置挑选

例子：

  public static void sort1(int[] arr){
       for (int i = 0; i <arr.length-1; i++) {//负责选择的位置
           int min=i;
           for (int j = i+1; j < arr.length; j++) {//i+1表示与后面每一个元素作比较 每一个都要遍历所以 不能length-1
               if (arr[min]>arr[j]){
                   min=j;
               }
           }
           //将最小值与当前值进行交换
           if (min !=i){
           int temp=arr[i];
           arr[i]=arr[min];
           arr[min]=temp;
       }
   }
       //遍历数据
       for (int i = 0; i <arr.length ; i++) {
           System.out.print(arr[i]+"\t");
       }
   }

1. 3，Arrays工具类排除方法

package com.qfedu;

import java.util.Arrays;

public class demo5 {
    public static void main(String[] args) {
        int[] arr={22,11,87,45};
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]+"\t");
        }
        System.out.println("-----------------");
        String[] names={"cxk","main","sdsad","sdaw"};//字符串按照首字母ABC表进行排序
        Arrays.sort(names);
        for (int i = 0; i < names.length; i++) {
            System.out.println(names[i]+"\t");
        }
    }
}

七，二分查找法

    二分查找法（折半查找法）

            前提：数组的元素是有序的

    思路

            首先找到这个数组的中间数，与找到的中间元素比较，如相等就代表查找的数找到了

            如果传入的数比中间数大，那么就表示想找的数在元素中间值的右边，所以最大值的下标等于中间值的下标-1

            如果传入的数比中间数小，那么就表示想找的数在元素中间值的左边，所以最小值的下标等于中间值的下标+1

例子：

public class demo6 {
    public static void main(String[] args) {
        int[]  arr= {1,2,3,4,5,6,7};//数组必须有顺序
        System.out.println(seach2(arr,4));
    }
    public static int seach2(int[] arr,int num){
        //1，获取到最大值，最小值
        int min = 0;
        int max = arr.length-1;

        while(min<=max){
            //2，获取到中间值
            int middle = (min+max)/2;

            //3，将查找的数与中间值作比较
            if(num>arr[middle]){
                min=middle+1;
            }else if(num<arr[middle]){
                max=middle-1;
            }else{
                return middle;
            }
        }
        return -1;
    }
}