1.什么是算法?
就是一系列可以解决问题的 清晰的 可执行的计算机指令
那么生活中有哪些算法?
问路:坐公交车到达某一站下车—>再转某一个地铁站 这个地铁站坐几号线?从哪一站下车?下车以后从几号地铁口出去?—>再怎么走就能到了–>😃
求解方程:一步一步的求解一元二次方程,这里涉及的每一步都是清晰可执行的
这一系列的指令本质其实就是一个算法: 解决了如何到达目的地的一个问题，解决了如何求得一个一元二次方程的解
1.1算法的五大特性
① 有限性:
一个算法不应该是无限循环的,应该在有限的时间里可以执行完
有限时间 ≠ 时间短 : 假设一个算法需要万年亿年才能执行完,那么从原则上讲他也是一个算法,只不过他消耗的时间太长,这个算法并不实用而已,同样的,不实用不代表没有意义,研究算法恰恰是从这样的一个看似不可行的算法出发,一步一步的优化它,最终得到一个可行的算法
② 确定性
它是一系列清晰的可执行的计算机指令, 那么每一个指令本身是含义唯一的, 不会产生二义性
假设一个指令要求说出某校成绩最高的学生,严谨来讲,他就是会产生二义性的,"成绩最高"在不同人眼里,可能理解到的含义不同 ,最终执行的结果就不同(语文成绩最高?数学成绩最高?总成绩最高)
含义唯一 ≠ 相同输入会有相同输出 : 对于一个随机算法来说，那么很有可能输入是同样的一个数据，输出的结果呢却不相同
③可行性
算法中的每一步应该是可行的
假设算法要求拿出最大的质数，那么这个指令呢 就是不可行的——质数有无穷个的
④输入
对于一个算法来说，它是有输入的
一个函数我们就可以把它理解成一个算法 它内部执行了一系列的运算 获得了一些结果 那么对于一个函数来说 我们是可以给它指定输入的参数 并且指定返回的类型
函数没有任何的输入的参数 ≠ 算法没有输入 : 算法的输入的概念是更加广义的，对于一个函数来讲，可能并没有输入的参数，但对于一个算法来说，他肯定是有他需要操作的对象的，那么他所操作的这些对象就是这个算法的输入
具体表现在程序中，一个算法操作的对象有可能定义在一个类中，它是一个成员变量，是一个全局变量，它不是这个函数的参数，那么它也是这个算法的输入，甚至有可能一个算法操作的对象本身隐藏在这个算法的语义中——比如设计一个算法，这个算法他做的事情就是生成零这个数字，所以这个算法内部的逻辑直接通过return 0返回零就好了，那么这个算法看起来没有输入的值，但是其实我们必须在数学上定义清楚了0：0到底是什么？才能返为零这样的一个数字。那么从数学上拥有了零这个概念本身就是我们这个算法的输入
一个算法是有输入的，这个输入本身应该站在一个更高的层次去理解，它可以是一个很抽象的输入
⑤输出
对于一个算法来说，它是有输出的
与输入同理，一个函数可能没有返回值，返回值是void类型，这不意味着这个算法没有输出
比如一个算法做的事情是在屏幕中绘制了一个圆 ，那么这样的一个绘制函数很有可能它的返回类型是void，但是这个算法本身确实在我们的这个屏幕中把这个圆绘制出来了，这个绘制的结果就是这个算法的输出。
或者一个算法做的事情就是休眠x分钟，x是一个输入，那么对于这个算法来说，没有返回值，只是执行了休眠x分钟这样的一个操作，返回值是void，但是这个算法的输出就是我们的这个程序真的休眠了x分钟，在这x分钟中不进行任何的响应
2.线性查找法
2.1生活中的线性查找法
高三的时候，老班经常晚自习进行模拟考试，在批完卷子后，由课代表将试卷发下去，此时每张卷子都有对应的同学名字，这时有的同学就会主动去课代表那里找到自己的卷子，而方法就是：把这一张试卷拿到自己的面前 看一下第一张卷子是不是自己的，如果不是，那么看第二张卷子是不是自己的，如果还不是，看第三张卷子是不是自己的，以此类推…比如说，看到第五张卷子，发现这张卷子就是自己的，那么就找到了，这就叫做线性查找法： 一个一个的去寻找自己想要找到的那个目标元素
上面的一张卷子，可以理解成就是在一个数组中查找某一个元素，数组是非常简单的这样一种数据结构
2.2 计算机中的线性查找法
假设我们就是在一个叫做data这样的数组中查找元素16，数组中一共有八个元素，八个元素所对应的索引是0 1 2 3 4 5 6 7，对应的值分别是24 18 12 9 16 66 32 4
想在这个数组中查找目标16，应用线性查找法的思路，应该怎样找？
设置一个 索引i，初始的时候是0
从0开始查看这个data数组中对应的元素是不是我们的目标
data[0]的值是24≠16，进行i++(其实这就是一个循环的过程)
data[1]的值是18≠16，继续进行i++
…
data[4]的值是16=16，我们就找到了这个结果
上述过程就叫做线性查找法——对于这个线性查找法，整个算法的输入是什么？
这个输入包含有一个数组——即我们要从一堆试卷中找到属于自己的那一张试卷，首先要有这一堆试卷，在算法中用一个数组来表示
输入还应该包含一个目标元素 ——知道自己的名字是什么，才能在这一点试卷中找到属于自己的那一张试卷，在上面这个例子中，目标元素其实就是16
对于这个线性查找法，整个算法的输出是什么？
设计这个算法的输出是目标元素所在的索引——例子中16这个元素索引为4，这个算法返回就应该是4
也有可能你想要查找的这个目标在数组中不存在——返回-1，因为-1不是一个合法的索引值 (对于任何一个索引值来说 肯定是大于等于零的一个值)
3.线性查找法的实现
3.1初步实现
public class LinearSearch {
/*
@function 线性查找的方法
@param data 整型数组 待查找的数组
@param terget 整型数组 查找的目标
@return 整型 找到的索引值或-1
*/
public int search(int[] data, int target) {
for (int i = 0; i < data.length; i++) {
if (data[i] == target)
return i; //如果找到目标，返回对应的索引值
}
return -1; //如果没有找到目标，返回-1
}
public static void main(String[] args) {
//准备用于查找的数组
int[] data = {24, 18, 12, 9, 16, 66, 32, 4};
LinearSearch ls = new LinearSearch(); //声明一个LinearSearch的对象
//调用LinearSearch的search(),查找目标16
//将返回的结果赋值给一个整型变量res
int res = ls.search(data, 16);
System.out.println(res); //输出res
int res2 = ls.search(data,666); //查找目标666
System.out.println(res2);
}
}
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
运行结果
3.2 代码优化
3.2.1优化1
没有必要声明一个LinearSearch的对象，可以将search()改成静态的方法，这样在调用search()的时候，就可以直接用LinearSearch这个类名进行调用search()
用户不需要创建一个LinearSearch的对象，他只希望使用线性查找的方式从某个数组中查找一个元素，我们将这个方法写成static，直接让用户调用这个方法就好了，而不需要new 一个新对象
public class LinearSearch {
/*
@function 线性查找的方法，static将其设置为静态方法
@param data 整型数组 待查找的数组
@param terget 整型数组 查找的目标
@return 整型 找到的索引值或-1
*/
public static int search(int[] data, int target) {
for (int i = 0; i < data.length; i++) {
if (data[i] == target)
return i; //如果找到目标，返回对应的索引值
}
return -1; //如果没有找到目标，返回-1
}
public static void main(String[] args) {
//准备用于查找的数组
int[] data = {24, 18, 12, 9, 16, 66, 32, 4};
//调用LinearSearch的search(),查找目标16
//将返回的结果赋值给一个整型变量res
int res = LinearSearch.search(data, 16);
System.out.println(res); //输出res
int res2 = LinearSearch.search(data,666); //查找目标666
System.out.println(res2);
}
}
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
3.2.2 优化2
上述优化后，虽然用户能直接通过LinearSearch.search()调用方法，但是用户依然可以进行“new一个LinearSearch类的对象”的操作，如何阻止这一操作？可以在LinearSearch中将LinearSearch的构造函数声明为私有的即可
public class LinearSearch {
//将LinearSearch的构造函数声明为私有
private LinearSearch(){}
/*
@function 线性查找的方法，static将其设置为静态方法
@param data 整型数组 待查找的数组
@param terget 整型数组 查找的目标
@return 整型 找到的索引值或-1
*/
public static int search(int[] data, int target) {
for (int i = 0; i < data.length; i++) {
if (data[i] == target)
return i; //如果找到目标，返回对应的索引值
}
return -1; //如果没有找到目标，返回-1
}
public static void main(String[] args) {
//准备用于查找的数组
int[] data = {24, 18, 12, 9, 16, 66, 32, 4};
//调用LinearSearch的search(),查找目标16
//将返回的结果赋值给一个整型变量res
int res = LinearSearch.search(data, 16);
System.out.println(res); //输出res
int res2 = LinearSearch.search(data,666); //查找目标666
System.out.println(res2);
}
}
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
虽然将LinearSearch的构造函数声明为私有，但是上述代码中的main()里依旧可以进行“new一个LinearSearch类的对象”的操作
这是因为当前的main()是LinearSearch类的内部的函数，所以它依然可以访问到LinearSearch中的所有方法（包括私有方法），但这个优化的思想是没有问题的，是需要我们学习的
