【从浅到深的算法技巧】4.静态方法

1.1.6静态方法

在许多语言中，静态方法被称为函教，静态方法是一组在被调用时会被顺序执行的语句。修饰符static将这类方法和1.2的实例方法区别开来。当讨论两类方法共有的属性时我们会使用不加定语的方法一词。

1.1.6.1静态方法

方法封装了由一系列语句所描述的运算。方法需要参数(某种数据类型的值)并根据参数计算出某种数据类型的返回值(例如数学函数的结果)或者产生某种副作用(例如打印一个值)。BinarySearch 中的静态函数rank()是前者的一个例子; main()则是变量后者的一个例子。 每个静态方法都是由签名(关键字public static以及函数的返回值，方法名以及一串各种类型的参数)和函数体(即包含在花括号中的代码)组成的。

典型静态方法的实现

任务	实现
计算一个整数的绝对值	public static int abs(int x) { if (x<0) return -x；else return x; }
计算一个浮点数的绝对值	public static double abs(double x) { if (x < 0.0) return -x; else return x; }
判定一个数是否是素数	public static boolean isPrime(int N){ for (int=2; i*i <= N; i++) for(N%i ==0) return false; return true; } }
计算平方根(牛顿迭代法)	public static double sqrt(double c){ if (c <0) return Double. NaN; double err=le -15; while (Math.abs(t - c/t) > err*t) return t; }
计算直角三角形的斜边	public static double hypotenuse(double a, double b){ return Math. sqrt(a* a + b*b); }

1.1.6.2调用静态方法

调用静态方法的方法是写出方法名并在后面的括号中列出参数值，用逗号分隔。当调用是表达式的一部分时，方法的返回值将会替代表达式中的方法调用。例如，BinarySearch 中调用rank()返回了一个int值。仅由一个方法调用和一个分号组成的语句一般用于产生副作用。例如，BinarySearch 的main()函数中对系统方法Arrays . sort()的调用产生的副作用，是将数组中的所有条目有序地排列。调用方法时，它的参数变量将被初始化为调用时所给出的相应表达式的值。返回语句将结束静态方法并将控制权交还给调用者。如果静态方法的目的是计算某个值，返回语句应该指定这个值(如果这样的静态方法在执行完所有的语句之后都没有返回语句，编译器会报错)。

1.1.6.3方法的性质

下面是对方法性质的描述:

1.方法的参数按值传递:在方法中参数变量的使用方法和局部变量相同，唯一不同的是参数变量的初始值是由调用方提供的。方法处理的是参数的值，而非参数本身。这种方式产生的结果是在静态方法中改变一个参 数变量的值对调用者没有影响。本书中我们一般不会修改参数变量。值传递也意味着数组参数将会是原数组的别名——方法中使用的参数变量能够引用调用者的数组并改变其内容(只是不能改变原数组变量本身)。例如，Arrays. sort()将能够改变通过参数传递的数组的内容，将其排序。

2.方法名可以被重载:例如，Java的Math包使用这种方法为所有的原始数值类型实现了Math. abs()、Math.main()和Math. max()函数。重载的另一种常见用法是为函数定义两个版本，其中一个需要一个参数而另一个则为该参数提供一个默认值。

3.方法只能返回一个值，但可以包含多个返回语句:一个Java方法只能返回一个值，它的类型是方法签名中声明的类型。静态方法第一次执行到一-条返回语句时控制权将会回到调用代码中。尽管可能存在多条返回语句，任何静态方法每次都只会返回一个值，即被执行的第一条返回语句的参数。

4.方法可以产生副作用:方法的返回值可以是void,这表示该方法没有返回值。返回值为void的静态函数不需要明确的返回语句，方法的最后一条语句执行完毕后控制权将会返回给调用方。我们称void类型的静态方法会产生副作用(接受输入、产生输出、修改数组或者改变系统状态)。例如，我们的程序中的静态方法main()的返回值就是void,因为它的作用是向外输出。技术上来说，数学方法的返回值都不会是void ( Math. random()虽然不接受参数但也有返回值 )。

实例方法也拥有这些性质，尽管两者在副作用方面大为不同。

1.1.6.4递归

方法可以调用自己。例如，下面给出了BinarySearch 的rank()方法的另一种实现。 我们会经常使用递归，因为递归代码比相应的非递归代码更加简洁优雅、易懂。下面这种实现中的注释就言简意赅地说明了代码的作用。我们可以用数学归纳法证明这段注释所解释的算法的正确性。

编写递归代码时最重要的有以下三点。

1.递归总有一个最简单的情况一方法的第一条语句总是一个包含 return的条件语句。

2.递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。在下面的代码中，第四个参数和第三个参数的差值一直在缩小。

3.递归调用的父问题和尝试解决的子问题之间不应该有交集。在下面的代码中，两个子问题各自操作的数组部分是不同的。

二分查找的递归实现

public static int rank(int key, int[] a)

{ return rank(key, a, 0, a. length- 1); }

public static int rank(int key, int[] a, int 10, int hi){ //如果key存在于a[]中， 它的索引不会小于10且不会大于hi

if (lo> hi) return  -1;

int mid=lo+ (hi - lo) / 2;

if(key < a[mid]) return rank( key, a, 10, mid-1);

else if (key> a[mid]) return rank(key, a, mid + 1, hi);

else return mid;

}

1.1.6.5基础编程模型

静态方法库是定义在一个Java类中的一组静态方法。 类的声明是public class 加上类名，以及用花括号包含的静态方法。存放类的文件的文件名和类名相同，扩展名是java。Java 开发的基本模式是编写一个静态方法库(包含一个main()方法)来完成一个任务。输人java和类名以及一系列字符串就能调用类中的main()方法，其参数为由输入的字符串组成的一个数组。main()的最后一条语句执行完毕之后程序终止。 在本书中，当我们提到用于执行一项任务的Java程序时，我们指的是用这种模式开发的代码。例如，BinarySearch就是一个由两个静态方法rank()和main()组成的Java程序，它的作用是将输人中所有不在通过命令行指定的白名单中的数字打印出来。

1.1.6.6模块化编程

这个模型的最重要之处在于通过静态方法库实现了模块化编程。我们可以构造许多个静态方法库(模块)，一个库中的静态方法也能够调用另- 个库中定义的静态方法。这能够带来许多好处:

1.程序整体的代码量很大时，每次处理的模块大小仍然适中;

2.可以共享和重用代码而无需重新实现;

3.很容易用改进的实现替换老的实现:

4.可以为解决编程问题建立合适的抽象模型;

5.缩小调试范围

1.1.6.7单元测试

Java 编程的最佳实践之一就是每 个静态方法库中都包含一个 main()函数来测试库中的所有方法(有些编程语言不支持多个main()方法，因此不支持这种方式)。恰当的单元测试本身也是很有挑战性的编程任务。每个模块的main()方法至少应该调用模块中的其他代码并在某种程度上保证它的正确性。随着模块的成熟，我们可以将main()方法作为一个开发用例，在开发过程中用它杂时，我们可能会将它独立成一个模块。

1.1.6.8 外部库

我们会使用来自4个不同类型的库中的静态方法，重用每种库代码的方式都稍有不同。它们大多都是静态方法库，但也有部分是数据类型的定义并包含了一些静态方法。

1.系统标准库java.lang*:这其中包括Math库，实现了常用的数学函数; Integer 和Double库，能够将字符串转化为int和double值; String 和StringBuilder库等等以及其他一些我们没有用到的库。

2.导入的系统库，例如java.utils.Arrays: 每个标准的Java版本中都含有上千个这种类型的库，而且要在程序的开头使用import语句导入才能使用这些库。

要调用另一个库中的方法(存放在相同或者指定的目录中，或是一个系统标准库，或是在类定义前用import语句导入的导库)，我们需要在方法前指定库的名称。例如，BinarySearch 的main()方法调用了系统库java.utils.Arrays的sort()方法，我们的库StdIn中的readInts()方法和StdOut库中的println()方法。

含有静态方法的数据类型的定义

//系统标准库

Double

String

StringBuilder

//导入的系统库

java.utils.Arrays

//我们的标准库

StdIn

StdOut

StdDraw

StdStats

Out