3.1 数组的概述
- 数组（Array），是多个相同数据类型按一定顺序排列的集合，使用一个名字命名，并通过编号的方式对这些数据进行统一管理。
- 数组的常见概念
- 数组名
- 下标（或索引）
- 元素
- 数组的长度
- 数组本身是引用数据类型，而数组中的元素可以是任何数据类型，包括基本数据类型和引用数据类型。
- 创建数组对象会在内存中开辟一整块连续的空间。
- 数组的长度一旦确定，就不能修改。
- 我们可以直接通过下标（或索引）的方式调用指定位置的元素，速度很快。
- 数组的分类
- 按照维度：一维数组、二维数组……
- 按照数组元素的类型：基本数据类型元素的数组、引用数据类型元素的数组（即对象数组）
3.2 一维数组
3.2.1 一维数组的声明和初始化
- 数组一旦初始化完成，其长度就确定了。
1、静态初始化
- 数组的初始化和数组元素的赋值操作同时进行。
int[] arr1 = new int[]{1, 2, 3, 4};
int[] arr2 = {1, 2, 3, 4};
/* 报错
int[] arr3;
arr3 = {1, 2, 3, 4};
*/2、动态初始化
- 数组的初始化和数组元素的赋值操作分开进行。
int[] arr3 = new int[4]; arr3[0] = 1; arr3[1] = 2; arr3[2] = 3; arr3[3] = 4;
3.2.2 如何调用数组的指定位置的元素
通过索引的方式调用。
数组的索引从0开始，到数组的长度-1结束。
String[] names = {"张三", "李四", "王五", "赵六"};
String name1 = names[0];
String name2 = names[1];
String name3 = names[2];
String name4 = names[3];3.2.3 如何修改数组的指定位置的元素
通过索引的方式调用。
数组的索引从0开始，到数组的长度-1结束。
String[] names = {"张三", "李四", "王五", "赵六"};
names[0] = "一一";
names[1] = "二二";
names[2] = "三三";
names[3] = "四四";3.2.4 如何获取数组的长度
- 属性：length。
String[] names = {"张三", "李四", "王五", "赵六"};
int length = names.length; // 43.2.5 如何遍历数组
- 循环。
String[] names = {"张三", "李四", "王五", "赵六"};
// for循环
for(int i = 0; i < names.length; i++) {
System.out.println(names[i]);
}
// 增强for循环
for(String name : names) {
System.out.println(name);
}3.2.6 数组元素的默认初始化值
- 基本数据类型
- 整型（byte、short、int、long）：0
- 浮点型（float、double）：0.0
- 字符型（char）：‘\u0000’
- 布尔型（boolean）：false
- 引用数据类型：null
3.2.6 数组的内存解析
3.2.7 例题
从键盘读入学生成绩，找出最高分，并输出学生成绩等级。
import java.util.Scanner;
public class Test {
public static void main(String[] args) {
// 1、使用Scanner，读取学生个数
Scanner scan = new Scanner(System.in);
System.out.println("请输入学生人数：");
int num = scan.nextInt();
// 2、创建数组，存储学生成绩（动态初始化）
int[] scores = new int[num];
// 3、给数组中的元素赋值
System.out.println("请输入" + num + "个学生成绩：");
for(int i = 0; i < scores.length; i++) {
scores[i] = scan.nextInt();
}
scan.close();
// 4、获取数组中的元素的最大值（最高分）
int maxScore = scores[0];
for(int i = 1; i < scores.length; i++) {
if(scores[i] > maxScore) {
maxScore = scores[i];
}
}
// 5、根据每个学生成绩与最高分的差值，得到每个学生的等级，并输出等级和成绩
for(int i = 0; i < scores.length; i++) {
switch((maxScore-scores[i])/10) {
case 0:
System.out.println("等级：A，成绩：" + scores[i]);
break;
case 1:
System.out.println("等级：B，成绩：" + scores[i]);
break;
case 2:
System.out.println("等级：C，成绩：" + scores[i]);
break;
default:
System.out.println("等级：D，成绩：" + scores[i]);
}
}
}
}3.3 数组
- Java语言里提供了支持***数组的语法。
- 如果说可以把一维数组当成几何中的线性图形，那么二维数组就相当于是一个表格。
- 对于二维数组的理解，我们可以看成是一维数组array1又作为另一个一维数组array2的元素而存在。
- 其实，从数组底层的运行机制来看，并没有***数组。
3.3.1 二维数组的声明和初始化
1、静态初始化
int[][] arr1 = new int[][]{{1,2,3},{4,5,6},{7,8,9}};
int[][] arr2 = {{1,2,3},{4,5,6},{7,8,9}};2、动态初始化
String[][] arr1 = new String[3][2];
for(int i = 0; i < arr1.length; i++) {
for(int j = 0; j < arr1[0].length; j++) {
arr1[i][j] = "name";
}
}
String[][] arr2 = new String[3][];
for(int i = 0; i < arr2.length; i++) {
arr2[i] = new String[2];
}3.3.2 如何调用二维数组的指定位置的元素
String[][] names = new String[]{{"张一","张二","张三"},{"李一","李二","李三"};
names[0][0]; // "张一"
names[1][1]; // "李二"3.3.3 获取数组的长度
String[][] arr = new String[3][2];
int len1 = arr.length; // 3
int len2 = arr[0].length; // 23.3.4 如何遍历二维数组
int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};
for(int i = 0; i < arr.length; i++) {
for(int j = 0; j < arr[i].length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
/*
1 2 3
4 5 6
7 8 9
*/3.3.5 二维数组元素的默认初始化值
int[][] arr1 = new int[4][3];
arr1[0]; // 地址
arr1[0][0]; // 0
int[][] arr2 = new int[4][];
arr2[0]; // null
arr2[0][0]; // 报错:java.lang.NullPointerException3.3.6 二维数组内存解析
3.3.7 练习
- 练习1
声明：
int[] x, y[];
在给变量赋值以后，以下选项允许通过编译的是：
x[0] = y; // ×
y[0] = x; // √
y[0][0] = x; // ×
x[0][0] = y; // ×
y[0][0] = x[0]; // √
x = y; // ×- 练习2
使用二维数组打印一个10行杨辉三角。
提示：
第一行有1个元素，第n行有n个元素
每一行的第一个元素和最后一个元素都是1
从第三行开始，对于非第一个元素和最后一个元素的元素：yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j]
import java.util.Arrays;
public class Test {
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];
yanghui[i][0] = 1;
yanghui[i][i] = 1;
if(i > 1) {
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[] arr : yanghui) {
System.out.println(Arrays.toString(arr));
}
}
}- 练习3
创建一个长度为6的int型数组，要求数组元素的值都在1~30之间，且是随机赋值。同时，要求元素的值各不相同。
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = new int[6];
int num;
boolean flag;
for (int i = 0; i < arr.length; i++) {
flag = true;
while (true) {
num = (int) (Math.random() * 30 + 1);
for (int j = 0; j < i; j++) {
if(num == arr[j]) {
flag = false;
}
}
if(flag) {
break;
}
}
arr[i] = num;
}
System.out.println(Arrays.toString(arr));
}
}3.4 数组中涉及到的常见算法
- 数组元素的赋值（杨辉三角、回形数等）
- 求数值型数组中元素的最大值、最小值、平均数、总和等
- 数组的赋值、反转、查找（线性查找、二分查找）
- 数组元素的排序算法
- 练习1
定义一个int型的一维数组，包含10个元素，分别赋予一些随机整数，然后求出所有元素的最大值、最小值、和值、平均值，并输出出来。
要求：所有随机数都是两位数。
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = new int[10];
int num;
for(int i = 0; i < arr.length; i++) {
num = (int)(Math.random()*90+10);
arr[i] = num;
}
int max = arr[0];
int min = arr[0];
int sum = 0;
int avg;
for(int i = 0; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
if(arr[i] < min) {
min = arr[i];
}
sum += arr[i];
}
avg = sum/arr.length;
System.out.println("数组：" + Arrays.toString(arr));
System.out.println("最大值：" + max);
System.out.println("最小值：" + min);
System.out.println("和值：" + sum);
System.out.println("平均值：" + avg);
}
}- 练习2
使用简单数组
- 创建两个int型一维数组：arr1、arr2
- 使用大括号{}，把arr1初始化为8个素数：2，3，5，7，11，13，17，19
- 显示arr1的内容
- 赋值arr2变量等于arr1，修改arr2中的偶索引元素，使其等于索引值（如arr[0],arr[2]=2），打印出arr1
思考：arr1和arr2是什么关系？——arr1和arr2指向同一个数组地址。
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr1, arr2;
arr1 = new int[]{2,3,5,7,11,13,17,19};
for(int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + "\t");
}
System.out.println();
arr2 = arr1;
for(int i = 0; i < arr2.length; i++) {
if(i %2 == 0) {
arr2[i] = i;
}
}
for(int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + "\t");
}
System.out.println();
}
}- 练习2
实现arr2对arr1数组的复制。
public class Test {
public static void main(String[] args) {
int[] arr1, arr2;
arr1 = new int[]{2,3,5,7,11,13,17,19};
for(int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + "\t");
}
System.out.println();
arr2 = new int[arr1.length];
for (int i = 0; i < arr2.length; i++) {
arr2[i] = arr1[i];
}
for(int i = 0; i < arr2.length; i++) {
if(i %2 == 0) {
arr2[i] = i;
}
}
for(int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + "\t");
}
System.out.println();
}
}- 练习3
数组的复制、反转、查找（线性查找、二分查找）。
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
String[] arr = new String[]{"AA","BB","CC","DD","EE"};
// 数组的复制
String[] arr1 = new String[arr.length];
for(int i = 0; i < arr1.length; i++) {
arr1[i] = arr[i];
}
System.out.println(Arrays.toString(arr1));
// 数组的反转
String[] arr2 = new String[arr.length];
for(int i = 0; i < arr2.length; i++) {
arr2[i] = arr[arr.length-1-i];
}
System.out.println(Arrays.toString(arr2));
String temp;
for(int i = 0; i < arr.length/2; i++) {
temp = arr[i];
arr[i] = arr[arr.length-1-i];
arr[arr.length-1-i] = temp;
}
System.out.println(Arrays.toString(arr));
// 线性查找
String target = "BB";
boolean isFlag = true;
for(int i = 0; i < arr.length; i++) {
if(target.equals(arr[i])) {
System.out.println("找到了指定的元素，位置为：" + i);
isFlag = false;
break;
}
}
if(isFlag) {
System.out.println("很遗憾，没有找到！");
}
// 二分查找
int[] nums = new int[]{1,2,3,4,5,6,7,8,9};
int target2 = 3;
isFlag = true;
int left = 0;
int right = arr.length - 1;
int mid = (left+right)/2;
while(left <= right) {
if(target2 == nums[mid]) {
System.out.println("找到了指定的元素，位置为：" + mid);
isFlag = false;
break;
} else if(target2 < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
if(isFlag) {
System.out.println("很遗憾，没有找到！");
}
}
}3.4.1 排序算法
1、排序
假设含有n个记录的序列为{R1, R2, ……, Rn}，其相应的关键字序列为{K1, K2, ……, Kn}。将这些记录重新排列为{Ri1, Ri2, ……, Rin}，使得相应的关键字值满足条件：Ki1 ≤ Ki2 ≤ …… ≤ Kin，这样的操作称为排序。
- 通常来说，排序的目的是快速查找。
2、衡量排序算法的优劣
- 时间复杂度：分析关键字的比较次数和记录的移动次数。
- 空间复杂度：分析排序算法中需要多少辅助内存。
- 稳定性：若两个记录A和B的关键值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。
3、排序算法分类
- 内部排序：整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。
- 外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。
4、十大内部排序算法
- 选择排序
- 直接选择排序
- 堆排序
- 交换排序
- 冒泡排序
- 快速排序
- 插入排序
- 直接插入排序、折半插入排序、Shell排序
- 归并排序
- 桶排序
- 基数排序
5、算法的5大特征
- 输入：有0个或多个输入数据，这些输入必须有清楚的描述和定义。
- 输出：至少有1个或多个输出结果，不可以没有输出结果。
- 有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成。
- 确定性：算法中的每一步都是有确定的含义，不会出现二义性。
- 可行性：算法的每一步都是清楚且可行的，能让用户用纸笔计算而求出答案。
说明：满足确定性的算法也称为“确定性算法”。现在人们也关注更加广泛的概念。例如：考虑各种非确定性的算法，如并行算法、概率算法等。另外，人们也关注并不要求终止的计算描述，这种描述有时被称为过程（Procedure）。
3.4.2 冒泡排序
import java.util.Arrays;
public class Test {
public static void bubbleSort(int[] arr) {
int length = arr.length;
int temp;
for(int i = 1; i < length; i++) {
for(int j = 0; j < length - i; j++) {
if(arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{49,38,65,97,76,13,27,49};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
}3.4.3 快速排序
import java.util.Arrays;
public class Test {
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length-1);
}
public static void quickSort(int[] arr, int left, int right) {
int l = left;
int r = right;
int pivot = arr[(l+r)/2];
int temp;
while(l < r) {
while(l < r && arr[l] <= pivot) {
l++;
}
while(l < r && arr[r] >= pivot) {
r--;
}
if(l < r) {
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
}
if(l > left) {
quickSort(arr, left, r-1);
}
if(l < right) {
quickSort(arr, l, right);
}
}
public static void main(String[] args) {
int[] arr = new int[]{49,38,65,97,76,13,27,49};
quickSort(arr);
System.out.println(Arrays.toString(arr));
}
}3.4.4 排序算法性能比较
3.5 Arrays工具类
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
// 1、Arrays.equals(int[] a, int[] b)：判断两个数组是否相等
int[] arr1 = new int[]{1,3,2,4};
int[] arr2 = new int[]{1,3,2,4};
boolean isEqual = Arrays.equals(arr1, arr2);
System.out.println(isEqual);
// 2、Arrays.toString(int[] a)：输出数组信息
System.out.println(Arrays.toString(arr1));
// 3、Arrays.fill(int[] a, int val)：将指定值填充到数组之中
Arrays.fill(arr1, 10);
System.out.println(Arrays.toString(arr1));
// 4、Arrays.sort(int[] a)：对数组进行排序
Arrays.sort(arr2);
System.out.println(Arrays.toString(arr2));
// 5、Arrays.binarySearch(int[] a, int key)：二分查找
int[] arr3 = new int[]{-78,46,7,9,2,95,79};
int index = Arrays.binarySearch(arr3, 9);
System.out.println(index);
}
}
京公网安备 11010502036488号