0%

Java 常用基础类（四）：剖析 Arrays

发表于 更新于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

1. Arrays 类是干嘛的

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

2. 怎样理解 Arrays 的 toString() 方法

  • Arrays 的 toString() 方法可以方便地输出一个数组的字符串形式

3. 怎样理解 Arrays 的 sort() 方法

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

4. Comparator 是干嘛的

  • Comparator 的名字叫比较器，实际上就是一个接口

  • Java 7 中 Comparator 的定义是

    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 8 中 Comparator 增加了多个静态方法和默认方法（同接口）

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

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

6. 怎样理解 Arrays 的 binarySearch() 方法

  • 二分查找效率很高。二分查找既可以针对基本数据类型数组，也可以针对对象数组
  • 如果能找到，那么 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
}

10. 怎样理解 Arrays 的 sort() 排序方法

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

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

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

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

13. 十大经典排序算法总结

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