第五章 数组和算法
有一个需求，元动力招生了，有一百个学生报名，我想记录一下这一百个学生的年龄和姓名，或者计算一下学生的平均年龄，难道我们要定义一百个变量吗？
From: 元动力1
2
3
| int student1 = 12;
...
算了不写了。
|
合理的做法一定是，在内存里找一个片空间，按顺序存起来。其实这个道理很简单，一拿一个苹果用手拿就行，如果是10个你就要用篮子或袋子拿了，如果是一万个，你就要用卡车拉了。同理在计算机中，我们有这样一种数据结构能帮助我们把想同类型的数据统一聚拢放在一起，他就是【数组】。
一、数组的定义
1、基本概念和内存图
数组可以存放多个同一类型的数据。 数组也是一种数据类型， 是引用类型，他在内存里是这个样子的。
image-20210727190938663他是这样定义的。
From: 元动力1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 定义：
int[] nums;
初始化：
nums = new int[3];
赋值：
nums[0] = 1;
nums[1] = 4;
nums[2] = 3;
int[] nums = {1,2,3};
int nums[] = new int[5];
int nums[] = new int[]{1,2,4,5};
nums.length
类型[] 名字 = new 类型[长度];
|
说说这三个步骤，如图：
image-20210802145617399三个问题：
1、数组不初始化能赋值吗？
2、初始化之后，如果不赋值，会不会有默认值？只要给你开辟了空间就一定会有默认值。
3、数组能不能越界赋值，比如长度为三，非要给第五个赋值。
2、数组的性质
结束了这个谈论，我们简单的概括一个数组的特性
数组一旦建立，长度不能改变。
每个位置只能存一个值，多了会覆盖。
数组创建后会有默认值：int 0， short 0, byte 0, long 0, float 0.0,double 0.0， char \u0000， boolean false， String null
编号从0开始，下标必须在指定范围内使用， 否则报： 下标越界异常。
他有个长度的属性，最后一个位置的编号是 长度-1。 0 - length -1
数组里边可以是基本类型，也可以是引用类型。
3、数据结构
大学里有一门课很重要，叫数据结构与算法。
数组是一种最基本的数据结构，是表的一种，是一种二维的线性表，我们以后还会接触链表，hash表等。
百度百科是这样解释线性表的：
- 线性表是最基本、最简单、也是最常用的一种数据结构。线性表*（linear list）*是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
- 线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的）。
二、玩转数组
1、通循环遍历打印数组的每一个值
我们已经学习过了for循环，for循环正好能从0循环到某一个值，而这刚好可以对应我们数据的下标，写出一个优雅的循环。
我们要明确的是我的的范围是 0 ~ length -1
From: 元动力1
2
3
| for (int i = 0; i < salary.length; i++) {
System.out.print(salary[i] + " ");
}
|
我们不妨思考一下使用while循环可以吗？
From: 元动力1
2
3
4
5
| int i = 0;
while (i < nums.length){
System.out.println(nums[i]);
i++;
}
|
大家慢慢一定要学会举一反三。
2、查找一个数组里存在的值
思路很简单，遍历每一个值，然后比较，知道遇到这个值为止。
From: 元动力1
2
3
4
5
6
7
8
|
int target ;
for (int i = 0; i < salary.length; i++) {
if(salary[i] == 5){
res = salary[i];
}
}
System.out.println(target);
|
你会发现这么写是错的，编译可能出问题：Error:(21, 28) java: 可能尚未初始化变量res；
那我们target初始化一个几呢？0吗？ 万一人家最后的就是要找0，怎么办，其实巧用数组下标是个好办法。
这其实很简单，我们的目标其实是查找一下这个数字在第几个格子而已。这样的好处就是，格子不可能有负数。
我们不妨这样设计，如果找到了就获得他的下标，如果找不到就得到-1，代码可以优化如下：
From: 元动力1
2
3
4
5
6
7
| int targetIndex = -1;
for (int i = 0; i < salary.length; i++) {
if(salary[i] == 9){
targetIndex = i;
}
break;
}
|
3、打擂台的形式找最大值
今天要比武决胜负，找出一个武功最高的当武林盟主。
1、黄蓉在台上大喊，今天我们要比武决胜负，选出一位丐帮帮主，哪位英雄好汉愿意第一个上。
2、丁春秋第一个上来，大吼，谁敢上来和我比试比试？
3、郭芙蓉上台一个排山倒海干掉了丁春秋，于是丁春秋下台，台上站的是郭芙蓉。
4、大家你来我往，一个一个上，最后站在台上的是张无忌，顺利当选。
我们的代码如下：
From: 元动力1
2
3
4
5
6
7
8
9
10
11
12
13
|
int[] salary = {4,5,0,6,7,8};
int maxIndex = 0 ;
for (int i = 1; i < salary.length; i++) {
if(salary[i] > salary[maxIndex]){
maxIndex = i;
}
}
System.out.println("经过了n轮比赛得到的最大值得下标是："+maxIndex+"。值是："+salary[maxIndex]);
|
作业：
写一段代码，找出一个数组的最小值。
4、元素的位移
一个新的需求：
我门计划将数组中的两个元素交换位置。
From: 元动力1
2
3
4
| int[] salary = {4,5,0,6,7,8};
salary[0] = salary[1];
salary[1] = salary[0];
|
我们第一次很有可能写出这样的代码。
salary[0] = salary[1]; 这句话执行完了之后 数组中 就出现了两个salary[1]了。
合适的方法是，在找一个空间，临时存一下salary[0]。
From: 元动力1
2
3
4
5
| int[] salary = {4,5,0,6,7,8};
int temp = salary[0];
salary[0] = salary[1];
salary[1] = temp;
|
5、数组的扩容
我们一定要知道，数组本质上不能改变大小，实质上的扩容是不行的，需要使用一些手段。
画一个图吧：
image-20210802163532080
From: 元动力1
2
3
4
5
6
7
8
9
10
11
12
13
|
int[] nums = new int[]{3,4,6};
int[] temp = new int[6];
for (int i = 0; i < nums.length; i++) {
temp[i] = nums[i];
}
nums = temp;
for (int i = 0; i < nums.length; i++) {
System.out.println(temp[i]);
}
|
【问题】
我使用temp修改数组的值，会不会影响nums？
6、数组的反转
（1）思路一：
创建一个等长的数组，反向放入，最后改变引用即可
From: 元动力1
2
3
4
5
6
7
8
9
| int[] nums = new int[]{3,4,6};
int[] temp = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
temp[i] = nums[nums.length - 1 - i];
}
nums = temp;
for (int i = 0; i < nums.length; i++) {
System.out.println(temp[i]);
}
|
（2）思路二
利用交换的方式：
image-20210802164737918
From: 元动力1
2
3
4
5
6
7
8
9
10
11
|
int[] nums = new int[]{3,4,6};
for (int i = 0; i < nums.length/2; i++) {
int temp = nums[nums.length - 1 - i];
nums[nums.length - 1 - i] = nums[i];
nums[i] = temp;
}
for (int i = 0; i < nums.length; i++) {
System.out.println(nums[i]);
}
|
7、练习作业：
元动力人事工号管理系统：
1、可以不断的选择功能，一是新增工号，二是查找工号
From: 元动力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
| import java.util.Scanner;
public class YdlHr {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int nums[] = new int[2];
int currentIndex = -1;
while (true){
System.out.println("请选择功能：1 添加工号 2 查找工号 3 打印所有员工 4 退出");
int function = scanner.nextInt();
if(function == 4){
break;
}
if(function == 1){
System.out.println("请输入要添加的工号：");
int num = scanner.nextInt();
currentIndex++;
if(currentIndex > nums.length-1){
int[] temp = new int[nums.length*2];
for (int i = 0; i < nums.length; i++) {
temp[i] = nums[i];
}
nums = temp;
}
nums[currentIndex] = num;
}
if(function == 2){
System.out.println("请输入要查找的工号：");
int num = scanner.nextInt();
int result = -1;
for (int i = 0; i < nums.length; i++) {
if(nums[i] == num){
result = i;
break;
}
}
System.out.println( result == -1 ? "改工号不存在" : "该工号存在："+nums[result] );
}
if(function == 3){
for (int i = 0; i <= currentIndex; i++) {
System.out.println(nums[i]);
}
}
}
}
}
|
学会使用debug排错
三、初识算法
数据结构是把数据在内存或磁盘存放时的规矩。是一个图书馆的书架，格子都给你规定好了，我们可以按照预设的方式去摆放图书。
算法是具体的动作，是怎么去摆放，怎么快速的找到我要的图书。
注意，我们的课程主线是怎么敲代码，在学习javase的阶段如果太痴迷于算法，你就学不完了。但是如果你大一大二时间多，那没问题。我会在后期的附加课中，讲解每一种排序方法，这里我们只选择讲解最简单的。
1、排序算法
我们的图书都放在了格子里，但是没有按照编号从小到大的排序，现在需要你完成这个工作。
这个场景下，必须这样做：
如果是你，你会怎么去排序呢？
简单排序：选择排序 插入排序 冒泡排序
高级排序：希尔排序 快速排序 归并排序
对排序 桶排序 基数排序
（1）冒泡排序
每一轮都是两两相比，大的靠后站，经过一轮下来，会将最大的冒到最后边。其实计算机是很笨的，我们用最笨的方法，就能解决很多问题。
image-20210802180546567那咱们就开始吧：
- 0和1比 ，1高不动
- 1和2比，1高，往后挪
- 这一轮下来，最高的就到了最后了。
image-202108021806562544、最后一个确定了就不用参与排序了，我们只对前边的用相同的方式继续就行了。
再来一轮：
image-20210802180920194一共需要length-1轮，因为第一个只剩一个的时候，就不需要了。
image-20210802181207198代码实现：
From: 元动力1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int[] nums = {3, 7, 4, 9, 5, 4, 1};
for (int j = 0; j < nums.length - 1 ; j++) {
for (int i = 0; i < nums.length - 1 -j ; i++) {
if (nums[i] > nums[i + 1]) {
int temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
}
}
}
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " ");
}
|
2、查找算法
怎么查找，我们之前已经讲过了，一个个遍历，找到拿出即可啊，这种方法叫【顺序查找】【，那有没有更加高效的方法呢？如果数组本身无序，那确实没事好的办法，但是如果数组有序那就不一样了啊。
【举个例子】，你去图书馆找一本书，如果你知道这个书架上的书是按照编号有序排列，你会从头开始一个一个找吗？
你大概的思路是这样的，先去中间看看，如果我找的书的编号比中间的大我就去左边找，否则去右边找。
这种思路就是我们的二分查找法：
（1）二分查找（折半查找）
如图所示：
image-20210803101044468代码实现：
From: 元动力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
| public class BinarySearch {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] nums = {1,3,5,7,8,12,23};
System.out.println("请输入您要查找的数字：");
int target = scanner.nextInt();
int left = 0;
int right = nums.length - 1;
if(target < nums[0] || target > nums[nums.length-1]){
System.out.println("您输入的不在范围之内！");
} else {
int res = -1;
while (left <= right){
int middle = (left + right)/2;
if(nums[middle] == target){
res = middle;
break;
} else if(nums[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
}
System.out.println(res);
}
}
}
|
3、算法性能
通常我们考虑一个算法的指标是看其在时间和空间两个维度的表现决定的。
- 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
- 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。
最经典的方法：叫「 大O符号表示法 」
（1）时间复杂度
a、线性阶
我们先来看个我们之前的例子：
From: 元动力1
2
3
4
5
6
7
| int targetIndex = -1;
for (int i = 0; i < salary.length; i++) {
if(salary[i] == 9){
targetIndex = i;
}
break;
}
|
通过「 大O符号表示法 」，这段代码的时间复杂度为：O(n) ，为什么呢?
对于我们这种顺序检索，随着数组的大小的变化，查询需要遍历的次数也会线性增长，n就好比要查找的次数。
b、常数阶
那如果有这么一种算法，无论数组多长，查询只需要一次就能出结果，这样的时间复杂度就是O(1)，后边我们会学习hash
c、指数阶
思考，我们的冒泡排序呢？
随着数组长度的变化，我们遍历的次数是指数级增长的，那他的时间复杂度就是O(n^2)。
d、对数阶
思考、我们的二分查找法呢
试想：
- 一个有序数组长度为8 最多需要3次即可，应为也只能折3次
- 一个有序数组长度为16 最多需要4次即可，应为也只能折4次
- 一个有序数组长度为32 最多需要5次即可，应为也只能折5次
这这很明显是一个对数关系：n是纵坐标，循环的次数的横坐标，看不懂就算了。
【这种算法下，你的数据越多效果越明显】。
e、高级排序
高级排序会在后续的附加课一一讲解，咱们就不在细说了。
O(logN*n)
（2）空间复杂度
和时间复杂度类似，空间复杂度就是在我的算法下，数据的长度越长，你额外需要多少空间。
比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：
a、空间复杂度 O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1) 比如咱们刚刚学习的冒泡排序，二分查找，无论数组多长，我们依然不需要更多的额外空间。
b、空间复杂度 O(n)
思考我们的数组反转：
思路一：创建一个等长的数组，反向放入，最后改变引用即可
这种方法，你的数组越长，总是需要一个等长的数据作为额外空间，这种增长是线性的，所以他的空间复杂度是O(n);
他的时间复杂度呢？ O(n)
思路二：利用首尾两两交换的方法
这种方法，你并不需要去创建额外的空间，所以他的空间复杂度是O(1);
他的时间复杂度呢？ O(n/2)
很明显，第二种方法在时间复杂度和空间复杂度上都要更加优秀。
- 算法是有优劣的。有的人写的是真牛逼，有的人写的是真辣鸡。
- 一段代码的性能和代码的长短没有毛线关系，不是越长的越好，也不是越短的越好。
4、归并的思想
小案例：
给你两个有序数组，合并成一个大的有序的数组。
（1）思路一：
创建一个大的数组，长度为两个数组之和，然后冒泡排序。
代码不写了。
（2）思路二：
归并思路如下：
1、同时遍历两个数组，遍历的当前值进行比较，小的放入新数组。
image-202108031050319522、放进去之后，数据继续遍历，指针后移。
image-202108031050465263、经过多次遍历
image-20210803105058061代码实现：
From: 元动力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
| public class Demo<a> {
public static void main(String[] args) {
int[] array1 = {1,3,5,8,12,35,54,456,2545};
int[] array2 = {2,4,7,10,40,60};
int i = 0;
int j = 0;
int[] newArray = new int[array1.length+array2.length];
while ( i<array1.length || j<array2.length){
if(i == array1.length){
newArray[i+j] = array2[j];
j++;
continue;
}
if(j == array2.length){
newArray[i+j] = array1[i];
i++;
continue;
}
if(array1[i] < array2[j]){
newArray[i+j] = array1[i];
i++;
} else {
newArray[i+j] = array2[j];
j++;
}
}
for (int l = 0; l < newArray.length; l++) {
System.out.println(newArray[l]);
}
}
}
|
每个人写的代码，都不一样，我们学习的是思路，是思想。
四、二维数组
二维数组使用的频率很少，但是也有一些类似的需求，比如我们开发一个围棋游戏， 棋盘就可以用二维数组来表示。 如图：
怎么定义一个数组呢？
From: 元动力1
| 比如: int nums[][]=new int[2][3]
|
在内存中二维数组张这个样子：
image-20210802171351473请用二维数组输出如下图形 :TwoDimensionalArray
From: 元动力1
2
3
4
5
6
7
8
9
10
11
| int[][] nums = {{1,2,3,4,5,6},
{6,5,4,3,2,1},
{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.print(arr[i][j] + " ");
}
System.out.println();
}
|
思考，二维数组里的每一个数组的长度一定要一样吗，如下图可以吗？
image-20210802172753104答案是可以的：
From: 元动力1
| int[][] nums = {{1,4},{1,2,6},{5,6,3,2,1}};
|
我们还可以这样赋值：
From: 元动力1
2
3
4
5
6
|
int[][] nums = new int[3][];
nums[0] = new int[5];
nums[1] = new int[3];
nums[2] = new int[7];
|
明白一个道理，初识化只要知道我需要多少空间，然后在堆内存给他分配就好了。
附加题：
写一个杨辉三角，他是这么一个三角：
- 每个数等于它上方两数之和。
- 每行数字左右对称，由1开始逐渐变大。
- 第n行的数字有n项。
- 前n行共[(1+n)n]/2 个数。
我们的输入目标：
From: 元动力1
2
3
4
5
6
7
| 使用二维数组打印一个 10 行杨辉三角
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
|
代码实现
From: 元动力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
| public class YangHui {
public static void main(String[] args) {
int max = 10;
int[][] nums = new int[max + 1][];
for (int n = 0; n <= max; n++)
nums[n] = new int[n + 1];
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[i].length; j++) {
if (j == 0 || j == nums[i].length - 1) {
nums[i][j] = 1;
} else {
nums[i][j] = nums[i-1][j-1] +nums[i-1][j];
}
}
}
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[i].length; j++) {
System.out.print(nums[i][j]+" ");
}
System.out.println();
}
}
}
|
