数组的定义

  • 数组是相同类型数据的有序集合。

数组的声明创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//声明一个数组
int[] nums;//1.声明一个数组
int nums2[];
//两种方法都可以声明一个整型数组,但建议使用第一个
nums = new int[10];//2.创建一个数组

//也可以这样写
int[] nums = new int[10];//声明并创建一个数组

//3.给数组元素赋值
nums[0] = 1;
nums[1] = 2;
nums[2] = 3;
nums[3] = 4;
nums[4] = 5;
nums[5] = 6;
nums[6] = 7;
nums[7] = 8;
nums[8] = 9;
nums[9] = 10;
//int类型数组未赋值的元素默认值是0
  • 获取数组长度:arrays.length。
1
2
3
4
5
6
//计算所有元素的和
int sum = 0;

for (int i = 0;i<nums.length;i++){
sum = sum + nums[i];
}

内存分析

三种初始化

  1. 静态初始化

    1
    int[] a = {1,2,3,4,5,6,7,8,};//一旦定义不可改变
  1. 动态初始化(包含默认初始化)

    1
    2
    3
    4
    int[] nums = new int[10];
    nums[0] = 1;
    nums[1] = 2;
    nums[2] = 3;
  1. 数组的默认初始化

数组的四个基本特点

  1. 长度确定。数组一旦被创建,它的大小就不可以改变。

  2. 元素必须是相同类型,不允许出现混合类型。

  3. 数组中的元素可以是任意数据类型,包括基本类型和引用类型。

  4. 数组本身就是对象,可以无限套娃。数组对象本身是在堆中

数组边界

  • 下标的合法区间:[0,length-1],如果越界就会报错。

数组的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
int[] arrays = {1,2,3,4,5};
//计算所有元素的和
int sum = 0;
for (int i = 0; i < arrays.length; i++) {
sum += arrays[i];
}
System.out.println("sum="+sum);//sum=15
//查找最大元素
int max =arrays[0];
for (int i = 0; i < arrays.length; i++) {
if (arrays[i]>max){
max = arrays[i];
}
}
System.out.println("max="+max);
}

For-Each循环

1
2
3
4
for (int array: arrays) {
System.out.println(array);
}//遍历每一个元素
//缺点:没有下标,不方便对某个元素操作

数组作为方法入参

1
2
3
4
5
6
//定义一个方法,打印数组元素
public static void printArray(int[] arrays){
for (int i = 0; i < arrays.length; i++) {
System.out.print(arrays[i]+" ");
}
}

数组作返回值

1
2
3
4
5
6
7
8
9
//定义一个方法,反转数组
public static int[] reverse(int[] arrays){
int[] result = new int[arrays.length];
//反转的操作
for (int i = 0,j = result.length-1; i < arrays.length; i++,j--) {
result[j] = arrays[i];
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Demo03 {
public static void main(String[] args) {
int[] arrays = {1,2,3,4,5};
printArray(arrays);
System.out.println();
int[] reverse = reverse(arrays);
printArray(reverse);
}
//定义一个方法,打印数组元素
public static void printArray(int[] arrays){
for (int i = 0; i < arrays.length; i++) {
System.out.print(arrays[i]+" ");
}
}
//定义一个方法,反转数组
public static int[] reverse(int[] arrays){
int[] result = new int[arrays.length];
//反转的操作
for (int i = 0,j = result.length-1; i < arrays.length; i++,j--) {
result[j] = arrays[i];
}
return result;
}
}

多维数组

  • 一般我们这样定义一个数组:

    1
    int[][] array = {{1,2},{2,4},{3,4},{4,5}}; 
  • int a[][] = new int[2][5];

    以上二维数组a可以看成一个两行五列数组。

使用

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
int[][] array = {{1,2},{2,4},{3,4},{4,5}};
//打印二维数组的每一个元素
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
System.out.println(array[i][j]);
}
}
}

Arrays类

  • import java.util.Arrays;
1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.Arrays;

public class Demo05 {
public static void main(String[] args) {
int[] a = {1,5,7,6485,4564,789,26};
//打印数组元素Array.toString
System.out.println(Arrays.toString(a));
Arrays.sort(a);//数组进行排序
System.out.println(Arrays.toString(a));
}
}
//[1, 5, 7, 6485, 4564, 789, 26]
//[1, 5, 7, 26, 789, 4564, 6485]
  • 具有以下常用功能:

    • 给数组赋值:通过fill方法。

    • 对数组排序:通过sort方法,按升序。

    • 比较数组:通过equals方法比较数组中元素值是否相等。

    • 查找数组元素:通过binarySearch方法能对排序好的数组进行二分查找法操作。

冒泡排序

  1. 比较数组中,两个相邻的元素,如果第一个数比第二个数大,我们就交换他们的位置。

  2. 每一次比较,都会产出一个最大,或者最小的数字。

  3. 下一轮则可以少一次排序。

  4. 依次循环,直到结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Arrays;

public class Demo06 {
public static void main(String[] args) {
int[] a = {1,45,1574,18574,45,2,2,78,2};
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;
}
}
}
return array;
}
}

时间复杂度优化

  • 通过定义一个布尔值,在外层循环下,默认为false,在内层循环内,将布尔值重改为true,然后每当内层循环结束后判断布尔值是否为false,如果为false,表明排序已完成,直接跳出外层循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Arrays;

public class Demo06 {
public static void main(String[] args) {
int[] a = {1,45,1574,18574,45,2,2,78,2};
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;
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;
flag = true;
}
}
if (flag==false){
break;
}
}
return array;
}
}

稀疏数组

  • 二维数组中如果很多值都是0或者同一数值时,意味着记录了很多没有意义的数据。采用稀疏数组是不错的选择。

  • 稀疏数组的处理方式是:

    • 记录数组一共有几行几列,有多少个不同值。

    • 把具有不同值的元素和行列及值记录在一个小规模的数组中,从而缩小程序的规模。

原始数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Demo07 {
public static void main(String[] args) {
//创建一个二维数组 11*11 0:没有棋子 1:黑棋 2:白棋
int [][] array1 = new int[11][11];
array1[1][2] = 1;
array1[2][3] = 2;
System.out.println("输出原始的数组:");

for (int[] ints : array1) {
for (int anInt : ints) {
System.out.print(anInt+"\t");
}
System.out.println();
}
}
}

稀疏数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package cool.ply.array;

public class Demo07 {
public static void main(String[] args) {
//创建一个二维数组 11*11 0:没有棋子 1:黑棋 2:白棋
int [][] array1 = new int[11][11];
array1[1][2] = 1;
array1[2][3] = 2;
System.out.println("输出原始的数组:");

for (int[] ints : array1) {
for (int anInt : ints) {
System.out.print(anInt+"\t");
}
System.out.println();
}
//转化为稀疏数组保存
//获取有效值的个数
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (array1[i][j]!=0){
sum++;
}
}
}
System.out.println("有效值个数为:"+sum);

//创建一个稀疏数组的数组
int[][] array2 = new int[sum+1][3];
array2[0][0] = 11;
array2[0][1] = 11;
array2[0][2] = sum;

//遍历二维数组,将非零的值存放在稀疏数组中
int 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");
}

System.out.println("======================");
System.out.println("还原");
//读取稀疏数组
int[][] array3 = new int[array2[0][0]][array2[0][1]];
//给其中的元素还原值
for (int i = 1; i < array2.length; i++) {
array3[array2[i][0]][array2[i][1]] = array2[i][2];
}
//打印
System.out.println("输出还原的数组");
for (int[] ints : array3) {
for (int anInt : ints) {
System.out.print(anInt+"\t");
}
System.out.println();
}
}
}
  • 输出结果为: