Arrays类
- 数组的工具类java.util.Arrays
- 由于数组对象本身并没有什么方法可以供我们调用，但API中提供了一个工具类Arrays供我们使用，从而可以对数据对象进行一些基本操作、
- 具体可查看JDK帮助文档
- Arrays类中的方法都是static修饰的静态方法，在使用的时候可以直接使用类名进行调用，而"不用"使用对象来调用(注意：是"不用"，而不是"不能")
- 具有以下常用功能：
- 给数组赋值：通过fill方法；
- 对数组进行排序：通过sort方法，按升序
- 比较数组：通过equals方法比较数组中元素值是否相等
- 查找数组元素：通过binarySearch方法能对排序好的数组进行二分查找法操作
冒泡排序
- 冒泡排序是最为出名的排序算法之一，总共有八大排序！
- 这个算法的时间复杂度为O(n2)
package array;
import java.util.Arrays;
/*
冒泡排序
1.比较数组中，两个相邻的元素，如果第一个数比第二个数大，我们就交换他们的位置
2.每一次比较，都会产生出一个最大，或者最小的数字
3.下一轮则可以少一次排序！
4.依次循环，直到结束！
*/
public class Demo07 {
public static void main(String[] args) {
int[] a = {5,34,53,22,76,345,32,45,87};
int[] sort = sort(a); // 调用完我们自己写的排序方法以后，返回一个排序后的数组
System.out.println(Arrays.toString(sort));
}
public static int[] sort(int[] array){
int temp = 0; //临时变量，用于交换两个值
// 外层循环 判断我们这个要走多少次
for (int i = 0; i < array.length-1; i++) {
// 内层循环，比较判断两个数，如果第一个数比第二个数大，则交换位置
for (int j = 0; j < array.length-1-i; j++) {
if (array[j+1]>array[j]){
// temp = array[j];
// array[j] = array[j+1];
// array[j+1] = temp;
temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
}
return array;
}
}
-
思考：如何优化？
public class Demo07 { public static void main(String[] args) { int[] a = {5,34,53,22,76,345,32,45,87}; int[] sort = sort(a); // 调用完我们自己写的排序方法以后，返回一个排序后的数组 System.out.println(Arrays.toString(sort)); } public static int[] sort(int[] array){ int temp = 0; //临时变量，用于交换两个值 // 外层循环 判断我们这个要走多少次 for (int i = 0; i < array.length-1; i++) { boolean flag = false; //通过flag标志位，减少没有意义的比较 // 内层循环，比较判断两个数，如果第一个数比第二个数大，则交换位置 for (int j = 0; j < array.length-1-i; j++) { if (array[j+1]>array[j]){ // temp = array[j]; // array[j] = array[j+1]; // array[j+1] = temp; temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; flag = true; } } if (flag==false){ break; } } return array; } }
稀疏数组
-
当一个数组中大部分元素为0，或者为同一值的数组时，可以使用稀疏数组来保存该数组。
-
稀疏数组的处理方式是：
- 记录数组一共有几行几列，有多少不同值
- 把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模
-
如下图：左边是原始数组，右边是稀疏数组
-
第一行6、7、8分别代表原始数组中有6行 7咧 8个数字(除0以外有8个数字)
-
第二行0、3、22代表第一个数字22 在0行3列
-
以下以此类推
-
创建一个二维原始数组
public class Demo08 {
public static void main(String[] args) {
// 创建一个二维数组 11*11 0：没有棋子 1：黑棋 2：白棋
int[][] array1 = new int[11][11]; //创建出了一个11*11的格子
array1[1][2] = 1;
array1[2][3] = 2;
// 输出原始数组
System.out.println("输出原始数组");
// 打印 使用for each循环
for (int[] ints : array1) { // 快速输出方式：array1.for+tab键
for (int anInt : ints) { // 快速输出方式：ints.for+tab键
System.out.print(anInt+"\t");
}
System.out.println(); // 换行操作
}
}
}
// 输出结果
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
- 将二维原始数组转换为稀疏数组
// 转换为稀疏数组进行保存
// 1.获取有效值的个数 遍历数组
int sum = 0;
for (int i = 0; i < array1.length; i++) {
for (int j = 0; j < array1[i].length; j++) {
if (array1[i][j] != 0) {
sum++;
}
}
}
System.out.println("有效值的个数为" + sum);
// 2.创建一个稀疏数组的数组
int[][] array2 = new int[sum + 1][3];
// 给稀疏数组赋值
array2[0][0] = 11;
array2[0][1] = 11;
array2[0][2] = sum;
// 3.遍历二维数组，将非零的值，存放稀疏数组中
int count = 0; //设定一个非零值的数量为count 初始值为0
for (int i = 0; i < array1.length; i++) {
for (int j = 0; j < array1[i].length; j++) {
if (array1[i][j] != 0) {
count++;
array2[count][0] = i;
array2[count][1] = j;
array2[count][2] = array1[i][j];
}
}
}
// 输出稀疏数组
System.out.println("稀疏数组");
for (int i = 0; i < array2.length; i++) {
System.out.println(array2[i][0]+"\t"
+array2[i][1]+"\t"
+array2[i][2]+"\t");
}
- 将稀疏数组还原为原始二维数组
//1.读取稀疏数组的值
int[][] array3 = new int[array2[0][0]][array2[0][1]]; // 原始数组共有11行11列
//2.给元素还原值
for (int i = 1; i < array2.length; i++) {
array3[array2[i][0]][array2[i][1]] = array2[i][2];
}
//3.打印还原数组
for (int[] ints : array3) { // 快速输出方式：array3.for+tab键
for (int anInt : ints) { // 快速输出方式：ints.for+tab键
System.out.print(anInt + "\t");
}
System.out.println(); // 换行操作
}