数组的概念
概述
数组（Array）是多个相同类型的数据按照一定的顺序排列的集合，并使用一个名字命名，并通过编号的方式对这些数据进行统一管理。
概念
- 数组名
- 元素
- 下标、角标、索引
- 数组的长度，数组元素的个数
特点
- 数组是有序排列的
- 数组属于引用数据类型，而数组的元素既可以是引用数据类型，也可以是基本数据类型
- 创建数组对象会在内存中开辟出一块连续的空间
- 数组的长度一旦确定不能再修改
- 数组有一维数组、二维数组、三维数组、………
一维数组的声明和初始化
静态声明
1
2
3
| int[] ids;
ids = new int[]{1001,1002,1003};
System.out.println(ids.length);
|
动态声明
1
2
3
4
5
6
7
8
9
10
11
12
| String[] names = new String[5];
names[0] = "张三";
names[1] = "李四";
names[2] = "王五";
names[3] = "赵柳";
names[4] = "王琦";
System.out.println(names.length);
System.out.println(names[2]);
for(int i=0; i<names.length; i++){
System.out.println(names[i]);
}
|
遍历数组结构
1
2
3
4
5
6
7
8
9
10
11
12
13
|
String[] names = new String[5];
names[0] = "张三";
names[1] = "李四";
names[2] = "王五";
names[3] = "赵柳";
names[4] = "王琦";
System.out.println(names.length);
System.out.println(names[2]);
for(int i=0; i<names.length; i++){
System.out.println(names[i]);
}
|
不同类型数组的默认值
| 数组类型 |
默认值 |
| int |
0 |
| double |
0.0 |
| boolean |
false |
| String |
null |
| char |
(char类型是一个空值) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int[] intarr = new int[2];
System.out.println(intarr[0]);
double[] douarr = new double[2];
System.out.println(douarr[0]);
boolean[] boolarr = new boolean[2];
System.out.println(boolarr[0]);
String[] strarr = new String[2];
System.out.println(strarr[0]);
|
二维数组的声明方式
二维数组表示数组的元素也是一个一维数组
静态声明
1
2
|
int[][] ids = new int[][] { { 1, 2, 3 }, { 4, 5 }, { 6, 7, 8 } };
|
动态声明
1
2
|
String[][] names = new String[3][2];
|
类型推断
1
2
|
int[][] arr = { { 1, 2, 3 }, { 4, 5 } };
|
二维数组的遍历
1
2
3
4
5
6
|
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
System.out.println(arr[i][j]);
}
}
|
二维数组的默认值
规定：二维数组分为外层数组元素和内层数组元素
外层元素表示为：arr[0]，arr[1]
内层元素表示为：arr[0][1]，arr[0][2]
当内层元素有长度时，则外层元素的默认值都是一个应用地址，否则是一个 null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static void main(String[] args) {
int[][] arr = new int[2][4];
System.out.println(arr[0]);
System.out.println(arr[0][0]);
String[][] arr1 = new String[3][2];
System.out.println(arr1[0]);
System.out.println(arr1[0][0]);
int[][] arr2 = new int[3][];
System.out.println(arr2[0]);
}
|
二维数组练习
计算二维数组元素和
1
2
3
4
5
6
7
8
9
10
11
|
int[][] arr = new int[][] {{3,5,8},{12,9},{7,0,6,4}};
int count = 0;
for(int i = 0; i < arr.length; i++) {
for(int j = 0; j < arr[i].length; j++) {
count += arr[i][j];
}
}
System.out.println(count);
|
打印出一个杨辉三角
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
| public static void main(String[] args) {
int[][] YangHui = new int[10][];
for(int i = 0; i<YangHui.length; i++) {
YangHui[i] = new int[i+1];
YangHui[i][0] = YangHui[i][YangHui[i].length - 1] = 1;
for(int j = 1; j < YangHui[i].length - 1; j++) {
YangHui[i][j] = YangHui[i-1][j-1] + YangHui[i-1][j];
}
}
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
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
public class ArrayDemo04 {
public static void main(String[] args) {
int[] nums = new int[6];
for(int i = 0; i < nums.length; i++) {
nums[i] = (int)(Math.random() * 30) + 1;
for(int j = 0; j < i; j++) {
if(nums[i] == nums[j]) {
i--;
break;
}
}
}
for(int i = 0; i < nums.length; i++) {
System.out.println(nums[i]);
}
}
}
|
数组拓展练习题
数组复制
1
2
3
4
5
6
7
8
9
10
11
12
|
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];
if(arr1[i] == "aa") {
arr1[i] = "AA";
}
System.out.println(arr1[i]);
}
|
数组反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
String[] arr = new String[] {"aa","bb","cc","dd","ee"};
for(int i = 0,j = arr.length - 1; i < j; i++,j--) {
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
|
数组查找之 - 线性查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
String[] names = new String[] { "aa", "bb", "cc", "dd" };
String tmp = "cc";
boolean isFlag = false;
for (int i = 0; i < names.length; i++) {
if (names[i].equals(tmp)) {
isFlag = true;
System.out.println("要查找的元素下标是：" + i);
}
}
if (!isFlag) {
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
| int[] nums = new int[] { -32, -21, -10, -1, 12, 32, 45, 56, 67, 71, 82 };
int num = 67;
int head = 0;
int end = nums.length - 1;
boolean isflag = false;
while(true) {
if((end - head) + 1 <= 3) {
for(int i = head; i <= end; i++) {
if(nums[i] == num) {
isflag = true;
System.out.println("元素下标是ss：" + i);
}
}
break;
}
int middle = (head + end) / 2;
if(nums[middle] == num) {
isflag = true;
System.out.println("元素下标是：" + middle);
break;
}else if(nums[middle] > num) {
end = middle - 1;
}else {
head = middle + 1;
}
}
if(!isflag) {
System.out.println("没有找到");
}
|
排序算法
通常来说：排序的目的是为了快速查找
衡量排序算法的优劣
- 时间复杂度。分析关键字的比较次数和记录的移动次数
- 空间复杂度。分析排序算法中需要多少辅助内存
- 稳定性。若两个记录A和B的关键字相等，单排序后A、B的先后次序保持不变，则称这种排序算法是稳定的
十大内部排序算法
选择排序
堆排序
交换排序
冒泡排序
快速排序
插入排序
直接插入排序
折半插入排序
Shell排序，也叫希尔排序
归并排序
桶式排序
基数排序
算法的5大特征
| 特征 |
描述 |
| 输入（input） |
有0个获取多个输入数据，这些输入必须有清楚的描述和定义 |
| 输出（Output） |
至少有1个或者多个输出结果，不能没有输出结果 |
| 有穷性（有限性，Finiteness） |
算法在有限的步骤之后会自动结束而不会无限循环，并且每一步骤可以在可接受的时间内完成 |
| 确定性（明确性，Definiteness） |
算法中的每一步都有明确的含义，不会出现二义性 |
| 可行性（有效性，Effectiveness） |
算法的每一步都是清楚且可行的，能让用户用纸笔计算而求出答案 |
说明：满足确定性的算法也称为：确定性算法。
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public static void main(String[] args) {
int[] nums = new int[] {45,68,5,98,10,-42,35,-55,-65,3};
for(int i = 0; i < nums.length -1; i++) {
for(int j = 0; j <nums.length - 1 - i ; j++) {
if(nums[j] > nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
for(int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+ " ");
}
}
|
数组工具类 Arrays 的使用
使用前要先导入数组工具类
1
2
3
4
5
6
7
8
9
| import java.util.Arrays;
public class Arrays05 {
public static void main(String[] args) {
int[] arr = new int[] {12,65,45,8,35};
int[] arr1 = new int[] {8,12,23,36,45,56};
}
}
|
判断两个数组是否相等Arrays.equals(arr,arr1)
1
2
3
4
|
boolean isEquals = Arrays.equals(arr,arr1);
System.out.println(isEquals);
|
打印数组信息Arrays.toString(arr)
1
2
|
System.out.println(Arrays.toString(arr));
|
1
2
3
4
5
6
7
|
Arrays.fill(arr, 2,3,20);
System.out.println(Arrays.toString(arr));
|
对数组进行排序Arrays.sort(arr)
1
2
3
|
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
|
使用二分查找获取指定元素下标 Arrays.binarySearch(arr,key)
1
2
3
4
5
6
7
8
9
10
|
int index = Arrays.binarySearch(arr, 12);
if(index >= 0) {
System.out.println(index);
}else {
System.out.println("未找到");
}
|
数组中常见的异常
下标越界异常
指获取数组不存在的下标值而出现的异常
1
2
3
4
5
6
7
| int[] nums = new int[] { 1, 2, 3, 4, 5, 6 };
for (int i = 0; i <= nums.length; i++) {
System.out.println(nums[i]);
}
|
空指针异常
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
String[] arr = new String[] { "aa", "bb" };
arr[0] = null;
system.out.println(arr[0].toString());
int[] arr1 = new int[] {1,2,3};
arr1 = null;
System.out.println(arr1[0]);
int[][] arr2 = new int[2][];
System.out.println(arr2[0][0]);
|
