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

  1. Arrays 类是干嘛的?
    答:

    • Arrays 类包含一些对数组操作的静态方法
    • Java 8Java 9Arrays 类又增加了一些方法,比如将数组转换为流,并行排序、数组比较等。
  2. 怎样理解 ArraystoString() 方法?
    答:ArraystoString() 方法可以方便地输出一个数组的字符串形式,以便查看。

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

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

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

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

    • Java 8Comparator 增加了多个静态方法和默认方法
  5. 怎样理解策略模式这种设计模式?
    答:

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

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

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

    • 可以认为,多维数组只是一个假象,只有一维数组,只是数组中的每个元素还可以是一个数组。
    • 类似于高中时学过的立体几何
  9. 【笔试题】请写出 Arrays 的二分查找 binarySearch() 代码实现?
    答:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    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
    }
  1. 怎样理解 Arrayssort() 排序方法?
    答:

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

    • 排序算法有一个稳定性概念
    • 稳定性:对值相同的元素,如果排序前和排序后,算法可以保证它们的相对顺序不变,那算法就是稳定的,否则就是不稳定的
    • 快速排序更快,但不稳定;归并排序是稳定的
    • 对于基本类型,值相同就是完全相同,所以稳定不稳定没有关系;但对于对象类型,相同只是比较结果一样,它们还是不同的对象,其他实例变量也不见得一样,这时候稳定不稳定就很有关系了,所以采用归并排序
  3. ArraysbinarySearch() 只能针对已排序数组进行查找,那没有排序的数组怎么方便查找呢?
    答:Apache 有一个开源包(http://commons.apache.org/proper/commons-lang/),里面有一个类 ArrayUtils(位于包 org.apache.commons.lang3),包含了更多的常用数组操作。