Java数组和Arrays类

Java的内存分配

概念

• 栈 : 存放的是局部变量
  • 局部变量：在方法定义或者方法声明上的变量都是局部变量。
• 堆: 存放的是所有new出来的东西
  • 每一个new出来的东西都会为其分配一个地制值。
  • 每一个变量都有一个默认的值
  • 使用完毕就变成了垃圾，等待垃圾回收器对其回收
• 方法区:(面向对象部分讲解)
• 本地方法区:(和系统相关)
• 寄存器:(cpu使用)

栈和堆的区别

• 栈内存：模拟的是后进先出的数据结构

  • 入栈：存储数据,只能从栈顶入
  • 弹栈：取出数据,只能从栈顶出

• 栈的内存相对其他区，容量小

  • 存储基本数据和引用类型数据
  • 频繁创建和销毁的数据

• 堆内存

  • 栈的内存大
  • 存储对象的数据
  • 不会频繁创建和销毁

数组

• 数组概念
  • 数组是一个容器，可以存储多个变量，这些变量数据类型要一致
  • 数组既可以存储基本数据类型，也可以存储引用数据类型

一维数组

• 数组定义格式

  • 格式1：数据类型[] 数组名

  • 格式2：数据类型 数组名[]

    int[] a；     定义了一个int类型的数组a；
    int a[];    定义了一个int类型的a数组；
    //推荐使用第一种定义方式。
    数据类型[] 数组名 = new 数据类型[数组长度];

• 数组的初始化

  • Java中的数组必须先初始化,然后才能使用。
  • 所谓初始化：就是为数组中的数组元素分配内存空间，并为每个数组元素赋值。

• 初始化分类：

  • 动态初始化: 只指定长度，由系统给出初始化值

    我们规定长度，系统赋。 格式： 初始化值：数据类型	默认值
    byte，short，int，long	0
    float，double	0.0
    char	‘\u0000’
    boolean	false
    String[](引用类型)	null

  • 静态初始化: 给出初始化值，由系统决定长度

    • 格式：数据类型[] 数组名 = new 数据类型[]{元素，元素，（元素，.....）}
    • 简写：数据类型[] 数组名 = {元素，元素，（元素，.....）}

  • 注意事项：这两种方式，只能使用一种，不能进行动静结合

二维数组

• 数组定义格式

  • 数据类型[][] 变量名 = new 数据类型[m][n];
  • m:表示这个二维数组有多少个一维数组
  • n:表示每一个一维数组的元素个数
  • 本质是一个一元数组里放一个一元数组

• 举例:

  int[][] arr = new int[3][2];
  定义了一个二维数组arr
  这个二维数组有3个一维数组，名称是arr[0],arr[1],arr[2]
  每个一维数组有2个元素，可以通过arr[m][n]来获取,表示获取第m+1个一维数组的第n+1个元素

• 遍历二维数组

  Scanner sc = new Scanner(System.in);
  int[][] arr = new int[2][3];
  //赋值
  for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 3; j++) {
          System.out.print("请输入：");
          arr[i][j] = sc.nextInt();
      }
  }
  
  // 遍历
  for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 3; j++) {
          System.out.print(arr[i][j]+ " ");
      }
      System.out.println();
  }

不规则二维数组

格式：

int[][] arr2 = new int[][]{{1},{1,2},{1,2,3}};

int[][] arr = new int[row][];

for(int i=0;i<row;i++){
	arr[i]=new int[i+1];
}
//不初始化会报空指针异常

杨辉三角形

for(int i=0;i<row;i++){
    arr[i]=new int[i+1];
    for(int j=0;j<arr[i].length;j++){
        if(j==0||j==arr[i].length-1){
            arr[i][j]=1;
        }else{
            arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
        }

        System.out.print(arr[i][j]+"\t");
    }
    System.out.println();
}

数组的常用操作

最大值

int[] arr = { 15, 21, 36, 100, 89, 78 };
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}
System.out.println("最大值：" + max);

最小值

int[] arr = { 15, 21, 36, 100, 89, 78 };
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
	if (arr[i] < max) {
		min = arr[i];
	}
}
System.out.println("最大值：" + min);

数组的遍历

for循环遍历

• 代码如下：

  int[] arr = { 15, 21, 36, 100, 89, 78 };
  for (int i = 0; i < arr.length - 1; i++) {
  		System.out.println(arr[i]);
  	}
  }

增强for遍历

• 写法更加简洁，一个一个向后访问，不用考虑越界。

• 只能顺序遍历，不能改变元素的值(对象的属性可以改)

  int[] arr = { 15, 21, 36, 100, 89, 78 };
  for( int a : arr){
  	System.out.print(a+" ");
  }

数组排序

• 升序：从小到大
• 降序：从大到小

冒泡排序

• 效率并不高

• 冒泡排序是将数组中的两个元素进行比较，并将最小的元素交换到前面

  int[] arr = { 15, 21, 36, 100, 89, 78 };
  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;
  		}
  	}
  }
  System.out.println(Arrays.toString(arr));

选择排序

• 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

• 代码如下：

  private static void sort(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;
  			}
  		}
  	}
  	for(int a : arr) {
  		System.out.print(a+" ");
  	}
  }

插入排序

• 检查数组列表中的每个元素，并将其放入已排序元素中的适当位置(类似我们打扑克牌)
• 当最后一个元素放入合适位置时，该数组排序完毕

public static void main(String[] args) {
    int[] arr = new int[] { 12, 56, 32, 76, 8, 45, 61 };
    Demo1.sort(arr);
}

private static void sort(int[] arr) {
    for(int i = 1;i<arr.length;i++){
        for(int j=0;j<i;j++){
            if(arr[i]<arr[j]){
                // 需要插入arr[i],j到i的元素需要向后移动
                int temp=arr[i];
                for(int k=i;k>j;k--){
                    arr[k]=arr[k-1];
                }
                arr[j]=temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}


// 另外写法
public static void StraightInsertSort(int[] a) {
    int temp = 0,j = 0;
    for(int i = 1;i < a.length;i++){
        temp = a[i];
        j = i;
        // 如果遍历的数据temp小于已排序的最后一个a[j-1]
        while(j > 0 && a[j-1] >= temp){
            //则将前一位往后移，以此类推，直到找到比temp小的元素
            a[j] = a[j-1];
            j--;
        }
        //这时将temp插入进去
        a[j] = temp;
    }
}

二分插入排序

• 将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较，即可得到折半插入排序算法

• 在处理A[i]时，A[0]……A[i-1]已经按关键码值排好序。

• 所谓折半比较，就是在插入A[i]时，取A[(i-1)/2]的关键码值与A[i]的关键码值进行比较

  • 如果A[i]的关键码值小于A[(i-1)/2]的关键码值，则说明A[i]只能插入A[0]到A[i-1/2]之间，
    • 故可以在A[0]到A[(i-1)/2 - 1]之间继续使用折半比较；
  • 否则只能插入A[(i-1)/2]到A[i-1]之间，故可以在A[(i-1)/2 + 1]到A[i-1]之间继续使用折半比较。
  • 直到最后能够确定插入的位置为止。经过一次比较即可排除一半记录，把可能插入的区间减小了一半，故称为折半。

• 执行折半插入排序的前提是文件记录必须按顺序存储。

  public static void binaryInsertSort(int array[],int size) {
      int i,j,k,temp;
      for(i=1;i<size;i++)      {
          temp=array[i];
          if(array[i]<array[0])
              k=0;
          else
              k = binarySearch(array,0,i,temp);
  		// 将k-i的数据后移
          for(j=i;j>k;j--)          {
              array[j]=array[j-1];
          }
          array[k]=temp;
          System.out.println(Arrays.toString(array));
      }
  }

数组查找

普通遍历查找

• 代码如下：

  public static void main(String[] args) {
      //一维数组的定义和初始化
      int[] scores={90,70,50,80,60,85};
      System.out.println("请输入要查找的值value:");
      Scanner in=new Scanner(System.in);
      int value=in.nextInt();
      //. 遍历数组scores中的值, 如果有值与 给定的value相等  打印出当前索引
      //否则打印-1 没有找到
      boolean isSearch=false;
      for(int i=0;i<scores.length;i++) {
          if(scores[i]==value) {
              isSearch=true;
              System.out.println("找到值:"+value+" 在数组scores中的索引为: "+i);
              break;
          }
      }
      if(!isSearch)    {
          System.out.println("在数组scores中没有找到 值 : "+value);
      }
  }

二分查找

Scanner superman = new Scanner(System.in);
int start = 0;
int end = arr.length-1;

//中间位置
int middle = (start + end) / 2;

System.out.println("--输入要找的数字：");
int n = superman.nextInt();

//中间位置数字不等于 查找的数就循环
while(arr[middle] != n) {
    if(n > arr[middle]) {
        start = middle +1;
    }else if(n < arr[middle]) {
        end = middle -1;
    }
    if(start > end) {
        middle = -1;
        System.out.println("不存在");
        break;
    }
    middle = (start + end) / 2;
}
System.out.println(middle);

//Arrays.binarySearch(int[] a, int key)
public static int binarySearch(Integer[] srcArray, int des)
{
    // 定义初始最小、最大索引
    int low = 0;
    int high = srcArray.length - 1;
    // 确保不会出现重复查找，越界
    while (low <= high)
    {
        // 计算出中间索引值
        // (high + low) >>> 1 等同于 (high+low)/2,但是要求high和low的合要大于等于0
        //>>>是位运算符，只对整型有效（不能用于浮点型）。
        //这里计算平均值使用>>>取代>>，是因为可能出现很大的数字，这些数字单独用不会超过Integer.MAX_VALUE，
        //但求和之后可能超过，这时如果使用>>或者/来计算，会因为溢出而算出负数结果。
        int middle = (high + low) >>> 1;
        if (des == srcArray[middle])
        {
            return middle;
            // 判断下限
        }
        else if (des < srcArray[middle])
        {
            high = middle - 1;
            // 判断上限
        }
        else
        {
            low = middle + 1;
        }
    }
    // 若没有，则返回-1
    return -1;
}

数组的复制

• 在 Java 中实现数组复制分别有以下 4 种方法：
  1. Arrays 类的 copyOf() 方法
  2. Arrays 类的 copyOfRange() 方法
  3. System 类的 arraycopy() 方法
  4. Object 类的 clone() 方法
• Object.clone 和 System.arraycopy 都可以实现数组引用区的完全复制。对复制后的新数组的引用区进行操作不影响原数组引用区内容 ,但System.arraycopy()更快速。 (引用区指的是:对象的指针列表)。

System.arraycopy

• arraycopy 常用于数组扩容

• public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

  • Object src : 原数组
  • int srcPos : 从元数据的起始位置开始
  • Object dest : 目标数组
  • int destPos : 目标数组的开始起始位置
  • int length : 要copy的数组的长度

  // 源数组:数组的总长度为 12位
  byte[]  srcBytes = new byte[]{2,4,0,0,0,0,0,10,15,50};
  // 目标数组
  byte[] destBytes = new byte[5];
  // 我们使用System.arraycopy进行转换(copy)
  // 将srcBytes源数组中 从0位开始取5个数值 copy 到 destBytes目标数组中,在目标数组的第0位开始放置.
  System.arrayCopy(srcBytes,0,destBytes,0,5)
  //运行效果应该是 2,4,0,0,0,

Object.clone

• protected Object clone() 创建并返回此对象的副本。

• 代码如下：

  public static void main01(String[] args) {
  	String[] array01 = new String[]{"01", "02", "03"};
  	String[] array02 = array01.clone();
  	System.out.println(array01);
  	System.out.println(array02);
  	array02[1] = "将哈哈哈哈";
  	array02[2] = null;
  	System.out.println(Arrays.toString(array01));
  	System.out.println(Arrays.toString(array02));
  
  	/*
  	->输出:
  	[Ljava.lang.String;@16acdd1
  	[Ljava.lang.String;@ee6681
  	[01, 02, 03]
  	[01, 将哈哈哈哈, null]
  	*/
  }

小总结

拷贝内容

• System.arraycopy() 和 array.clone() 都是引用区拷贝,不拷贝元素对象。

• 代码如下：

  /**
   * 对象拷贝内容测试
   */
  public static void main(String[] args) {
  	Object[] array01 = new Object[]{new Object(), new Object(), new Object()};
  	Object[] array02 = array01.clone();
  	System.out.format("%s->%s\n", array01, Arrays.toString(array01));
  	System.out.format("%s->%s\n", array02, Arrays.toString(array02));
  
  	array02 = new Object[array01.length];
  	System.arraycopy(array01, 0, array02, 0, array01.length);
  	System.out.format("%s->%s\n", array01, Arrays.toString(array01));
  	System.out.format("%s->%s\n", array02, Arrays.toString(array02));
  
  	/*
  	->输出:
  	[Ljava.lang.Object;@a0864f->[java.lang.Object@facf0b, java.lang.Object@2f0df1, java.lang.Object@13c6a22]
  	[Ljava.lang.Object;@d1e233->[java.lang.Object@facf0b, java.lang.Object@2f0df1, java.lang.Object@13c6a22]
  	[Ljava.lang.Object;@a0864f->[java.lang.Object@facf0b, java.lang.Object@2f0df1, java.lang.Object@13c6a22]
  	[Ljava.lang.Object;@15983b7->[java.lang.Object@facf0b, java.lang.Object@2f0df1, java.lang.Object@13c6a22]
  	*/
  }

速度

• 当复制类型无论为对象类型还是基本数据:System.arraycopy() 的速度都是 array.clone()的9-10倍。

• java中System.nanoTime()返回的是纳秒，nanoTime而返回的可能是任意时间，甚至可能是负数……

• java中System.currentTimeMillis()返回的毫秒，这个毫秒其实就是自1970年1月1日0时起的毫秒数.

• ns（nanosecond）：纳秒， 时间单位。一秒的10亿分之一，即等于10的负9次方秒。常用作 内存读写速度的单位。

  • 1纳秒=0.000001 毫秒
  • 1纳秒=0.00000 0001秒

• 代码如下:

  /**
   * 对象类型的元素拷贝速度测试
   */
  public static void main02(String[] args) {
      // String对象
      String[] array01 = new String[]{"01", "02", "03"};
      long begin = System.nanoTime();
      for (int i = 0; i < 100000000; i++) {
          // String[] array02 = array01.clone();
          String[] array02 = new String[array01.length];
          System.arraycopy(array01, 0, array02, 0, array01.length);
      }
      long end = System.nanoTime();
      System.out.println(end - begin);
  
      /*
      ->输出:
      使用 array.clone():
      13189919392
      使用 System.arraycopy():
      1689826432
      */
  }
  
  
  /**
  * 基本数据类型的元素拷贝速度测试
    */
  public static void main03(String[] args) {
    int[] array01 = new int[]{01, 02, 03};
    long begin = System.nanoTime();
    for (int i = 0; i < 100000000; i++) {
        int[] array02 = array01.clone();
        // int[] array02 = new int[array01.length];
        // System.arraycopy(array01, 0, array02, 0, array01.length);
    }
    long end = System.nanoTime();
    System.out.println(end - begin);
  
    /*
    ->输出:
    使用 array.clone():
    12566117948
    使用 System.arraycopy():
    1488130581
    */
  }

Arrays类

常用方法

方法名	描述
toString(array)	数组变字符串
parallelSort(array)	在多核的情况下排序
sort(array)	升序排序
sort(array ,start,end)	对范围[start,end)的数据排序
binarySearch(arr ,searchValue)	二分查找，返回下标（前提：排好序的数组）
	找不到:返回插入的位置（下标+1）的负数
equals()	判断数组元素是否相等，个数和位置都要相同
fill()	数据填充
fill(arr,起始位置，结束位置，填充值)	对指定范围内的数据填充
copyof(arr,元素个数)	产生新的数组对象
copyofRange(arr,from ,to)	复制[fron，to)范围元素，返回数组对象

Arrays.copyOf

• 从代码可知，数组拷贝时调用的是本地方法 System.arraycopy() ；

• Arrays.copyOf()方法返回的数组是新的数组对象，原数组对象仍是原数组对象，不变，

  • 该拷贝不会影响原来的数组。
  • copyOf()的第二个自变量指定要建立的新数组长度，如果新数组的长度超过原数组的长度，则保留数组默认值.

  public static <T> T[] copyOf(T[] original, int newLength) {
      return (T[]) copyOf(original, newLength, original.getClass());
  }
  
  
  public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
      T[] copy = ((Object)newType == (Object)Object[].class)
          ? (T[]) new Object[newLength]
          : (T[]) Array.newInstance(newType.getComponentType(), newLength);
      System.arraycopy(original, 0, copy, 0,
                       Math.min(original.length, newLength));
      return copy;
  }
  
  int[] arr = { 15, 21, 36, 100, 89, 78 };
  int[] arr5 = Arrays.copyOf(arr, arr.length);
  System.out.println("arr5:" + Arrays.toString(arr5));