课程：算法

原文： https://docs.oracle.com/javase/tutorial/collections/algorithms/index.html

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

排序

sort算法重新排序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]

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

除了List之外，sort的第二种形式还需要 Comparator ，并使用Comparator对元素进行排序。假设您想要以相反的大小顺序打印出我们之前示例中的 anagram 组 - 首先是最大的 anagram 组。下面的示例向您展示了如何借助sort方法的第二种形式实现此目的。

回想一下，anagram 组以List实例的形式存储为Map中的值。修改后的打印代码遍历Map的值视图，将通过最小尺寸测试的每个List放入List的List中。然后代码使用期望List实例的Comparator对此List进行排序，并实现反向大小排序。最后，代码遍历排序的List，打印其元素（anagram 组）。以下代码替换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);

在 same dictionary 上运行 the program ，如映射接口部分，具有相同的最小 anagram 组大小（8），产生以下输出。

  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，使得假设公平的随机源，所有可能的排列以相等的可能性发生。该算法在实现机会游戏时很有用。例如，它可以用于随机播放代表牌组的Card对象的List。此外，它对生成测试用例很有用。

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

常规数据操作

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

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

搜索

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

两个表单的返回值相同。如果List包含搜索键，则返回其索引。如果不是，则返回值为(-(insertion point) - 1)，其中插入点是将值插入List的点，或者第一个元素的索引大于值或list.size()如果所有元素都在List小于指定值。当且仅当找到搜索关键字时，这个公认的丑陋公式保证返回值为&gt;= 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返回最小（或最大）元素。