Java语言程序设计与数据结构 - 第07章一维数组 - 《编程》

7.1 引言
7.2 数组的基础知识
7.3 示例学习：分析数字
7.4 示例学习：一副牌
7.5 复制数组
7.6 将数组传递给方法
7.7 方法返回数组
7.8 示例学习：统计每个字母出现的次数
7.9 可变长参数列表
7.10 数组的查找
- 7.10.1 线性查找法
- 7.10.2 二分查找法
7.11 数组的排序
7.12 Arrays类
7.13 命令行参数
- 7.13.1 向main方法传递字符串
- 7.13.2 示例学习：计算器

7.1 引言

单个的数组变量可以引用一个大的数据集合

7.2 数组的基础知识

一旦数组被创建，它的大小是固定的。使用一个数组引用变量和下标来访问数组中的元素

7.2.1 声明数组变量

为了在程序中使用数组，必须声明一个引用数组的变量，并指名数组的元素类型。下面是声明数组变量的语法：
```
elementType[]  arrayRefVar;
```

或者

elementType arrayRefVar[]; //Allowed, but not preferred

elementType可以是任意数据类型，但是数组中所有的元素都必须具有相同的数据类型。例如：下面的代码声明变量myList，它引用一个具有double型元素的数组
```
double[] myList;
```

或者

double myList[]; //Allowed, but not preferred

也可以用elementType arrayRefVar[] (元素类型数组引用变量[ ] )声明数组变量。这种来自C/C语言的风格被Java采纳以适用于C/C程序员。推荐使用elementType[ ] arrayRefVar (元素类型 [ ] 数组引用变量)风格。

7.2.2 创建数组

不同于声明基本数据类型变量，声明一个数组变量时并不给数组分配任何内存空间。它只是创建一个对数组的引用的存储位置。如果变量不包含对数组的引用，那么这个变量的值为**null**。除非数组已经被创建，否则不能给它分配任何元素。声明数组变量之后，可以使用下面的语法用new操作符创建数组，并且将它的引用赋给一个变量：
```
arrayRefVar = new elementType[arraySize];
```

这条语句做了两件事情：
- 使用new elementType[arraySize] 创建了一个数组
- 把这个新创建的数组的引用赋值给变量arrayRefVar
声明一个数组变量、创建数组、将数组引用赋值给变量这三个步骤可以合并在一条语句里，如下所示：
```
elementType[] arrayRefVar = new elementType[arraySize];
```

或

elementType arrayRefVar[] = new elementType[arraySize];

下面是使用这种语句的一个例子：
```
double[] myList = new double[10];
```

这条语句声明了数组变量myList，创建了一个由10个double型元素构成的数组，并将该数组的引用赋值给myList。
一个数组变量看起来似乎是存储了一个数组，但实际上它存储的是指向数组的引用。严格地讲，一个数组变量和一个数组是不同的，但多数情况下它们的差别是可以忽略的。因此，为了简化，通常可以说myList是一个数组，而不用更长的陈述：myList是一个含有double型元素数组的引用变量

7.2.3 数组大小和默认值

当给数组分配空间时，必须指定该数组能够存储的元素个数，从而确定数组大小。创建数组之后就不能在修改它的大小。可以使用arrayRefVar.length得到数组的大小。例如：myList.length为10.
当创建数组后，它的元素被赋予默认值，数值型基本数据类型的默认值为0，char型的默认值为’\u0000’,boolean 型的默认值为false

7.2.4 访问数组元素

数组元素可以通过下标访问。数组下标是基于0的，也就是说，其范围从0开始到arrayRefVar.length - 1结束。例如，在图7-1的例子中，数组myList包含10个double值，而且下标从0到9
数组中的每个元素都可以使用下面的语法表示，称为下标变量（indexed variable）
一些语言使用圆括号引用数组元素，例如myList(9)。而Java语言使用方括号，例如myList[9]

7.2.5 数组初始化简写方式

Java有一个简捷的标记，称作数组初始化简写方式，它使用下面的语法将声明数组、创建数组和初始化数组结合到一条语句中：
```
elementType[] arrayRefVar = {value0, value1, ... , valuek};
```

例如：
```
double[] myList = {1.9, 2.9, 3.4, 3.5};
```

这条语句声明、创建并初始化包含4个元素的数组myList，它等价于下列语句：
数组初始化简写方式中不使用操作符new。使用数组初始化简写方式时，必须将声明、创建和初始化数组都放在一条语句中。将它们分开会产生语法错误。因此，下面的语句是错误的：
```
double[] myList;
myList = {1.9, 2.9, 3.4, 3.5};//error
```

7.2.6 处理数组

处理数组元素时，经常会用到for循环，理由有以下两点：
- 数组中所有元素都是同一类型的。可以使用循环以同样的方式反复处理这些元素
- 由于数组的大小是已知的，所以很自然地就使用for循环

下面是一些处理数组的例子：

（使用输入值初始化数组）下面的循环使用用户输入值初始化数组myList

java.util.Scanner input = new java.util.Scanner(System.in);
System.out.println("Enter " + myList.length + " values:");
for(int i = 0; i < myList.length; i++)
myList[i] = input.nextDouble();

（使用随机数初始化数组）下面的循环使用0.0到100.0之间，但小于100.0的随机值初始化数组myList。
```
for(int i = 0; i < myList.length; i++){
myList[i] = Math.random() *  100;
}
```

（显示数组）为了打印数组，必须使用类似下面的循环，打印数组中的每一个元素
```
for(int i = 0; i <myList.length; i++){
System.out.print("myList[i]" + " ");
}
```

提示：对于char[ ] 类型的数组，可以使用一条打印语句打印。例如下面的代码显示Dallas：
```
char[] city = {'D'、'a'、'l'、'l'、'a'、's'};
System.out.println(city)
```

（对所有元素求和）使用名为total的变量存储和。total的值初始化为0。使用如下循环将数组中的每个元素加到total中：
```
double total = 0;
for(int i = 0 ; i < myList.length; i++){
total += myList[i];
}
```

（找出最大元素）使用名为max的变量存储最大元素。将max的值初始化为myList[0]。为了找出数组myList中的最大元素，将每个元素与max比较，如果该元素大于max，则更新max
```
double total = 0;
for(int i = 0 ; i < myList.length; i++){
if(myList[i] > max) max = myList[i];
}
```

（找出最大元素的最小下标值）经常需要找出数组中的最大元素。如果数组中含有多个最大元素，那么找出最大元素的最小下标值。假设数组myList为{1，5，3，4，5，5}。最大元素为5，5的最小下标为1。使用名为max的变量存储最大元素，使用名为indexOfMax的变量表示最大元素的下标。将max的值初始化为myList[0]，而将indexOfMax的值初始化为0。将myList 中的每个元素与max比较，如果这个元素大于max，则更新max和indexOfMax。
```
double max = myList[0];
int indexOfMax = 0;
for(int i = 1; i < myList.length;i++){
if(myList[i] > max){
  max = myList[i];
  indexOfMax = i;
}
}
```

（随机打乱）在很多应用程序中，需要对数组中的元素进行任意的重新排序。这称作打乱（shuffling）。为完成这种功能，针对每个元素myList[i],随意产生一个下标j，然后将myList[i]和myList[j]互换，如下所示：
```
for(int i = 0; i < myList.length -1 ; i++){
//Generate an index j randomly
int j = (int)(Math.random() * myList.length);
//Swap myList[i] with myList[j]
double temp = myList[i];
myList[i] = myList[j];
myList[j] = temp;
}
```

（移动元素）有时候需要向左或向右移动元素。这里的例子就是将元素向左移动一个位置并且将第一个元素放在最后一个元素的位置： ```java double temp = myList[0];//Retain the first element

//Shift elements left for(int i = 1; i < myList.length; i++){ myList[i-1] = myList[i]; }

//Move the first element to fill in the last position myList[myList.length - 1] = temp;


   -  （简化编码）对于某些任务来说，使用数组可以极大简化编码。例如，假设你想通过给定数字的月份来获得一个该月份的英文名字。如果月份名称保存在一个数组中，给定月份的月份名可以简单通过下标获得。下面的代码提示用户输入一个月份数字，然后显示它的月份名称： 
```java
String[] months = {"January", "February", ... ,"December"};
System.out.print("Enter a month numebr (1 to 12): ");
int monthNumber = input.nextInt();
System.out.println("The month is " + months[monthNumber - 1]);

如果不使用months数组，将不得不使用一个很长的多分支if - else语句来确定月份名称，如下所示：

if(monthNumber == 1)
System.out.println("The month is January");
else if (monthNumber == 2)
System.out.println("The month is February");
...
else
System.out.println("The month is December");

7.2.7 foreach循环

Java支持一个简便的for循环，称为foreach循环，即不使用下标变量就可以顺序地遍历整个数组。例如，下面的代码就可以显示数组myList的所有元素：
```
for(double e : myList){
 System.out.println(e);
}
```

此代码可以读作”对myList中每个元素e进行以下操作”。注意，变量e必须声明为与myList中元素相同的数据类型。
通常，foreach循环的语法为：
```
for(elementType element : arrayRefVar){
 //Process the element
}
```
但是，当需要以其他顺序遍历数组或改变数组中的元素时，还是必须使用下标变量。
越界访问数组是经常会出现的程序设计错误，它会抛出一个运行时错误ArrayIndexOutOfBoundsException。为了避免这类错误的发生，在使用时应确保所使用的下标不超过arrayRefvar.length - 1。
程序员经常错误地使用下标1引用数组的第一个元素，但其实第一个元素的下标应该是0。这称为下标差一错误（off - by - one error）。另一种常犯的差一错误是在循环中应该使用 < 的地方误用 <= 。例如，下面的循环是错误的：
```
for(int i = 0; i <= list.length; i++)
 System.out.print(list[i] + " ");
```

应该用 < 替换 <= 。这种情形下，使用foreach循环可以避免差一错误。

7.3 示例学习：分析数字

编写一个程序，找到大于平均值的项的数目。
现在你可以编写程序来解决本章开始时提出的问题了。问题是，读取100个数，计算这些数的平均值并找到大于平均值的那些项的个数。为了更加灵活地处理任意数目的输入，我们让用户给出输入的个数，而不是将其固定为100。程序清单7-1给出了一个解答。

程序清单 7-1 AnalyzeNumbers.java

public class AnalyzeNumbers {
    public static void main(String[] args) {
        java.util.Scanner input = new java.util.Scanner(System.in);
        System.out.print("Enter the number of items: ");
        int n = input.nextInt();
        double[] numbers = new double[n];
        double sum = 0;
        System.out.print("Enter the numbers: ");
        for (int i = 0; i < n; i++) {
            numbers[i] = input.nextDouble();
            sum += numbers[i];
        }
        double average = sum / n;
        //The number of elements above average
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (numbers[i] > average) {
                count++;
            }
        }
        System.out.println("Average is " + average);
        System.out.println("Number of elements above the average is " + count);
    }
}

7.4 示例学习：一副牌

编写一个程序，从一副牌中随机选出4张牌

程序清单 7-2 DeckOfCards.java

public class DeckOfCards {
    public static void main(String[] args) {
        int[] deck = new int[52];
        String[] suits = {"Spades", "Hearts", "Diamonds", "Clubs"};
        String[] ranks = {"Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King"};
        //Initialize the cards
        for (int i = 0; i < deck.length; i++) {
            deck[i] = i;
        }
        //Shuffle the cards
        for (int i = 0; i < deck.length; i++) {
            //Generate an index randomly
            int index = (int) (Math.random() * deck.length);
            int temp = deck[i];
            deck[i] = deck[index];
            deck[index] = temp;
        }
        //Display the first four cards
        for (int i = 0; i < 5; i++) {
            String suit = suits[deck[i] / 13];
            String rank = ranks[deck[i] % 13];
            System.out.println("Card number " + deck[i] + ": " +
                    rank + " of " + suit);
        }
    }
}

程序为四种花色定义了一个数组suits（第4行），而为一个花色中的13张牌定义一个数组ranks（第5和6行）。这些数组中的每个元素都是一个字符串。
程序在第9和10行用0到51初始化deck。deck的值为0表示黑桃A，1表示黑桃2，13表示红桃A，14表示红桃2.
第13 ~ 19行随意地打乱这副牌。在牌被打乱后，deck[i]中放的是一个任意的值。deck[i] / 13的值为0、1、2或3，该值确定这张牌是哪种花色。deck[i] % 13的值在0到12之间，该值确定这张牌是花色中的哪张牌。如果没有定义suits数组，你将不得不用比较冗长的多分支if - else 语句来确定花色。

7.5 复制数组

要将一个数组中的内容复制到另外一个数组中，需要将数组的每个元素复制到另外一个数组中
复制数组有三种方法：
- 使用循环语句逐个地复制数组的元素
- 使用System类中的静态方法arraycopy
- 使用clone方法复制数组，这将在第13章中介绍
arraycopy方法没有给目标数组分配内存空间。复制前必须创建目标数组以及分配给它的内存空间。复制完成后，sourceArray和targetArray具有相同的内容，但占有独立的内存空间
arraycopy方法违反了Java命名习惯。根据命名习惯，该方法应该命名为arrayCpoy（即字母C大写）。

7.6 将数组传递给方法

当将一个数组传递给方法时，数组的引用被传给方法。
正如前面给方法传递基本数据类型的值一样，也可以给方法传递数组。例如，下面的方法显示int型数组的元素：
```
public static void printArray(int[] array){
 for(int i = 0; i < array.length; i++){
     System.out.println(array[i] + " ");
 }
}
```

可以通过传递一个数组调用上面的方法。例如，下面的语句调用printArray方法显示3、1、2、6、4和2
注意：前面的语句使用下述语法创建数组：
```
new elementType[] {value0,value1, ... , valuek};
```

该数组没有显式地引用变量，这样的数组称为匿名数组（anonymous array）。
Java使用按值传递（pass - by - value）的方式将实参传递给方法。传递基本数据类型变量的值与传递数组值有很大的不同。
对于基本数据类型参数，传递的是实参的值。

对于数组类型参数，参数值是数组的引用，给方法传递的是这个引用。从语义上来讲，最好的描述为传递共享信息（pass - by - sharing）,即方法中的数组和传递的数组是一样的。因此，如果改变方法中的数组，将会看到方法外的数组也改变了

public class TestArrayArguments{
 public static void main(String[] args){
     int x = 1; // x represents an int value
     int[] y = new int[10]; // y represents an array of int values
     m(x,y); // Invoke m with arguments x and y
     System.out.println("x is " + x);
     System.out.println("y[0] is " + y[0]);
 }
 public static void m(int number, int[] numbers){
     number = 1001; // Assign a new value to number
     numbers[0] = 5555; // Assign a new value to numbers[0]
 }
}

你可以会觉得困惑，为什么在调用m之后x仍然是1，但是y[0]却变成了5555。这是因为尽管y和numbers是两个独立的变量，但它们指向同一数组，如图7-5所示。当调用m(x,y)时，x和y的值传递给number 和numbers。因为y包含数组的引用值，所以，numbers现在包含的是指向同一数组的相同引用值。
数组在Java中是对象。JVM将对象存储在一个称作堆（heap）的内存区域中，堆用于动态内存分配。
程序清单7-3给出另外一个例子，说明传递基本数据类型值与传递数组引用变量给方法的不同之处。
程序包含两个交换数组中元素的方法。第一个方法名为swap，它没能将两个整型参数交换。第二个方法名为swapFirstTwoInArray，它成功地将数组参数中前两个元素进行交换。

程序清单 7-3 TestPassArray.java

public class TestPassArray {
    /**
     * Main method
     */
    public static void main(String[] args) {
        int[] a = {1, 2};
        //Swap elements using the swap method
        //invoke - 调用
        System.out.println("Before invoking swap");
        System.out.println("array is {" + a[0] + ", " + a[1] + "}");
        swap(a[0], a[1]);
        System.out.println("After invoking swap");
        System.out.println("array is {" + a[0] + ", " + a[1] + "}");
        //Swap elements using the swapFirstTwoInArray method
        System.out.println("Before invoking swapFirstTwoInArray");
        System.out.println("array is {" + a[0] + ", " + a[1] + "}");
        swapFirstTwoInArray(a);
        System.out.println("After invoking swapFirstTwoInArray");
        System.out.println("array is {" + a[0] + ", " + a[1] + "}");
    }
    /**
     * Swap two variables
     */
    public static void swap(int n1, int n2) {
        int temp = n1;
        n1 = n2;
        n2 = temp;
    }
    /**
     * Swap the first two elements in the array
     */
    public static void swapFirstTwoInArray(int[] array) {
        int temp = array[0];
        array[0] = array[1];
        array[1] = temp;
    }
}

swap方法中的参数为基本数据类型，所以调用swap（a[0],a[1]）时，a[0]和a[1]的值传给了方法内部的n1和n2。n1和n2的内存位置独立于a[0]和a[1]时的内存位置。这个方法的调用没有影响数组的内容
swapFirstTwoInArray方法的参数是一个数组。如图7-6所示，数组的引用传给方法。这样，变量a（方法外）和array（方法内）都指向在同一内存位置中的同一个数组。因此，在方法swapFirstTwoInArray内交换array[0]和array[1]和在方法外交换a[0]与a[1]是一样的。

7.7 方法返回数组

当方法返回一个数组时，数组的引用被返回

7.8 示例学习：统计每个字母出现的次数

本节给出一个程序，用于统计一个字符数组中每个字母出现的次数

程序清单 7-4 CountLettersInArray.java

import Based_On_Article.The_Textbook_Source_Code.Chapter06.RandomCharacter;
//上头导入的类是之前在第六章的程序清单6 - 10，前面的一串是我的package path
public class CountLettersInArray {
    /**
     * Main method
     */
    public static void main(String[] args) {
        //Declare and create an array
        char[] chars = createrArray();
        //Display the array
        System.out.println("The lowercase letters are: ");
        displayArray(chars);
        //Count the occurrences of each letter
        int[] counts = countLetters(chars);
        //Display counts
        System.out.println();
        System.out.println("The occurrences of each letter are: ");
        displayCounts(counts);
    }
    /**
     * Create an array of characters
     */
    public static char[] createrArray() {
        //Declare an array of characters and create it
        char[] chars = new char[100];
        //Create lowercase letters randomly and assign
        //them to the array
        for (int i = 0; i < chars.length; i++) {
            chars[i] = RandomCharacter.getRandomLowerCaseLetter();
        }
        //Return the array
        return chars;
    }
    /**
     * Display the array of characters
     */
    public static void displayArray(char[] chars) {
        //Display the characters in the array 20 on each line
        for (int i = 0; i < chars.length; i++) {
            if ((i + 1) % 20 == 0) {
                System.out.println(chars[i]);
            } else {
                System.out.print(chars[i] + " ");
            }
        }
    }
    /**
     * Count the occurrences of each letter
     */
    public static int[] countLetters(char[] chars) {
        //Declare and create an array of 26 int
        int[] counts = new int[26];
        //For each lowercase letter in the array , count it
        for (int i = 0; i < chars.length; i++) {
            counts[chars[i] - 'a']++;
        }
        return counts;
    }
    /**
     * Display counts
     */
    public static void displayCounts(int[] counts) {
        for (int i = 0; i < counts.length; i++) {
            if ((i + 1) % 10 == 0) {
                System.out.println(counts[i] + " " + (char) (i + 'a'));
            } else {
                System.out.print(counts[i] + " " + (char) (i + 'a') + " ");
            }
        }
    }
}

7.9 可变长参数列表

具有同样类型的数目可变的参数可以传递给方法，并将作为数组对待
可以把类型相同但数目可变的参数传递给方法。方法中的参数声明如下：
```
typeName ... parameterName(类型名 ... 参数名)
```

在方法声明中，指定类型后紧跟着省略号（…）。只能给方法指定一个可变长参数，同时该参数必须是最后一个参数。任何常规参数必须在它之前。
Java将可变长参数当成数组对待。可以将一个数组或数目可变的参数传递给可变长参数。当用数目可变的参数调用方法时，Java会创建一个数组并把参数传给它。程序清单7-5给出了打印出个数不定的列表中最大值的方法

程序清单 7-5 VarArgsDemo.java

public class VarArgsDemo {
    public static void main(String[] args) {
        printMax(34,3,3,2,56.5);
        printMax(new double[]{1,2,3});
    }
    public static void printMax(double... numbers) {
        if (numbers.length == 0) {
            System.out.println("No argument passed");
            return;
        }
        double result = numbers[0];
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] > result) {
                result = numbers[i];
            }
        }
        System.out.println("The max value is " + result);
    }
}

7.10 数组的查找

如果一个数组排好序了，对于查找数组中的一个元素，二分查找比线性查找更加高效
- 查找（searching）是在数组中寻找特定元素的过程，例如：判断某一特定分数是否包括在成绩列表中。查找是计算机程序设计中经常要完成的任务。有很多用于查找的算法和数据结构。本节讨论两种经常使用的方法：线性查找（linear searching）和二分查找（binary searching）。

7.10.1 线性查找法

线性查找法将要查找的关键字key与数组中的元素逐个进行比较。这个过程持续到在数组中找到与关键字匹配的元素，或者查完数组也没有找到关键字为止。如果匹配成功，线性查找法找到与关键字匹配的元素，或者查完数组也没有找到关键字为止。如果匹配成功，则返回 - 1。程序清单 7 - 6 中的 lineSearch 方法给出了解决方案：

程序清单 7-6 LinearSearch.java

public class LinearSearch {
    /**
     * The method for finding a key in the list
     */
    public static int linearSearch(int[] list, int key) {
        for (int i = 0; i < list.length; i++) {
            if (key == list[i]){
                return i;
            }
        }
        return -1;
    }
}

线性查找法把关键字和数组中的每一个元素进行比较。数组中的元素可以按任意顺序排列。平均而言，如果关键字存在，那么在找到关键字之前，这种算法必须与数组中一半的元素进行比较。由于线性查找法的执行时间随着数组元素个数的增长而线性增长，所以，对于大数组而言，线性查找法的效率并不高。

7.10.2 二分查找法

二分查找法是另一种常见的对数值列表的查找方法。使用二分查找法的前提条件是数组中的元素必须已经排好序。假设数组已按升序排列。二分查找法首先将关键字与数组的中间元素进行比较。考虑以下三种情况：
- 如果关键字小于中间元素，只需要在数组的前一半元素中继续查找关键字
- 如果关键字和中间元素相等，则匹配成功，查找结束
- 如果关键字大于中间元素，只需要在数组的后一半元素中继续查找关键字
显然，二分法在每次比较之后就排除掉一半的数组元素，有时候是去掉一半的元素，有时候是去掉一半加1个元素。假设数组有n个元素。为方便起见，假设n是2的幂。经过第1次比较，只剩下n/2个元素需要进一步查找；经过第2次比较，剩下（n / 2）/ 2 个元素需要进一步查找。经过k次比较之后，需要查找的元素就剩下 n / 2k 个。当k = log2 n 时，数组中只剩下1个元素，就只需要在比较1次。因此，在一个已经排序的数组中用二分查找法查找一个元素，即使是最坏的情况，也只需要log2 n + 1 次比较。对于一个有1024个元素的数组，在最坏的情况下，二分查找法只需要比较11次，而在最坏的情况下线性查找要比较1023次
每次比较后，数组要查找的部分就会缩小一半。用 low 和 high 分别表示当前查找的数组的第一个下标和最后一个下标。初始条件下，low为0，而high为 list.length - 1。让 mid 表示列表的中间元素的下标。这样，mid就是（low + high） / 2。图 7-9 显示怎样使用二分法从列表{2，4，7，10，11，45，50，59，60，66，69，70，79}中找出关键字11。
现在知道了二分查找法是如何工作的。下一个任务就是在Java中实现它。不要急于给出一个完整的实现，而是逐步地实现这个程序，一次一步。可以从查找的第一次迭代开始，如图7 - 10 a所示。它将关键字key和下标low为0、下标high为 list.length - 1的列表的中间元素进行比较。如果key < list[mid]，就将下标high设置为mid - 1；如果key == list[mid]，则匹配成功并返回 mid ；如果key > list[mid]，就将下标 low 设置为 mid + 1。
接下来就要考虑增加一个循环来实现这个方法，使其重复地完成查找，如图7-10b所示。如果找到这个关键字，或者当low > high时还没有找到这个关键字，就结束查找。
没有找到这个关键字时，low就是一个插入点，这个位置将插入关键字以保持列表的有序性。返回插入点位置比返回 -1 更加有用。这个方法必须返回一个负值，表明这个关键字不在该序列中。可以简单地返回 - low 吗？答案是：不可以。如果关键字小于 list [ 0 ]，那么 low 就是 0 ， - 0 也就是 0。这表明关键字匹配 list [ 0 ]。一个好的选择是，如果关键字不在该序列中，方法返回 - low - 1。返回 - low - 1不仅表明关键字不在序列中，而且还给出了关键字应该插入的地方。
完整的程序在程序清单 7-7 中给出。
程序清单 7-7 BinarySearch.java

public class BinarySearch {
    public static int binarySearch(int[] list, int key) {
        int low = 0;
        int high = list.length - 1;
        while (high >= low) {
            int mid = (low + high) / 2;
            if (key < list[mid]) {
                high = mid - 1;
            } else if (key == list[mid]) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
        //Now high < low , key not found
        return -low - 1;
    }
}

线性查找法适用于在较小数组或没有排序的数组中查找，但是对大数组而言效率不高。二分查找法的效率较高，但它要求数组已经拍好序。

7.11 数组的排序

如同查找一样，排序是计算机编程中非常普遍的一个任务。对于排序已经开发出很多不同的算法。本节介绍一个直观的排序算法：选择排序

程序清单 7-8 SelectionSort.java

public class SelectionSort {
    /**
     * The method for sorting the numbers
     */
    public static void selectionSort(double[] list) {
        for (int i = 0; i < list.length - 1; i++) {
            //Find the minimum in the list[i..list.length -1 ]
            double currentMin = list[i];
            int currentMinIndex = i;
            for (int j = 0; j < list.length; j++) {
                if (currentMin > list[j]) {
                    currentMin = list[j];
                    currentMinIndex = j;
                }
            }
            //Swap list[i] with list[currentMinIndex] if necessary
            if (currentMinIndex != i) {
                list[currentMinIndex] = list[i];
                list[i] = currentMin;
            }
        }
    }
}

7.12 Arrays类

java.util.Arrays类包含一些实用的方法用于常见的数组操作，比如排序和查找
java.util.Arrays类包括各种各样的静态方法，用于实现数组的排序和查找、数组的比较和填充数组元素，以及返回数组的字符串表示。这些方法都有对所有基本类型的重载方法。

可以使用 sort 或者parallelSort 方法对整个数组或部分数组进行排序。例如，下面的代码对数值型数组和字符型数组进行排序

double[] numebrs = {6.0, 4.4, 1.9, 2.9, 3.4, 3.5};
java.util.Arrays.sort(numbers); //Sort the whole array
java.util.Arrays.parallelSort(numbers); //Sort the whole array

可以调用sort(numbers)对整个数组numbers排序。可以调用sort(chars, 1, 3)对从chars [ 1 ] 到chars [ 3-1 ]的部分数组排序。如果你的计算机有多个处理器，那么parallelSort将更加高效。
可以采用二分查找法（binarySearch方法）在数组中查找关键字。数组必须提前按升序排好。如果数组中不存在关键字，方法返回 - (insertionIndex + 1) 。例如，下面的代码在整数数组和字符数组中查找关键字：

7.13 命令行参数

main方法可以从命令行接收字符串参数

7.13.1 向main方法传递字符串

如果运行程序时没有传递字符串，那么使用 new String[ 0 ]创建数组。在这种情况下，该数组是长度为 0 的空数组。args 是对这个空数组的引用。因此，args不是null，但是args.length 为 0 .

7.13.2 示例学习：计算器

程序清单 7-9 Calculator.java

public class Calculator {
    /**
     * Main method
     */
    public static void main(String[] args) {
        //Check number of strings passed
        if (args.length != 3) {
            System.out.println("Usage: java Calculator operand1 operator operand2");
            System.exit(1);
        }
        //The result of the operation
        int result = 0;
        //Determine the operator
        switch (args[1].charAt(0)) {
            case '+':
                result = Integer.parseInt(args[0]) + Integer.parseInt(args[2]);
                break;
            case '-':
                result = Integer.parseInt(args[0]) - Integer.parseInt(args[2]);
                break;
            case '*':
                result = Integer.parseInt(args[0]) * Integer.parseInt(args[2]);
                break;
            case '/':
                result = Integer.parseInt(args[0]) / Integer.parseInt(args[2]);
                break;
            default:
                System.out.println("Error!!!");
        }
        //Display result
        System.out.println(args[0] + ' ' + args[1] + ' ' + args[2] + " = " + result);
    }
}

第07章 一维数组