课程：算法

这里描述的多态算法是Java平台提供的可重用功能的一部分。它们都来自Collections类，并且都采用静态方法的形式，其第一个参数是要执行操作的集合。Java平台提供的绝大多数算法都是对List实例进行操作，但也有一些算法适用于任意的Collection实例。本节简要描述以下算法：

• 排序
• 洗牌
• 常规数据操作
• 搜索
• 组合
• 查找极值

排序

sort算法会根据排序关系将List的元素重新排序为升序。提供了两种形式的操作。简单形式接受一个List并根据其元素的自然排序进行排序。如果您不熟悉自然排序的概念，请阅读对象排序部分。

sort操作使用了稍微优化的归并排序算法，它速度快且稳定：

• 快速：它保证以n log(n)的时间运行，并且在几乎有序的列表上运行速度更快。经验证明，它的速度与高度优化的快速排序相当。快速排序通常被认为比归并排序更快，但它不稳定，并且不能保证n log(n)的性能。
• 稳定：它不会重新排列相等的元素。如果您反复对不同属性的同一个列表进行排序，这一点非常重要。如果一个邮件程序的用户按照邮件日期对收件箱进行排序，然后按照发件人进行排序，用户自然希望来自同一发件人的邮件仍然按照邮件日期排序。只有当第二次排序是稳定的时，才能保证这一点。

以下的简单程序按字典顺序（字母顺序）打印出其参数。

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对元素进行排序。假设您想要以大小的逆序（最大的字谜组首先）打印出之前示例中的字谜组。接下来的示例将向您展示如何使用sort方法的第二种形式来实现此目标。

请记住，字谜组以List实例的形式作为值存储在Map中。修订后的打印代码遍历Map的值视图，将每个通过最小大小测试的List放入List的List。然后，该代码使用一个Comparator对此List进行排序，该Comparator期望List实例，并实现逆向大小排序。最后，该代码遍历排序后的List，打印其元素（即字谜组）。以下代码替换了Anagrams示例中main方法末尾的打印代码。

// 创建一个超过最小大小阈值的所有字谜组的List。
List<List<String>> winners = new ArrayList<List<String>>();
for (List<String> l : m.values())
    if (l.size() >= minGroupSize)
        winners.add(l);

// 根据大小对字谜组进行排序
Collections.sort(winners, new Comparator<List<String>>() {
    public int compare(List<String> o1, List<String> o2) {
        return o2.size() - o1.size();
    }});

// 打印字谜组。
for (List<String> l : winners)
    System.out.println(l.size() + ": " + l);

在程序中，使用与Map接口部分中相同的字典和相同的最小字谜组大小（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相反，它破坏了列表中可能存在的任何顺序痕迹。也就是说，这个算法根据随机源的输入重新排序列表，以便所有可能的排列以等概率发生，假设随机源是公平的。这个算法在实现游戏机会的时候非常有用。例如，它可以用来洗牌一个代表一副牌的Card对象的列表。此外，它还可以用于生成测试用例。

这个操作有两种形式：一种是接受一个列表并使用默认的随机源，另一种要求调用者提供一个Random对象作为随机源。该算法的代码作为一个示例在List章节中使用。

常规数据操作

Collections类提供了五种算法来对List对象进行常规数据操作，它们都非常简单：

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

搜索

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

两种形式的返回值相同。如果List包含搜索关键字，则返回其索引。如果没有，则返回值为(-(插入点) - 1)，其中插入点是将该值插入到List中的位置，或者是第一个大于该值的元素的索引，如果List中的所有元素都小于指定的值，则为list.size()。这个确实很丑的公式保证了返回值只有在找到搜索关键字时才会大于等于0。基本上，它是将一个布尔值(found)和一个整数(index)组合成一个单独的int返回值的技巧。

下面的用法适用于binarySearch操作的两种形式，它寻找指定的搜索关键字，并在适当的位置插入它（如果它不存在）。

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

组成

frequency和disjoint算法测试一个或多个Collections的组成方面：

• frequency — 计算指定元素在指定集合中出现的次数
• disjoint — 判断两个Collections是否不相交；即它们是否没有共同的元素

查找极值

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