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

  • 排序
  • 改组
  • 例行数据处理
  • 正在搜寻
  • 组成
  • 寻找极值

排序

排序算法对List进行重新排序，以便其元素按照排序关系升序排列。提供了两种形式的操作。简单形式采用一个List，并根据其元素的自然顺序对其进行排序。如果您不熟悉自然排序的概念，请阅读“对象排序”部分。
sort操作使用了快速优化且稳定的稍微优化的合并排序算法：

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

以下 trivial program按字典顺序（字母顺序）打印其参数。

  1. import java.util.*;
  3. public class Sort {
  4.     public static void main(String[] args) {
  5.         List<String> list = Arrays.asList(args);
  6.         Collections.sort(list);
  7.         System.out.println(list);
  8.     }
  9. }

让我们运行程序。

  1. % java Sort i walk the line

产生以下输出。

  1. [i, line, the, walk]

包含该程序只是为了向您展示算法确实像看起来一样容易使用。
sort的第二种形式除了List之外还包含一个Comparator，并使用Comparator对元素进行排序。假设您要按照相反的大小打印先前示例中的字谜组——首先是最大的字谜组。下面的示例向您展示如何在sort方法的第二种形式的帮助下实现这一目标。
回想一下，字谜组以List实例的形式作为值存储在Map中。修改后的打印代码将遍历Map的值视图，将通过最小尺寸测试的每个List放入List中。然后，代码使用需要List实例的Comparator对该List进行排序，并实现反向大小排序。最后，代码遍历已排序的List，并打印其元素（字谜组）。以下代码替换了Anagrams示例中main方法末尾的打印代码。

  1. // Make a List of all anagram groups above size threshold.
  2. List<List<String>> winners = new ArrayList<List<String>>();
  3. for (List<String> l : m.values())
  4.     if (l.size() >= minGroupSize)
  5.         winners.add(l);
  7. // Sort anagram groups according to size
  8. Collections.sort(winners, new Comparator<List<String>>() {
  9.     public int compare(List<String> o1, List<String> o2) {
  10.         return o2.size() - o1.size();
  11.     }});
  13. // Print anagram groups.
  14. for (List<String> l : winners)
  15.     System.out.println(l.size() + ": " + l);

在与“Map接口”部分相同的词典上运行该程序，并使用最小的字谜组大小（八个）相同，将产生以下输出。

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

洗牌

shuffle算法的作用与sort相反，破坏了List中可能存在的任何顺序痕迹。即，该算法基于来自随机性源的输入对List进行重新排序，从而假定合理的随机性源，所有可能的排列均以相同的可能性发生。该算法在实施机会游戏中很有用。例如，它可以用于洗牌代表牌组的卡片列表对象。另外，它对于生成测试用例也很有用。
此操作有两种形式：一种采用List并使用默认的随机源，另一种则要求调用者提供一个Random对象用作随机源。 此算法的代码在“List接口”部分中用作示例。

常规数据处理

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

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

搜寻

binarySearch算法在排序列表中搜索指定的元素。该算法有两种形式。第一个带有一个List和一个要搜索的元素（“搜索关键字”）。这种形式假定List是根据其元素的自然顺序以升序排序的。第二种形式除List和搜索键外还采用一个Comparator，并假定List根据指定的Comparator以升序排序。排序算法可用于在调用binarySearch之前对List进行排序。
两种形式的返回值都相同。如果List包含搜索关键字，则返回其索引。如果不是，则返回值是(-(insertion point) - 1)，其中插入点是将值插入List的点，第一个元素的索引大于该值的索引；或者list.size()，如果List中的所有元素都小于指定的值。这个丑陋的公式保证了只有当找到搜索键时，返回值才是>= 0。将布尔值(found)和整数(index)组合成单个int返回值基本上是一种技巧。
以下习惯用法可用于两种形式的binarySearch操作，查找指定的搜索关键字，并将其插入适当的位置（如果尚不存在）。

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

组成

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

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

寻找极值

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