Java 常用基础类(四):剖析 Arrays

1. Arrays 类是干嘛的?

答:

  • Arrays 类包含一些对数组操作的静态方法
  • Java 8Java 9Arrays 类又增加了一些方法,比如将数组转换为流,并行排序、数组比较等。

2. 怎样理解 ArraystoString() 方法?

答:ArraystoString() 方法可以方便地输出一个数组的字符串形式,以便查看。

3. 怎样理解 Arrayssort() 方法?

答:

  • 对每种基本类型的数组,Arrays 都有 sort() 方法(boolean 除外),默认升序排列。
  • 除了基本类型,sort() 方法还可以直接接受对象类型,但对象需要实现 Comparable 接口
  • 大写字母的 ASCII 码比小写字母都小

4. Comparator 是干嘛的?

答:

  • Comparator 的名字叫比较器实际上就是一个接口
  • Java 7Comparator 的定义是:

    public interface Comparator<T>  {
        int compare(T o1, T o2);
        boolean equals(Object obj);
    }
    
  • 最主要的是 compare() 这个方法,它比较两个对象,返回一个表示比较结果的值。-1 表示 o1 小于 o20 表示 o1 等于 o21 表示 o1 大于 o2

  • Java 8Comparator 增加了多个静态方法和默认方法

5. 怎样理解策略模式这种设计模式?

答:

  • 传递比较器 Comparatorsort() 方法,体现了程序设计中一种很重要的思维方式:将不变和变化相分离
  • 排序的基本步骤和算法是不变的,但按什么排序是变化的,sort() 方法将不变的算法设计为主体逻辑,而将变化的排序方式设计为参数,允许调用者动态指定,这种设计模式就是策略模式。不同的排序方式就是不同的策略

6. 怎样理解 ArraysbinarySearch() 方法?

答:

  • 二分查找效率很高
  • 二分查找既可以针对基本类型数组,也可以针对对象数组
  • 如果能找到,那么 binarySearch() 返回找到的元素索引;如果没有找到,返回一个负数,这个负数等于-(插入点 + 1)插入点表示,如果在这个位置插入没找到的元素,则可以保持原数组有序
  • binarySearch() 针对的必须是已排序数组,如果指定了 Comparator,需要和排序时指定的 Comparator 保持一致
  • 如果数组中有多个匹配的元素,则返回哪一个是不确定的

7. 怎样理解多维数组?

答:

  • 二维数组类似于一个矩阵或者一个表格arr[i][j] 表示第 i 行中的第 j 个元素。
  • 数组还可以是三维、四维等,一般很少用到,有几维就有几个[]
  • 在创建多维数组时,除了第一维的长度需要指定外,其他维的长度不需要指定,甚至第一维中每个元素的第二维的长度可以不一样

8. 多维数组到底是什么呢?

答:

  • 可以认为,多维数组只是一个假象,只有一维数组,只是数组中的每个元素还可以是一个数组。
  • 类似于高中时学过的立体几何

9. 【笔试题】请写出 Arrays 的二分查找 binarySearch() 代码实现?

答:

private static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c) {

    int low = fromIndex;
    int high = toIndex - 1;

    while(low <= high) {
        int mid = (low + high) >>> 1;
        T midVal = a[mid];
        int cmp = c.compare(midVal, key);
        if(com < 0) {
            low = mid + 1;
        } else if(cmp > 0) {
            high = mid - 1;
        } else {
            return mid; // key found
        }

    }
    return -(low + 1); // key not found
}

10. 怎样理解 Arrayssort() 排序方法?

答:

  • Arrays 中的其他方法相比,sort() 方法具体实现非常复杂
  • 一般而言,没有一个最好的算法,不同算法往往有不同的使用场合
  • 对于基本类型的数组,Java 采用的算法是双枢轴快速排序(Dual-Pivot Quicksort)。这个算法是 Java 7 引入的,在此之前,Java 采用的算法是普通的快速排序。双枢轴快速排序是对快速排序的优化,新算法的实现代码位于类 java.util.DualPivotQuicksort
  • 对于对象类型,Java 采用的算法是 TimSortTimSort 也是在 Java 7 引入的,在此之前,Java 采用的是归并排序。TimSort 实际上是对归并排序的一系列优化,TimSort 的实现代码位于类 java.util.TimSort
  • 在这些排序算法中,如果数组长度比较小,它们还会采用效率更高的插入排序

11. 为什么基本类型和对象类型的算法不一样?怎样理解排序算法里的稳定性概念?

答:

  • 排序算法有一个稳定性概念
  • 稳定性:对值相同的元素,如果排序前和排序后,算法可以保证它们的相对顺序不变,那算法就是稳定的,否则就是不稳定的
  • 快速排序更快,但不稳定;归并排序是稳定的
  • 对于基本类型,值相同就是完全相同,所以稳定不稳定没有关系;但对于对象类型,相同只是比较结果一样,它们还是不同的对象,其他实例变量也不见得一样,这时候稳定不稳定就很有关系了,所以采用归并排序

12. ArraysbinarySearch() 只能针对已排序数组进行查找,那没有排序的数组怎么方便查找呢?

答:Apache 有一个开源包(http://commons.apache.org/proper/commons-lang/),里面有一个类 ArrayUtils(位于包 org.apache.commons.lang3),包含了更多的常用数组操作。

-------------本文结束感谢您的阅读-------------