javajavase
尚硅谷宋红康第3章_数组.pdf 3 数组 - 图1

概述

定义

  • 数组(Array)是多个按一定顺序排列的相同类型数据的集合，使用一个名字命名，并通过编号的方式对这些数据进行统一管理

好处

  • 同时存储多个数，代码简洁，而且提高了效率
  • 分类存储，方便查找

概念

  • 数组名：对一组具有相同数据类型的变量，使用一个名字来进行管理
  • 元素：数组中的每一个数据
  • 索引：数组的每一个元素，依靠下标，索引，编号进行区分
  • 长度：数组的元素的总个数

注意

  • 这一组具有相同数据类型的变量，在堆内存中开辟连续的空间
  • 数组属于引用数据类型的变量。数组的元素，既可以是基本数据类型，也可以是引用数据类型
  • 数组访问里面的元素 ，通过 数组名[下标]， 下标：0——length-1
  • 数组的长度一旦指定不能修改

一维数组

声明

  1. type[] arr_name;    //推荐使用此种方式
  2. type arr_name[];
  • 声明一个数组的时候并没有数组真正被创建，并没有实例化任何对象
  • 只有在实例化数组对象时JVM才分配空间，这时才与长度有关
  • 构造一个数组，必须指定长度

初始化

  • 静态初始化
    1. type[] arr_name = new type[]{element1, element2, …};
    ```java //静态初始化基本类型数组 int[] a = int[]{1, 2, 3};

//静态初始化引用类型数组 Student[] stu = Student[]{new Student(1, “张三”), new Student(2, “李四”)}; 

  2. - **动态初始化**
  3.    - 数组元素分配空间与赋值的操作分开进行
  4. ```java
  5. type[] arr_name = new type[length];
  6. arr_name[0] = element1;
  7. arr_name[1] = element2;
  8. …
  1. int][] a = new int[2];//动态初始化数组，先分配空间
  2. a[0] = 1;//给数组元素赋值
  3. a[1] = 2;//给数组元素赋值
  • 默认初始化
    • 数组是引用类型，它的元素相当于类的实例变量，因此数组一经分配空间，其中的每个元素也被按照实例变量同样的方式被隐式初始化
    • 整型：0
    • 浮点型：0.0
    • char型：0或’\u0000’，而非’0’
    • boolean型：false
    • 引用数据类型：null

长度：**数组名.length**
元素表示：**数组名[下标]**

  • 数组元素下标的合法区间：[0, length-1]，如果超过下标的范围，会报“数组下标越界ArrayIndexOutOfBoundsException”

遍历

  • for循环

    1. for(int i=0; i<数组名.length; i++) {
    2. }

  • for-each循环

    1. for(元素的数据类型  临时变量: 数组名) {
    2. }
    1. String str = {"aa", "bb", "cc", "dd"};
    2. for (String temp: str) {
    3.   System.out.println(temp);
    4. }
    • 增强for循环是JDK1.5新增功能，专门用于读取数组或集合中所有的元素

内存解析

二维数组

声明

  1. type[][]  arr_name;

初始化

  • 静态初始化

    1. type[][] arr_name = {{element, element, …}, {element, element, …}, …};
    1. int[][] a = {{1, 2, 3}, {3, 4}, {3, 5, 6, 7}};    //类型推断

    数组内存.png

  • 动态初始化

    • 规则

      1. arr_name = new type[行数][列数];
      • 总元素的个数是 行数*列数
      • 每一行的列数相同的
    • 不规则
      1. arr_name = new type[行数][];
      ```java 方式一 int[][] a = new int[3][]; a[0] = new int[2]; a[1] = new int[4]; a[2] = new int[3];

方式二 int[][] a = new int[3][]; //🔴 a[0] = {1, 2};//错误，没有声明就初始化，不能类型推断 a[0] = new int[]{1, 2}; a[1] = new int[]{3, 4, 5, 6}; a[2] = new int[]{7, 8, 9};

  1. 长度
  3. - 行数：`**二维数组名.length**`
  4. - 某一行的列数：`**arr_name[行标] .length**`
  6. 元素的表示
  8. - 行对象：`**arr_name[行标]**`
  10. 把二维数组如果看成一个一维数组，那么它的每一个元素就是一个行对象
  12. - 具体的元素：`**二维数组名[行标][列标]**`
  14. 行标的范围：[0, 二维数组名.length)<br />列标的范围：[0, 二维数组名[i].length)<br />遍历
  16. - for
  17. ```java
  18. for(int i=0; i<array.length; i++) {
  19.     for(int j=0; j<array[i].length; j++) {
  20.         array[i][j]代表一个元素
  21.     }
  22. }
  • 增强for ```java for(行对象的类型 行对象名: 二维数组名) { for(元素的类型 临时变量: 行对象名) {
    1.   临时变量代表每一行中的某个具体元素
    } }

操作二维数组不应使用常数来控制维数。 具体方法是array.length表示行，array[row].length来表示row行的列数。 这样当数组每行行的列数不相等时，代码可以自动调整为正确的值

  2. ---
  4. <a name="xGIqF"></a>
  5. ## 对象数组
  6. 格式：
  7. ```java
  8. 引用类型[] 变量名;
  9. 变量名 = new 引用类型[长度];    //开辟空间(指定长度)

赋值

  • 先创建对象（也就是房间中打算放的内容）**Student s = new Student();**
  • 将对象放到指定的数组某个空间中**数组名[下标] = s;**

使用

  • 循环打印

    1. for(int i=0; i<数组名.length; i++) {
    2.   数组名[i] .方法()/属性;
    3. }

  • 循环判断

    1. for(int i=0; i<数组名.length; i++) {
    2.   if(数组名[i].属性 < max) {
    3.   }
    4. }

数组常见异常

NullPointerException 空指针异常
ArrayIndexOutofBoundsException 数组下标越界

常见算法

赋值

  • 杨辉三角 ```java // 1.声明并初始化二维数组 int[][] yangHui = new int[10][];

// 2.给数组的元素赋值 for(int i = 0; i < yangHui.length; i++) { yangHui[i] = new int[i + 1];

  1. // 2.1 给首末元素赋值
  2. yangHui[i][0] = yangHui[i][i] = 1;  
  3. // 2.2 给每行的非首末元素赋值
  4. for(int j = 1; j < yangHui[i].length - 1; j++) { 
  5.     yangHui[i][j] = yangHui[i-1][j-1] + yangHui[i-1][j];
  6. }

}

  2. - 回行数
  4. 求数组元素最大 最小 平均值 和<br />复制 反转 查找
  6. - 二分查找
  7. ```java
  8. //前提：所要查找的数组必须有序。
  9. int[] arr = new int[]{-98,-34,2,34,54,66,79,105,210,333};
  10. int dest1 = -34;
  11. int head = 0;//初始的首索引
  12. int end = arr.length - 1;//初始的末索引
  13. boolean isFlag = true;
  15. while(head <= end) {
  16.     int middle = (head + end)>>1;
  17.     if(dest1 == arr[middle]) {
  18.         System.out.println("找到了指定的元素，位置为：" + middle);
  19.         isFlag = false;
  20.         break;
  21.     } else if(arr[middle] > dest1) {
  22.         end = middle - 1;
  23.     } else {
  24.         head = middle + 1;
  25.     }
  26. }
  28. if(isFlag) {
  29.     System.out.println("很遗憾，没有找到的啦！");
  30. }

排序

  • 衡量排序算法的优劣
    1. 时间复杂度：分析关键字的比较次数和记录的移动次数
    2. 空间复杂度：分析排序算法中需要多少辅助内存
    3. 稳定性：若两个记录A和B的关键字值相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的

  • 排序算法性能对比 | 排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | —- | —- | —- | —- | —- | —- | | 插入 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | | 希尔 | O(n1.3) | O(n2) | O(n) | O(1) | 不稳定 | | 选择 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | | 堆 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | | 冒泡 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | | 快速 | O(nlogn) | O(n2) | O(nlogn) | O(nlogn) | 不稳定 | | 归并 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | | 计数 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 | | 桶 | O(n+k) | O(n2) | O(n) | O(n+k) | 稳定 | | 基数 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |

  • 冒泡排序

    1. public static void main(String[] args) {
    2.   int[] arr = new int[]{43,32,76,-98,0,64,33,-21,32,99};
    3.   //冒泡排序
    4.   boolean isflag = true;
    5.   for(int i = 0; i < arr.length - 1; i++) {
    6.       for(int j = 0; j < arr.length - 1 - i; j++) {
    7.           if(arr[j] > arr[j + 1]) {
    8.               int temp = arr[j];
    9.               arr[j] = arr[j + 1];
    10.               arr[j + 1] = temp;
    11.               isflag = false;
    12.           }
    13.       }
    15.       if (isflag) {
    16.           break;
    17.       }
    18.   }
    20.   for(int i = 0; i < arr.length; i++) {
    21.       System.out.print(arr[i] + "\t");
    22.   }
    23. }

  • 快速排序 ```java public static void quickSort(int[] data) { subSort(data, 0, data.length-1); }

private static void subSort(int[] data, int start, int end) { if (start < end) { int base = data[start]; int low = start; int high = end + 1;

  1.     while (true) {
  2.         while (low < end && data[++low] - base <= 0)
  3.             ;
  4.         while (high > start && data[--high] - base >= 0)
  5.             ;
  6.         if (low < high) {
  7.             swap(data, low, high);
  8.         } else {
  9.             break;
  10.         }
  11.     }
  12.     swap(data, start, high);
  14.     subSort(data, start, high - 1);//递归调用
  15.     subSort(data, high + 1, end);
  16. }

}

private static void swap(int[] data, int i, int j) { int temp = data[i]; data[i] = data[j]; data[j] = temp; } ```

工具类Arrays

比较两个数组是否相等：
**public static boolean equals(int[] a, int[] a2)**
输出数组信息，转成字符串
**public static String toString(int[] a)**
字符串表示形式由数组的元素列表组成，括在方括号(“[]”)中。相邻元素用字符 “, “(逗号加空格)分隔
排序
**public static void sort(int[] a)**
引用类型的数组排序需要java.lang.Comparable或java.util.Comparator接口的支持
查找
**public static int binarySearch(int[] a, int key)**
a数组必须是排好序的
填充
**public static void fill(int[] a, int value)**
给a数组的每一个元素填充为val
**public static void fill(int[] a, int fromIndex, int toIndex, int value)**
给数组a中fromIndex到toIndex之间的元素填充为val
复制
**public static int[] copyOf(int[] original, int newLength)**
复制original数组，得到一个新的数组，新的数组的长度是newLength
如果newLength如果newLength>original数组的长度，相当于新的数组的前面的元素都是和original数组一样的，剩下的元素都是默认值
**public static int[] copyOfRange(int[] original, int from, int to)**
从original数组的from开始复制到to这个部分的元素，产生一个新的数组
from必须在original数组的[0, original数组长度]范围之内
to可以在original数组下标范围内，也可以超过，如果超过，超过的部分使用默认值
转换为List

  • **public static <T> List<T> asList(T... a)**

System类中方法
**static void arraycopy(object src，int srcpos，object dest， int destpos，int length)**