数组的概念

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

• 数组的常见概念

  • 数组名
  • 下表（索引）
  • 元素
  • 数组的长度
• 数组本身是 引用数据类型，而数组中的元素可以是任何数据类型，也包括基本数据类型和引用数据类型。
• 创建数组对象会在内存中开辟一块连续的空间，而数组名中引用的是这块连续空间的首地址
• 数组的长度 一旦确定，就不能修改
• 我们可以直接通过下标（索引）的方式调用指定位置的元素，速度很快

• 数组的分类：

  • 按照维度：

    • 一维数组
    • 二维数组
    • 三维数组

  • 按照元素的数据类型:

    • 基本数据类型元素的数组
    • 引用数据类型元素的数组（即对象数组）

一维数组

一维数组的声明和初始化

int[] ids;  // 声明
// 1.1 静态初始化
ids = new int[]{1001,1002,1003,1004};
// 1.2 动态初始化
String[] name = new String[5];

如何调用数组的指定位置的元素

// 数组的角标（索引）是从 0 开始，到数组的长度 -1 结束
name[0] = "张三";
name[1] = "李四";
name[2] = "王五";
name[3] = "zhangsan";
name[4] = "lisi";

如何获取数组的长度

使用 length 属性

name.length

如何遍历数组

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

数组元素的默认初始化值

• 整形：0
• 浮点型：0.0
• char：0 或 '\u0000'
• boolean：false

练习

从键盘读入学生成绩，找出最高分,并输出学生成绩等级。

成绩>=最高分-10等级为 A

成绩>=最高分-20等级为 B

成绩>=最高分-30等级为 C

其余 等级为 D

import java.util.Scanner;
public class ArrayDemo1 {
    public static void main(String[] args) {
        // 1. 使用 Scanner，读取学生个数
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入学生人数：");
        int number = scanner.nextInt();

        // 2. 创建数组，存储学生成绩：动态初始化
        int[] scores = new int[number];

        // 3. 给数组中的元素赋值
        System.out.println("请输入 " + number + " 个学生成绩:");
        int maxScore = 0;
        for (int i = 0; i < scores.length; i++) {
            scores[i] = scanner.nextInt();
            // 4. 求出数组中的元素的最大值
            if (maxScore < scores[i]) {
                maxScore = scores[i];
            }
        }

        // for (int i = 0; i < scores.length; i++) {
        //
        // }

        // 5. 根据每个学生成绩与最高分的插值，得到每个学生的等级，并输出等级和成绩
        char level;
        for (int i = 0; i < scores.length; i++) {
            if (maxScore - scores[i] <= 10) {
                level = 'A';
            } else if (maxScore - scores[i] <= 20) {
                level = 'B';
            } else if (maxScore - scores[i] <= 30) {
                level = 'C';
            } else {
                level = 'D';
            }
            System.out.println("student " + i + " score is " + scores[i] + " ,grade is " + level);
        }
        System.out.println("最高分为：" + maxScore);

    }
}

多维数组

• Java 语言里提供了支持多维数组的语法
• 如果说可以把一维数组当成几何中的线性图形，那么二维数组就相当于是一个表格，像 Excel 中的表格一样
• 对于二维数组的理解，我们可以堪称是一维数组 array1 又作为另一个数组 array2 的元素而存在。其实，从数组底层的运行机制来看，其实没有多维数组

二维数组的声明和初始化

// 静态初始化
int[][] arr1 = new int[][] { { 1, 2, 3, }, { 4, 5, }, { 6, 7, 8 } };
// 动态初始化 1
String[][] arr2 = new String[3][2];
// 动态初始化 2
String[][] arr3 = new String[3][];

如何调用数组的指定位置的元素

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

如何获取数组的长度

System.out.println(arr2.length);  // 3
System.out.println(arr2[0].length);  // 2
System.out.println(arr2[1].length);  // 2

如何遍历数组

for (int i = 0; i < arr2.length; i++) {
    for (int j = 0; j < arr2[i].length; j++) {
        System.out.print(arr2[i][j] + " ");
    }
    System.out.println();
}
/* 
   1 2 3
   4 5
   6 7 8
*/

数组元素的默认初始化值

初始化方式一：int[][] arr = new int[4][3];

• 外层元素的初始化值为：地址值
• 内层元素的初始化值为：与一维数组初始化情况相同

初始化方式二：int[][] arr = new int[4][];

• 外层元素的初始化值为：null
• 内层元素的初始化值为：不能调用，否则报错

练习

使用二维数组打印一个 10 行的杨辉三角

 /* 
 * 1.第一行有1个元素，第n行有n个元素
 * 2.每一行的第一个元素和最后一 个元素都是1
 * 3.从第三行开始，对于非第一一个元素和最后一个元素的元素。即:
 * yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
 */
public class YangHuiTest {
    public static void main(String[] args) {
        // 1. 声明并初始化
        int[][] yanghui = new int[10][];

        // 2. 给数组的元素赋值
        for (int i = 0; i < yanghui.length; i++) {
            yanghui[i] = new int[i + 1];
            // 2.1 给首末元素赋值
            yanghui[i][0] = yanghui[i][i] = 1;
            // 2.2 给非首末元素赋值
            for (int j = 1; j < yanghui[i].length - 1; j++) {
                yanghui[i][j] = yanghui[i - 1][j - 1] + yanghui[i - 1][j];
            }
        }
        // 3. 遍历二维数组
        for (int i = 0; i < yanghui.length; i++) {
            for (int j = 0; j < yanghui[i].length; j++) {
                System.out.print(yanghui[i][j] + " ");
            }
            System.out.println();
        }
    }
}

数组中涉及到的常见算法

1. 数组元素的赋值（杨辉三角、回形数等）
2. 求数值型数组中元素的最大值、最小值、平均数、总和等
3. 数组的复制、反转、查找（线性查找、二分法查找）
4. 数组元素的排序算法

排序算法

排序：假设含有 n 个记录的序列为 {R1,R2,……,Rn}，其相应的关键字序列为 {K1,K2,……,Kn}。将这些记录重新排序为 {Ri1,Ri2,……,Rin}，是的相应的关键字值满足条 Ki1 <= Ki2 <= …… <= Kin，这样的一种操作称为排序

• 通常来说，排序的目的是快速查找

衡量算法的优劣

1. 时间复杂度

   分析关键字的比较次数和记录的移动次数

2. 空间复杂度

   分析排序算法中需要多少辅助内存

3. 稳定性

   若两个记录 A 和 B 的关键字值相等，但排序后 A B 的先后次序保持不变，则称这种排序算法是稳定的

排序算法的分类

• 内部排序

  • 整个排序过程中不需要借助于外部存储器（如磁盘等），所有的排序操作都在内存中完成

• 外部排序

  • 参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序/可以认为外部排序是由多次内部排序组成

十大内部排序算法

• 选择排序

  • 直接选择排序、堆排序

• 交换排序

  • 冒泡排序、快速排序

• 插入排序

  • 直接插入排序、折半插入排序、Shell 排序
• 归并排序
• 桶式排序
• 基数排序

各种内部排序方法性能比较

1. 从平均时间而言

   快速排序最佳。但在最坏的情况下时间性能不如堆排序和归并排序

2. 从算法简单性看

   由于直接训责排序、直接插入排序和冒泡排序的算法比较简单，将其认为是简单算法。对于 Shell 排序、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序

3. 从稳定性看

   直接插入排序、冒泡排序和归并排序是稳定的；而且直接选择排序、快速排序、Shell 排序和堆排序是不稳定排序

4. 从待排序的记录数n的大小看

   n 较小时；宜采用简单排序；而 n 较大时宜采用改进排序

算法的5大特征

说明：满足确认定性的算法也成为：确定性算法。现在人们也关注更广泛的概念，例如：考虑各种非确定性的算法，如并行算法、概率算法等。另外，人们也关注并不要求终止的计算描述，这种描述有时候被称为过程（procedure）

冒泡排序

// 冒泡排序
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;
        }
    }
}