Java | Java 数组（下）
- 五、数组中涉及的常见算法
- 5.1 数组元素的赋值
- 5.2 数值型数组元素的操作
- 5.3 数组的复制、反转和查找
- 5.3.1 复制
-
- 5.3.2 反转
- 5.3.3 排序
-
- 5.3.4 查找
-
- 六、Arrays 类
- 七、稀疏数组
-
五、数组中涉及的常见算法
5.1 数组元素的赋值
- 杨辉三角
- 回形数
-
⋯
⋯
cdotscdots
⋯⋯
5.2 数值型数组元素的操作
- 最大值
- 最小值
- 平均数
- 总和
-
⋯
⋯
cdotscdots
⋯⋯
5.3 数组的复制、反转和查找
5.3.1 复制
（1）引用拷贝
- 引用拷贝不会生成新的对象，只会在原对象上增加了一个新的对象引用，两个不同的引用指向同一个对象。如果对一个对象进行改变，其他对象也会跟着改变。
- 数组引用拷贝：
public static void main(String[] args) {
int[] arr1 = new int[] {1,2,3,4,5,6,7,8,9};
int[] arr2 = arr1;// 引用拷贝，arr1和arr2指向同一对象
arr2[0] = 10;// 修改arr2元素，arr1同样被改变
for (int i = 0; i < arr1.length; i++) {
System.out.println("arr1[" + i +"]:" + arr1[i] + ", arr2[" + i +"]:" + arr2[i]);
}
}
输出：arr1[0]:10, arr2[0]:10
arr1[1]:2, arr2[1]:2
arr1[2]:3, arr2[2]:3
arr1[3]:4, arr2[3]:4
arr1[4]:5, arr2[4]:5
arr1[5]:6, arr2[5]:6
arr1[6]:7, arr2[6]:7
arr1[7]:8, arr2[7]:8
arr1[8]:9, arr2[8]:9
（2）对象拷贝（浅拷贝与深拷贝）
- 浅拷贝：
- 对基本数据类型，进行值传递；
- 对引用数据类型，进行引用拷贝。因此，如果其中一个对象改变了这个地址，就会影响到另一个对象。
- 数组引用拷贝也是一种浅拷贝。
- 深拷贝：
- 对基本数据类型，进行值传递；
- 对引用数据类型，创建一个新的对象，并复制其内容。
- 数组深拷贝：
public static void main(String[] args) {
int[] arr1 = new int[] {1,2,3,4,5,6,7,8,9};
int[] arr2 = new int[arr1.length];// 创建一个与arr1数组长度相同的新对象arr2
for (int i = 0; i < arr2.length; i++) {
arr2[i] = arr1[i];// 将arr1数组元素的内容复制给arr2数组元素
}
arr2[0] = 10;// 修改arr2元素，arr1不受影响
for (int i = 0; i < arr1.length; i++) {
System.out.println("arr1[" + i +"]:" + arr1[i] + ", arr2[" + i +"]:" + arr2[i]);
}
}
输出：arr1[0]:1, arr2[0]:10
arr1[1]:2, arr2[1]:2
arr1[2]:3, arr2[2]:3
arr1[3]:4, arr2[3]:4
arr1[4]:5, arr2[4]:5
arr1[5]:6, arr2[5]:6
arr1[6]:7, arr2[6]:7
arr1[7]:8, arr2[7]:8
arr1[8]:9, arr2[8]:9
5.3.2 反转
- 数组反转方式1：
public static void main(String[] args) {
int[] arr = new int[] {1,2,3,4,5,6,7,8,9};
int temp = arr[0];
for (int i = 0; i < arr.length; i++) {
if ((arr.length - 1 - i) > i) {
temp = arr[i];
arr[i] = arr[arr.length - 1 - i];
arr[arr.length - 1 - i] = temp;
} else {
break;
}
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");// 9,8,7,6,5,4,3,2,1,
}
}
- 数组反转方式2：
public static void main(String[] args) {
int[] arr = new int[] {1,2,3,4,5,6,7,8,9};
int temp;
for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");// 9,8,7,6,5,4,3,2,1,
}
}
5.3.3 排序
- 排序是计算机内经常进行的一种操作，其目的是将一组 “无序” 的序列按照某一种属性调整为 “有序” 的序列。通常来说，排序的目的是快速查找。
- 排序算法可分为内部排序和外部排序，若整个排序过程不需要借助外部存储器（例：磁盘）便能完成，则称此类排序问题为内部排序。反之，若参加排序的数据量很大，整个序列的排序过程无法在内存中完成，则称此类排序问题为外部排序，最常见的外部排序是多路归并排序。可以认为外部排序是由多次内部排序组成。
- 衡量排序算法的优劣：
- 时间复杂度：分析关键字的比较次数和记录的移动次数。
- 空间复杂度：分析排序算法中需要多少辅助内存。
- 稳定性：若序列中存在两条记录“A”和“B”，这两条记录的比较关键字相等，在排序后“A”和“B”的先后次序保持不变，则称这种排序算法是稳定的。
- 十大经典排序算法：1、冒泡排序；2、选择排序；3、插入排序；4、希尔排序；5、归并排序；6、快速排序；7、堆排序；8、计数排序；9、桶排序；10、基数排序
举例：冒泡排序
5.3.4 查找
（1）线性查找
- 线性查找又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。
public static void main(String[] args) {
String[] arr = new String[] {"a","b","c","d","e","f","g"};
String searchA = "a";
boolean flagA = true;
String searchZ = "z";
boolean flagZ = true;
for (int i = 0; i < arr.length; i++) {
if (searchA.equals(arr[i])) {// 字符串查找需要使用equals方法
flagA = false;
System.out.println(searchA + "查找到了，索引为：" + i);
}
if (searchZ.equals(arr[i])) {
flagZ = false;
System.out.println(searchZ + "查找到了，索引为：" + i);
}
}
if (flagA) {
System.out.println(searchA + "没有查找到");
}
if (flagZ) {
System.out.println(searchZ + "没有查找到");
}
}
（2）二分查找
- 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
public static void main(String[] args) {
Random rand = new Random();
int[] arr = new int[20];
int temp;// 临时变量
for (int i = 0; i < arr.length; i++) {
arr[i] = rand.nextInt(-100, 100);
}
System.out.print("数组排序前：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
System.out.println();
// 冒泡排序
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.print("数组排序后：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
System.out.println();
Scanner scan = new Scanner(System.in);
System.out.print("请输入要查找的整数值：");
int num = scan.nextInt();
int start = 0;
int end = arr.length - 1;
int middle;
boolean isFlag = true;
while (start <= end) {
middle = (end + start) / 2;
if (num == arr[middle]) {
isFlag = false;
System.out.println("整数" + num + "在数组中找到了！");
break;
} else if (num < arr[middle]) {
end = middle - 1;
} else if (num > arr[middle]) {
start = middle + 1;
}
}
if (isFlag) {
System.out.println("整数" + num + "在数组中没有找到！");
}
}
六、Arrays 类
- 数组对象本身并没有什么方法可以供我们调用，但API中提供了一个工具类Arrays供我们使用（java.util.Arrays），从而可以对数组对象进行一些基本的操作。
- Arrays 类中的方法都是 static 修饰的静态方法，在使用的时候可以直接使用类名进行调用，而 “不用” 使用对象来调用（注意：是 “不用” 而不是 “不能”）
- Arrays 类常用方法：（array 表示数组变量）
// 返回数组 array 的字符串表示形式
Arrays.toString(array)
// 将 dataType 类型的 val 值分配给数组 array 在指定范围内的每个元素，dataType 要与数组 array 的类型相同
Arrays.fill(array, [int fromIndex, int toIndex,] dataType val)
// 比较两个数组 array1、array2 在指定范围内是否相等
Arrays.equals(dataType[] array1,[int aFromIndex, int aToIndex,] dataType[] array2[, int bFromIndex, int bToIndex])
// 从原数组 original 复制指定长度 newLength 的数组到新的数组对象
// Arrays.copyOf 是浅拷贝，即如果数组元素是引用类型，则指向同一个地址
// 如果新数组的长度超过原数组的长度，则超过长度的数组元素赋默认值
Arrays.copyOf(dataType[] original, int newLength)
// 按升序排列数组的指定范围
Arrays.sort(dataType[] array[, int fromIndex, int toIndex])
// 使用二分查找算法在数组 array 中搜索 key
// 数组在调用前必须排序好
// 如果查找值 key 包含在数组 array 中，则返回搜索键的索引；否则返回 (-(插入点)-1)，插入点是索引键 key 将要插入数组的那一点，即第一个大于该键的元素索引
Arrays.binarySearch(dataType[] array, int fromIndex, int toIndex, dataType key)
七、稀疏数组
7.1 稀疏数组引入
- 需求：编写五子棋游戏中，有存储棋局退出和继续上一棋局的功能。
- 分析问题：因为该二维数组的很多值是默认值 0，因此记录了很多没有意义的数据。
- 解决：稀疏数组。
7.2 稀疏数组介绍
- 当一个数组中大部分元素为 0，或者为同一值的数组时，可以使用稀疏数组来保存该数组。
- 稀疏数组的处理方式是：
- 记录数组一共有几行几列，有多少个不同值。
- 把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模。
- 如下图：左边是原始数组，右边是稀疏数组。
- 五子棋游戏的棋盘数组转为稀疏数组：
- 示例：将五子棋棋盘使用稀疏数组保存。
public class Demo06 {
public static void main(String[] args) {
// 创建一个二维数组 11 * 11。其中，0：没有棋子，1：白棋，2：黑棋
int[][] array = new int[11][11];
array[1][2] = 1;
array[2][3] = 2;
// 打印原始数组
printArray(array,"原始数组：");
// 获取非零元素个数
int num = nonZero(array);
// 原始数组转为稀疏数组
int[][] sparseArray = originalToSparse(array, num);
printArray(sparseArray,"稀疏数组：");
// 稀疏数组转为原始数组
int[][] originalArray = sparseToOriginal(sparseArray);
printArray(originalArray,"原始数组：");
}
// 获取原始数组非零元素个数
public static int nonZero(int[][] originalArray) {
int num = 0;
for (int[] numArray : originalArray) {
for (int i : numArray) {
if (i != 0) {
num++;
}
}
}
System.out.println("一共有 "+num+" 个有效数字");
return num;
}
// 稀疏数组转换为原始数组
public static int[][] sparseToOriginal(int[][] sparseArray) {
int[][] originalArray = new int[sparseArray[0][0]][sparseArray[0][1]];
for (int i = 1; i < sparseArray.length; i++) {
originalArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
return originalArray;
}
// 原始数组转换为稀疏数组
public static int[][] originalToSparse(int[][] array, int num) {
int[][] sparseArray = new int[num+1][3];
int line = 0;
sparseArray[line] = new int[]{array.length, array.length, num};
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
if (array[i][j] != 0 && line < num) {
sparseArray[++line] = new int[]{i,j,array[i][j]};
}
}
}
return sparseArray;
}
// 打印数组
public static void printArray(int[][] array, String str) {
System.out.println(str);
for (int[] numArray : array) {
for (int i : numArray) {
System.out.print(i+"t");
}
System.out.println();
}
}
}
