Trail: Collections

课程：算法

这里描述的 polymorphic algorithms (多态算法) 是 Java 平台提供的可重用功能。所有这些都来自 Collections 类，并且都采用静态方法的形式，其第一个参数是要在其上执行操作的集合。Java 平台提供的绝大多数算法都在 List 实例上运行，但其中一些算法运行在任意 Collection 实例。本节简要介绍以下算法：

排序
洗牌
常规数据操作
搜索
组成
求极值

排序

sort 算法重新排序 List，以便其元素按照排序关系按升序排列。提供了两种形式的操作。简单形式采用 List 并根据其元素的 natural ordering (自然排序) 对其进行排序。如果你不熟悉自然排序的概念，请阅读 Object Ordering 部分。

sort 操作使用快速且稳定的略微优化的 merge sort (合并排序) 算法：

快：保证在 n log(n) 时间内运行，并且在近乎排序的列表上运行得更快。经验测试显示它与高度优化的快速排序一样快。快速排序通常被认为比合并排序更快但不稳定并且不保证 n log(n) 性能。
稳定：它不会重新排序相等的元素。如果在不同的属性上，重复对同一列表进行排序，这一点很重要。如果邮件程序的用户通过邮寄日期对收件箱进行排序，然后由发件人对其进行排序，则用户自然希望来自给定发件人的现在连续的邮件列表(仍然)将按邮寄日期排序。仅当第二个排序稳定时才能保证这一点。

以下 trivial program 以词典(按字母顺序)顺序打印出其参数。


import java.util.*;

public class Sort {
    public static void main(String[] args) {
        List<String> list = Arrays.asList(args);
        Collections.sort(list);
        System.out.println(list);
    }
}

我们来运行该程序。

% java Sort i walk the line

生成以下输出。

[i, line, the, walk]

该程序仅用于向你展示算法确实像它们看起来一样容易使用。

sort 的第二种形式采用除 List 之外的 Comparator，并使用 Comparator 排序元素。假设你想要以相反的大小顺序打印出前面示例中的 anagram 组最大的 anagram 组在前。下面的示例向你展示了如何借助 sort 方法的第二种形式实现此目的。

回想一下，anagram 组作为值存储在 Map 中，格式为 List 实例。修改后的打印代码遍历 Map 的值视图，将通过最小尺寸测试的每个 List 放入保存 List 的 List 中。然后代码使用需要 List 实例的 Comparator 对此 List 进行排序，并实现反向大小排序。最后，代码遍历排序的 List，打印其元素(anagram 组)。以下代码替换 Anagrams 示例中 main 方法末尾的打印代码。

// Make a List of all anagram groups above size threshold.
List<List<String>> winners = new ArrayList<List<String>>();
for (List<String> l : m.values())
    if (l.size() >= minGroupSize)
        winners.add(l);

// Sort anagram groups according to size
Collections.sort(winners, new Comparator<List<String>>() {
    public int compare(List<String> o1, List<String> o2) {
        return o2.size() - o1.size();
    }});

// Print anagram groups.
for (List<String> l : winners)
    System.out.println(l.size() + ": " + l);

在与 The Map Interface 部分中的 相同目录 上运行 该程序，使用相同的最小 anagram 组大小(8)，产生以下输出。


12: [apers, apres, asper, pares, parse, pears, prase,
       presa, rapes, reaps, spare, spear]
11: [alerts, alters, artels, estral, laster, ratels,
       salter, slater, staler, stelar, talers]
10: [least, setal, slate, stale, steal, stela, taels,
       tales, teals, tesla]
9: [estrin, inerts, insert, inters, niters, nitres,
       sinter, triens, trines]
9: [capers, crapes, escarp, pacers, parsec, recaps,
       scrape, secpar, spacer]
9: [palest, palets, pastel, petals, plates, pleats,
       septal, staple, tepals]
9: [anestri, antsier, nastier, ratines, retains, retinas,
       retsina, stainer, stearin]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares,
       sparse, spears]
8: [enters, nester, renest, rentes, resent, tenser,
       ternes,��treens]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [earings, erasing, gainers, reagins, regains, reginas,
       searing, seringa]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]
8: [ates, east, eats, etas, sate, seat, seta, teas]
8: [carets, cartes, caster, caters, crates, reacts,
       recast,��traces]

洗牌

shuffle 算法执行与 sort 相反的操作，破坏了 List 中可能存在的任何顺序跟踪。也就是说，该算法基于来自随机源的输入重新排序 List，使所有可能的排列以相等的可能性发生（假设公平的随机源）。该算法在实现机会游戏时很有用。例如，它可用于洗牌表示牌组的 Card 对象的 List。此外，它对生成测试用例很有用。

此操作有两种形式：一种采用 List 并使用默认的随机源，另一种需要调用者提供 Random 对象以用作随机源。该算法的代码用作 List section 中的示例。

常规数据操作

Collections 类提供了五种算法，用于对 List 对象进行常规数据操作，所有这些算法都非常简单：

reverse 颠倒 List 中元素的顺序。
fill 用指定的值覆盖 List 中的每个元素。此操作对于重新初始化 List 非常有用。
copy 接受两个参数，一个目标 List 和一个源 List，并将源的元素复制到目标中，覆盖其内容。目标 List 必须至少与源一样长。如果它更长，则目标 List 中的其余元素不受影响。
swap 交换 List 中的指定位置的元素。
addAll 将所有指定的元素添加到 Collection。要添加的元素可以单独指定，也可以作为数组指定。

搜索

binarySearch 算法在已排序的 List 中搜索指定元素。该算法有两种形式。第一个采用 List 和要搜索的元素(“search key”)。此形式假定 List 根据其元素的自然顺序按升序排序。第二种形式除了 List 和搜索键之外，还有一个的 Comparator，并假设 List 按照指定的 Comparator 升序排序。在调用 binarySearch 之前，可以使用 sort 算法对 List 进行排序。

两个形式的返回值相同。如果 List 包含搜索键，则返回其索引。如果不包含，则返回值为 (-(插入点) - 1)，其中插入点是将值插入 List 的点，或者说是第一个大于值的元素的索引，或者如果 List 中的所有元素都小于指定值，则返回 list.size()。这个公认的丑陋公式保证当且仅当找到搜索键时返回值 >= 0。将布尔值 (是否找到) 和整数 (索引) 组合成单个 int 返回值基本上是一种破解。

以下习惯用法(可用于 binarySearch 操作的两种形式)查找指定的搜索键并将其插入适当的位置(如果它尚不存在)。

int pos = Collections.binarySearch(list, key);
if (pos < 0)
   l.add(-pos-1, key);

组成

频率和不相交算法测试一个或多个 Collections 的组成的某些方面：

frequency 计算指定元素在指定集合中出现的次数
disjoint 确定两个 Collections 是否不相交；也就是说，它们是否不包含任何共同的元素

求极值

min 和 max 算法分别返回指定 Collection 中包含的最小和最大元素。这两种操作都有两种形式。简单形式只接受 Collection，并根据元素的自然顺序返回最小(或最大)元素。除了 Collection 之外，第二种形式还需要 Comparator，并根据指定的 Comparator 返回最小(或最大)元素。