Arrays1、用法1.1、toString1.2、排序1.3、查找1.4、更多方法2、多维数组3、实现原理3.1、二分查找3.2、排序1、用法Arrays类中有很多方法主要介绍toString、排序、查找对于一些其他方法如复制、比较、批量设置值和计算哈希值等我们也进行简单介绍。1.1、toStringArrays的toString()方法可以方便地输出一个数组的字符串形式以便查看。它有9个重载的方法包括8个基本类型数组和1个对象类型数组下面列举两个publicstaticStringtoString(int[]a)publicstaticStringtoString(Object[]a)例如int[]arr{9,8,3,4};System.out.println(Arrays.toString(arr));String[]strArr{hello,world};System.out.println(Arrays.toString(strArr));输出为[9,8,3,4][hello,world]如果不使用Arrays.toString方法直接输出数组自身即代码改为int[]arr{9,8,3,4};System.out.println(arr);String[]strArr{hello,world};System.out.println(strArr);则输出会变为如下所示[I1224b90[Ljava.lang.String;728edb84这个输出就难以阅读了后面的数字表示的是内存的地址。1.2、排序排序是一种非常常见的操作。同toString一样对每种基本类型的数组Arrays都有sort方法boolean除外​例如publicstaticvoidsort(int[]a)publicstaticvoidsort(double[]a)排序按照从小到大升序排列例如int[]arr{4,9,3,6,10};Arrays.sort(arr);System.out.println(Arrays.toString(arr));输出为[Break,abc,hello,world]Break之所以排在最前面是因为大写字母的ASCII码比小写字母都小。那如果排序的时候希望忽略大小写呢sort还有另外两个重载方法可以接受一个比较器作为参数publicstaticTvoidsort(T[]a,Comparator?superTc)publicstaticTvoidsort(T[]a,intfromIndex,inttoIndex,Comparator?superTc)方法声明中的T表示泛型泛型我们在第8章介绍这里表示的是这个方法可以支持所有对象类型只要传递这个类型对应的比较器就可以了。Comparator就是比较器它是一个接口Java 7中的定义是publicinterfaceComparatorT{intcompare(To1,To2);booleanequals(Objectobj);}最主要的是compare这个方法它比较两个对象返回一个表示比较结果的值-1表示o1小于o2,0表示o1等于o2,1表示o1大于o2。排序是通过比较来实现的sort方法在排序的过程中需要对对象进行比较的时候就调用比较器的compare方法。Java 8中Comparator增加了多个静态和默认方法具体可参看API文档。String类有一个public静态成员表示忽略大小写的比较器publicstaticfinalComparatorStringCASE_INSENSITIVE_ORDERnewCaseInsensitiveComparator();我们通过这个比较器再来对上面的String数组排序String[]arr{hello,world,Break,abc};Arrays.sort(arr,String.CASE_INSENSITIVE_ORDER);System.out.println(Arrays.toString(arr));为进一步理解Comparator我们来看下String的这个比较器的主要实现代码如代码所示。privatestaticclassCaseInsensitiveComparatorimplementsComparatorString{publicintcompare(Strings1,Strings2){intn1s1.length();intn2s2.length();intminMath.min(n1,n2);for(inti0;imin;i){charc1s1.charAt(i);charc2s2.charAt(i);if(c1!c2){c1Character.toUpperCase(c1);c2Character.toUpperCase(c2);if(c1!c2){c1Character.toLowerCase(c1);c2Character.toLowerCase(c2);if(c1!c2){//No overflow because of numeric promotionreturnc1-c2;}}}}returnn1-n2;}}sort方法默认是从小到大排序如果希望按照从大到小排序呢对于对象类型可以指定一个不同的Comparator可以用匿名内部类来实现Comparator比如String[]arr{hello,world,Break,abc};Arrays.sort(arr,newComparatorString(){Overridepublicintcompare(Stringo1,Stringo2){returno2.compareToIgnoreCase(o1);}});System.out.println(Arrays.toString(arr));程序输出为[world, hello, Break, abc]以上代码使用一个匿名内部类实现Comparator接口返回o2与o1进行忽略大小写比较的结果这样就能实现忽略大小写且按从大到小排序。Collections类中有两个静态方法可以返回逆序的Comparator例如publicstaticTComparatorTreverseOrder()publicstaticTComparatorTreverseOrder(ComparatorTcmp)这样上面字符串忽略大小写逆序排序的代码可以改为String[]arr{hello,world,Break,abc};Arrays.sort(arr,Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));System.out.println(Arrays.toString(arr));传递比较器Comparator给sort方法体现了程序设计中一种重要的思维方式。将不变和变化相分离排序的基本步骤和算法是不变的但按什么排序是变化的sort方法将不变的算法设计为主体逻辑而将变化的排序方式设计为参数允许调用者动态指定这也是一种常见的设计模式称为策略模式不同的排序方式就是不同的策略。1.3、查找Arrays包含很多与sort对应的查找方法可以在已排序的数组中进行二分查找。所谓二分查找就是从中间开始查找如果小于中间元素则在前半部分查找否则在后半部分查找每比较一次要么找到要么将查找范围缩小一半所以查找效率非常高。二分查找既可以针对基本类型数组也可以针对对象数组对对象数组也可以传递Comparator也可以指定查找范围。比如针对int数组publicstaticintbinarySearch(int[]a,intkey)publicstaticintbinarySearch(int[]a,intfromIndex,inttoIndex,intkey)针对对象数组publicstaticintbinarySearch(Object[]a,Objectkey)指定自定义比较器publicstaticTintbinarySearch(T[]a,Tkey,Comparator?superTc)如果能找到binarySearch返回找到的元素索引比如int[]arr{3,5,7,13,21};System.out.println(Arrays.binarySearch(arr,13));输出为3。如果没找到返回一个负数这个负数等于-插入点1​。插入点表示如果在这个位置插入没找到的元素可以保持原数组有序比如int[]arr{3,5,7,13,21};System.out.println(Arrays.binarySearch(arr,11));输出为-4表示插入点为3如果在3这个索引位置处插入11可以保持数组有序即数组会变为{3,5,7,11,13,21}。需要注意的是binarySearch针对的必须是已排序数组如果指定了Comparator需要和排序时指定的Comparator保持一致。另外如果数组中有多个匹配的元素则返回哪一个是不确定的。1.4、更多方法除了常用的toString、排序和查找Arrays中还有复制、比较、批量设置值和计算哈希值等方法。基于原数组复制一个新数组与toString一样也有多种重载形式例如publicstaticlong[]copyOf(long[]original,intnewLength)publicstaticTT[]copyOf(T[]original,intnewLength)判断两个数组是否相同支持基本类型和对象类型如下所示publicstaticbooleanequals(boolean[]a,boolean[]a2)publicstaticbooleanequals(Object[]a,Object[]a2)只有数组长度相同且每个元素都相同才返回true否则返回false。对于对象相同是指equals返回true。Arrays包含很多fill方法可以给数组中的每个元素设置一个相同的值publicstaticvoidfill(int[]a,intval)也可以给数组中一个给定范围的每个元素设置一个相同的值publicstaticvoidfill(int[]a,intfromIndex,inttoIndex,intval)针对数组计算一个数组的哈希值publicstaticinthashCode(inta[])计算hashCode的算法和String是类似的我们看下代码publicstaticinthashCode(inta[]){if(anull)return0;intresult1;for(intelement:a)result31 resultelement;returnresult;}回顾一下String计算hashCode的算法也是类似的数组中的每个元素都影响hash值位置不同影响也不同使用31一方面产生的哈希值更分散另一方面计算效率也比较高。Java 8和9对Arrays类又增加了一些方法比如将数组转换为流、并行排序、数组比较等。2、多维数组之前介绍的数组都是一维的数组还可以是多维的。先来看二维数组比如int[][]arrnewint[2][3];for(inti0;iarr.length;i){for(intj0;jarr[i].length;j){arr[i][j]ij;}}arr就是一个二维数组第一维长度为2第二维长度为3类似于一个矩阵或者类似于一个表格第一维表示行第二维表示列。arr[i]表示第i行它本身还是一个数组 arr[i]​[j]表示第i行中的第j个元素。除了二维数组还可以是三维、四维等但一般而言很少用到三维以上的数组有几维就有几个[​]​。比如一个三维数组的声明为int[][][]arrnewint[10][10][10];在创建数组时除了第一维的长度需要指定外其他维的长度不需要指定甚至第一维中每个元素的第二维的长度可以不一样看个例子int[][]arrnewint[2][];arr[0]newint[3];arr[1]newint[5];arr是一个二维数组第一维的长度为2第一个元素的第二维长度为3而第二个元素的第二维长度为5。多维数组到底是什么呢其实可以认为多维数组只是一个假象只有一维数组只是数组中的每个元素还可以是一个数组这样就形成二维数组如果其中每个元素还都是一个数组那就是三维数组。Arrays中的toString、equals、hashCode都有对应的针对多维数组的方法publicstaticStringdeepToString(Object[]a)publicstaticbooleandeepEquals(Object[]a1,Object[]a2)publicstaticintdeepHashCode(Objecta[])这些deepⅩⅩⅩ方法都会判断参数中的元素是否也为数组如果是会递归进行操作。int[][]arrnewint[][]{{0,1},{2,3,4},{5,6,7,8}};System.out.println(Arrays.deepToString(arr));输出为[[0, 1], [2, 3, 4], [5, 6, 7, 8]]3、实现原理3.1、二分查找二分查找binarySearch的代码比较直接如代码所示。privatestaticTintbinarySearch0(T[]a,intfromIndex,inttoIndex,Tkey,Comparator?superTc){intlowfromIndex;inthightoIndex-1;while(lowhigh){intmid(lowhigh)1;TmidVala[mid];intcmpc.compare(midVal,key);if(cmp0)lowmid1;elseif(cmp0)highmid-1;elsereturnmid;//key found}return-(low1);//key not found}上述代码中有两个标志low和high表示查找范围在while循环中与中间值进行对比大于则在后半部分查找提高low​否则在前半部分查找降低high​。3.2、排序与Arrays中的其他方法相比sort要复杂得多。排序是计算机程序中一个非常重要的方面几十年来计算机科学家和工程师们对此进行了大量的研究设计实现了各种各样的算法进行了大量的优化。一般而言没有一个最好的算法不同算法往往有不同的适用场合。对于基本类型的数组Java采用的算法是双枢轴快速排序Dual-Pivot Quicksort​。这个算法是Java 7引入的在此之前Java采用的算法是普通的快速排序。双枢轴快速排序是对快速排序的优化新算法的实现代码位于类java.util.DualPivotQuicksort中。在这些排序算法中如果数组长度比较小它们还会采用效率更高的插入排序。为什么基本类型和对象类型的算法不一样呢排序算法有一个稳定性的概念所谓稳定性就是对值相同的元素如果排序前和排序后算法可以保证它们的相对顺序不变那算法就是稳定的否则就是不稳定的。快速排序更快但不稳定而归并排序是稳定的。对于基本类型值相同就是完全相同所以稳定不稳定没有关系。但对于对象类型相同只是比较结果一样它们还是不同的对象其他实例变量也不见得一样稳定不稳定可能就很有关系了所以采用归并排序。