资源描述
第6章 一维数组 开放问题读取一百数字，计算它们的平均值，然后找出有多少个数大于平均值。 解决方案 Run 学习目标F描述数组在程序设计中的必要性 （第6.1节）。F声明数组引用变量、创建数组 （第6.2.1-6.2.2节）。F初始化数组中的值 （第6.2.3节）。F使用下标变量访问数组元素（第6.2.4节）。F利用一条数组初始化语法声明、创建和初始化数组 （第6.2.5节）。F编写程序实现常用的数组操作（显示数组、对所有元素求和、求最大和最小元素、随意打乱、移动元素）（第6.2.6节 ）。F使用for - each循环简化程序设计（第6.2.7）。F在LottoNumbers和DeckOfCards问题中应用数组 （第6.3-6.4节）。F将一个数组的内容复制到另一个数组 （第6.5节）。 F开发和调用带数组参数和返回值的方法（第6.66.7节）。F定义带变长参数列表的方法（第6.8节）。F使用线性查找算法（第6 .9.1节）或二分查找算法（第6. 9.2节）查找数组的元素。F使用选择排序法对数组排序（第6.10.1节）。F使用插入排序算法使排序数组 （第6.10.2节）。F使用 Arrays 类中的方法（第6.11节）。 介绍数组数组是一种数据结构，它表示一组相同类型的数据。 5.6 4.5 3.3 13.2 4 34.33 34 45.45 99.993 11123 double myList = new double10; myList reference myList0 myList1 myList2 myList3 myList4 myList5 myList6 myList7 myList8 myList9 元素值 数组引用变量 下标5处的 数组元素 声明数组变量Fdatatype arrayRefVar;举例： double myList;Fdatatype arrayRefVar; / 这种风格是允许的,但不推荐使用举例： double myList; 创建数组arrayRefVar = new datatypearraySize;举例：myList = new double10;myList0 引用数组中的第一个元素。myList9 引用数组中的最后一个元素。 一步完成声明和创建Fdatatype arrayRefVar = new datatypearraySize; double myList = new double10;Fdatatype arrayRefVar = new datatypearraySize;double myList = new double10; 数组的大小一旦数组被创建就不能再修改它的大小。可以通过使用arrayRefVar.length来求得数组的大小。举例：myList.length returns 10 默认值当数组被创建后，它的元素被赋予默认值 数值型基本数据类型的默认值是0， char 类型的默认值为u0000 ，而 boolean 类型默认值为false。 下标变量数组元素可以通过下标来访问。数组下标是基于0的，就是说它从0开始到arrayRefVar.length-1结束。在图6.1中的例子中, 数组myList 包含10个double值而下标是从0到9。数组中的每个元素都可以使用下面一般被称为下标变量的语法表示：arrayRefVarindex; 使用下标变量创建数组后，可以采用和一般变量相同的方法使用下标变量。例如：下面的代码是将myList0和myList1的值相加赋给myList2。myList2 = myList0 + myList1; 数组初始化语法F一步完成数组的声明、创建、初始化:double myList = 1.9, 2.9, 3.4, 3.5;这种缩略语法必须用在一条语句中。 使用缩略符号声明、创建、初始化数组double myList = 1.9, 2.9, 3.4, 3.5;这里的缩略符号相当于以下面的语句：double myList = new double4;myList0 = 1.9;myList1 = 2.9;myList2 = 3.4;myList3 = 3.5; 注意 使用缩略符号时，你必须将声明、创建和初始化数组都放在一条语句中。将它们分开会引起语法错误。例如：下面的语句就是错误的:double myList;myList = 1.9, 2.9, 3.4, 3.5; 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 声明数组变量value，创建一个数组并将它的引用赋值给values动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i 变为 1动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i （=1）小于5动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 这一行被执行后，values1是1 After the first iteration 0 1 2 3 4 0 1 0 0 0 动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i+后，i 变为 2动 画 After the first iteration 0 1 2 3 4 0 1 0 0 0 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i（= 2）小于5动 画 After the first iteration 0 1 2 3 4 0 1 0 0 0 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 这一行被执行之后，values2 为3（2 + 1） After the second iteration 0 1 2 3 4 0 1 3 0 0 动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 这之后，i就 变为 3. After the second iteration 0 1 2 3 4 0 1 3 0 0 动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i（=3）依旧小于5 After the second iteration 0 1 2 3 4 0 1 3 0 0 动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 这一行之后，values3变成 6（3 + 3） After the third iteration 0 1 2 3 4 0 1 3 6 0 动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 这之后，i变成4 After the third iteration 0 1 2 3 4 0 1 3 6 0 动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i（=4） 仍旧小于5 After the third iteration 0 1 2 3 4 0 1 3 6 0 动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 这之后，values4变成 10（4 + 6） After the fourth iteration 0 1 2 3 4 0 1 3 6 10 动 画 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i+后，i 变成5动 画 After the fourth iteration 0 1 2 3 4 0 1 3 6 10 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i ( =5） 5 为假。退出循环动 画 After the fourth iteration 0 1 2 3 4 0 1 3 6 10 跟踪数组程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 这行之后，values0 为11 (1 + 10） 0 1 2 3 4 11 1 3 6 10 动 画 处理数组下面是一些示例：F（使用输入值初始化数组）F（使用随机数初始化数组）F（打印数组）F（对所有元素求和）F（找出最大元素）F（找出最大元素的最小下标值） F（随意打乱） 1.（移动元素） 使用输入值初始化数组java.util.Scanner input = new java.util.Scanner(System.in);System.out.print(Enter + myList.length + values: );for (int i = 0; i myList.length; i+) myListi = input.nextDouble(); 使用随机数初始化数组for (int i = 0; i myList.length; i+) myListi = Math.random() * 100; 打印数组for (int i = 0; i myList.length; i+) System.out.print(myListi + ); 对所有元素求和double total = 0;for (int i = 0; i myList.length; i+) total += myListi; 找出最大的元素double max = myList0;for (int i = 1; i max) max = myListi; 随意打乱 for (int i = 0; i myList.length; i+) / Generate an index j randomly int index = (int)(Math.random() * myList.length); / Swap myListi with myListj double temp = myListi; myListi = myListindex; myListindex = temp; myList 0 1 . . . index A random index i swap 移动元素 double temp = myList0; / Retain the first element / Shift elements left for (int i = 1; i myList.length; i+) myListi - 1 = myListi; / Move the first element to fill in the last position myListmyList.length - 1 = temp; myList 增强型for循环（for - each循环）JDK 1.5引入了一个新的for循环，它可以让你不使用下标变量就可以顺序地遍历整个数组。 例如：下面的代码显示数组myList中的所有元素： for (double value: myList) System.out.println(value); 一般来讲，这个语法是 for (elementType value: arrayRefVar) / Process the value 当需要以其它顺序遍历该数组或改变数组中的元素时，你还是必须使用下标变量。 问题：乐透号码假设你要玩选10乐透游戏，每张筹码有10个范围从1到99的独特的数字。假设你买了一堆筹码，希望它们涵盖1到99的所有数字。编写一个程序，从一个文件中读取筹码上的数字，并检查是否涵盖所有的数字。 假设这个文件的最后一个数字是0。 问题：一副牌编写一个程序，它随机地从一副52张牌中选择4张。所有的牌可以使用一个名为deck的数组表示，这个数组用从0到51的初始值来填充，如下所示：int deck = new int52;/ Initialize cardsfor (int i = 0; i deck.length; i+) decki = i; 问题：一副牌（续） 0 . . . 12 13 . . . 25 26 . . . 38 39 . . . 51 13 Spades (?) 13 Hearts (?) 13 Diamonds (?) 13 Clubs (?) 0 . . . 12 13 . . . 25 26 . . . 38 39 . . . 51 deck 0 . . . 12 13 . . . 25 26 . . . 38 39 . . . 51 Random shuffle 6 48 11 24 . . . . . . . . . . . . . . . . deck 0 1 2 3 4 5 . . . 25 26 . . . 38 39 . . . 51 Card number 6 is 7 of Spades Card number 48 is 10 of Clubs Card number 11 is Queen of Spades Card number 24 is Queen of Hearts 问题:一副牌这个问题为今后构建一个更有趣和更具现实意义的应用程序打一个基础：参见练习题25.9。 复制数组在程序中，你经常需要复制一个数组或数组的一部分。在这种情况下，你可能会尝试使用赋值语句（=），如下所示： list2 = list1; list1 的内容 list1 list2 的内容 list2 赋值语句 list2 = list1;之前 list1 的内容 list1 list2 的内容 list2 赋值语句 list2 = list1;之后 Garbage 复制数组使用循环：int sourceArray = 2, 3, 1, 5, 10;int targetArray = new intsourceArray.length;for (int i = 0; i sourceArrays.length; i+) targetArrayi = sourceArrayi; arraycopy工具arraycopy(sourceArray, src_pos, targetArray, tar_pos, length);例如：System.arraycopy(sourceArray, 0, targetArray, 0, sourceArray.length); 传递数组给方法public static void printArray(int array) for (int i = 0; i array.length; i+) System.out.print(arrayi + ); Invoke the methodint list = 3, 1, 2, 6, 4, 2;printArray(list);Invoke the method printArray(new int3, 1, 2, 6, 4, 2);匿名数组 匿名数组语句printArray(new int3, 1, 2, 6, 4, 2); 使用下面的语法创建一个数组：new dataTypeliteral0, literal1, ., literalk;这里没有数组的显式引用变量。这样的数组被称为匿名数组。 值传递Java使用值传递的方法传递实参给方法。传递基本数据类型变量的值与传递数组值会有很大不同。F 对于基本数据类型参数，传递的是实参的值。在方法中改变局部参数的值并不影响方法之外变量的值。F 对于数组类型参数，参数值是数组的引用，传递给方法的是这个引用。方法体中数组发生的改变，将会影响到作为参数传给方法的原始数组。 public class Test public static void main(String args) int x = 1; / x represents an int value int y = new int10; / 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(y0 is + y0); public static void m(int number, int numbers) number = 1001; / Assign a new value to number numbers0 = 5555; / Assign a new value to numbers0 简单的例子 调用栈 当调用m(x,y)时，x和y的值被传递给 number 和 numbers。因为y包含的是数组的引用值，所以，numbers现在包含的是指向同一数组的相同引用值。 Space required for the main method int y: int x: 1 栈 Space required for method m int numbers: int number: 1 reference 0 0 0 The arrays are stored in a heap. 堆 reference Array of ten int values is 调用栈当调用m(x,y)时，x和y的值被传递给 number 和 numbers。因为y包含的是数组的引用值，所以，numbers现在包含的是指向同一数组的相同引用值。 Space required for the main method int y: int x: 1 Stack Space required for method m int numbers: int number: 1001 reference 5555 0 0 The arrays are stored in a heap. Heap reference Array of ten int values is stored here 堆 Space required for the main method int y: int x: 1 reference The arrays are stored in a heap. Heap 5555 0 0 JVM将数组存储在一个被称作堆的内存区域，堆是用来动态分配内存的，在堆中的内存块可以按任意顺序分配和释放。 传递数组参数F目标：演示传递基本数据类型变量和传递数组变量的不同之处。 举例（续） Invoke swap(int n1, int n2). The primitive type values in a0 and a1 are passed to the swap method. Space required for the main method int a Stack Space required for the swap method n2: 2 n1: 1 reference a1: 2 a0: 1 The arrays are stored in a heap. Invoke swapFirstTwoInArray(int array). The reference value in a is passed to the swapFirstTwoInArray method. Heap Space required for the main method int a Stack Space required for the swapFirstTwoInArray method int array reference reference 从方法中返回数组public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 跟踪reverse方法public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = 1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 0声明result 并创建数组 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 0 i = 0 而 j = 5 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 0 i (= 0) 小于6 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 1 i = 0 而 j = 5 将list0赋值给result5 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 1这之后，i 变为1 而 j 变为 4 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 1 i（=1）小于6 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 2 1 i = 1 而 j = 4 将list1赋值给给 result4 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 2 1这之后，i 变成2 而 j 变为 3 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 2 1 i (=2) 依旧小于6 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 3 2 1 i = 2 而 j = 3 将listi赋值给 resultj 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 3 2 1这之后，i 变成 3 而 j 变成 2 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 3 2 1 i（=3）依旧小于6 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 4 3 2 1 i = 3 而 j = 2 将listi赋值给 resultj 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 4 3 2 1这之后，i 变成 4 而 j 变成 1 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 4 3 2 1 i（=4）依旧小于6 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 5 4 3 2 1 i = 4 而 j = 1 将listi赋值给 resultj 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 5 4 3 2 1这之后，i变成5 而 j 变成 0 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 5 4 3 2 1 i (=5) 依旧小于6 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 66 5 4 3 2 1 i = 5 而 j = 0 将listi赋值给resultj 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 66 5 4 3 2 1这之后， i 变成 6 而j 变成 -1 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 66 5 4 3 2 1 i（=6） 6 为假，所以退出循环 动 画 跟踪reverse方法（续）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 66 5 4 3 2 1返回 resultlist2 动 画 问题：统计每个字母出现的次数F随机生成100个小写字母，将它们赋值给一个字符数组。F统计数组中的每个字母的出现计数。 (a) Executing createArray in Line 6 Space required for the main method char chars: ref Heap Array of 100 characters Space required for the createArray method char chars: ref (b) After exiting createArray in Line 6 Space required for the main method char chars: ref Heap Array of 100 characters Stack Stack 数组的搜索 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 = listi) return i; return -1; list key 将key 和 listi for i = 0, 1, 进行比较 0 1 2 搜索就是在数组中寻找特定元素的过程；例如：判断某一特定分数是否包含在成绩列表中。搜索是计算机程序设计中一种经常要完成的任务。有许多关于搜索的算法和数据结构。在本节中，讨论两种常用的方法：线性查找法和二分查找法。 线性查找法线性查找法就是将要查找的关键元素key顺序地与数组list中的每一个元素进行比较。这个方法一直继续直到在列表中找到与关键字匹配的元素，还有一种情况就是忙乎了半天，在list中也没找到匹配的元素。如果匹配成功，线性查找法返回与数组中与关键字匹配的元素的下标。 如果匹配不成功，则返回 -1。 线性查找法的动画6 4 1 9 7 3 2 86 4 1 9 7 3 2 86 4 1 9 7 3 2 86 4 1 9 7 3 2 86 4 1 9 7 3 2 86 4 1 9 7 3 2 83333 33 动 画Key List 从想法到解决方案/* 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 = listi) return i; return -1;int list = 1, 4, 4, 2, 5, -3, 6, 2; int i = linearSearch(list, 4); / returns 1int j = linearSearch(list, -4); / returns -1int k = linearSearch(list, -3); / returns 5跟踪这个方法 二分查找法使用二分查找法的前提是数组中的元素必须已经被排好序。为不时一般性，假设数组以升序排序。例如： 2 4 7 10 11 45 50 59 60 66 69 70 79二分查找法首先将关键字key与数组中间的元素进行比较。 二分查找法（续）F如果关键字key小于中间元素，你只需要在数组的前半部分的元素中继续查找关键字。F如果关键字key等于中间元素，这个查找结束。F如果关键字key大于中间元素，你只需要在数组的后半部分的元素中继续查找关键字。考虑下面三种情况： 二分查找法1 2 3 4 6 7 8 91 2 3 4 6 7 8 91 2 3 4 6 7 8 9888Key List动 画 二分查找法（续） 0 1 2 3 4 5 6 7 8 9 10 11 12 2 4 7 10 11 45 50 59 60 66 69 70 79 key 是 11 key 7 key = 11 high low mid high low list 3 4 5 mid high low list 2 4 7 10 11 45 10 11 45 Binary Search, cont. 0 1 2 3 4 5 6 7 8 9 10 11 12 2 4 7 10 11 45 50 59 60 66 69 70 79 key 是 54 key 50 list mid 0 1 2 3 4 5 6 7 8 9 10 11 12 key 66 key = low) int mid = (low + high) / 2; if (key listmid) high = mid - 1; else if (key = listmid) return mid; else low = mid + 1; return -1 - low; 方法Arrays.binarySearch由于二分查找法经常在程序设计中用到，所以Java在类java.util.Arrays提供了方法binarySearch的几个重载方法，它们可以在由 int、double、char、short、long,和 float 构成数组中搜索关键字。例如：下面的代码在包含数字的数组和包含字符的数组中查找关键字。int list = 2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79;System.out.println(Index is + java.util.Arrays.binarySearch(list, 11); char chars = a, c, g, x, y, z;System.out.println(Index is + java.util.Arrays.binarySearch(chars, t); 为使binarySearch正常运转，必须使数组按升序排列。 返回 4返回 4 （返回点是3，所以返回 -3-1) 数组的排序像查找一样，排序在计算机程序设计中也是一个常用任务。已经开发出许多不同的排序算法。 本节将介绍两种简单的、直观的排序算法：选择排序法和插入排序法。 选择排序就是找到数列中的最小数并将它放在最前面。 然后找到剩余数中最小的并将它放到最前面第二位，直到数列中只包含一个数字。 图6.17显示如何使用选择排序法对队列 2、9、5、4、8、1、6 进行排序。选择排序法 2 9 5 4 8 1 6 swap Select 1 (the smallest) and swap it with 2 (the first) in the list 1 9 5 4 8 2 6 swap The number 1 is now in the correct position and thus no longer needs to be considered. 1 2 5 4 8 9 6 swap 1 2 4 5 8 9 6 Select 2 (the smallest) and swap it with 9 (the first) in
展开阅读全文