Lesson: Algorithms课程：算法

The polymorphic algorithms described here are pieces of reusable functionality provided by the Java platform. 这里描述的多态算法是Java平台提供的可重用功能。All of them come from the Collections class, and all take the form of static methods whose first argument is the collection on which the operation is to be performed. 它们都来自Collections类，都采用静态方法的形式，其第一个参数是要对其执行操作的集合。The great majority of the algorithms provided by the Java platform operate on List instances, but a few of them operate on arbitrary Collection instances. Java平台提供的绝大多数算法都在List实例上运行，但有少数算法在任意集合实例上运行。This section briefly describes the following algorithms:本节简要介绍以下算法：

• Sorting排序
• Shuffling洗牌
• Routine Data Manipulation例行数据处理
• Searching搜索
• Composition作文
• Finding Extreme Values寻找极值

Sorting排序

The sort algorithm reorders a List so that its elements are in ascending order according to an ordering relationship. sort算法对List进行重新排序，使其元素根据排序关系按升序排列。Two forms of the operation are provided. 提供了两种操作形式。The simple form takes a List and sorts it according to its elements' natural ordering. 简单表单采用一个List，并根据其元素的自然顺序对其进行排序。If you're unfamiliar with the concept of natural ordering, read the Object Ordering section.如果你不熟悉自然排序的概念，请阅读对象排序部分。

The sort operation uses a slightly optimized merge sort algorithm that is fast and stable:sort操作使用了一种稍微优化的合并排序算法，该算法快速稳定：

• Fast: It is guaranteed to run in n log(n) time and runs substantially faster on nearly sorted lists. 快速：它保证在n log(n)时间内运行，并且在几乎排序的列表上运行得更快。Empirical tests showed it to be as fast as a highly optimized quicksort. 经验测试表明，它与高度优化的快速排序一样快。A quicksort is generally considered to be faster than a merge sort but isn't stable and doesn't guarantee n log(n) performance.快速排序通常被认为比合并排序更快，但不稳定，也不能保证n log(n)性能。
• Stable: It doesn't reorder equal elements. 稳定：它不会重新排列相等的元素。This is important if you sort the same list repeatedly on different attributes. 如果在不同属性上重复对同一列表排序，这一点很重要。If a user of a mail program sorts the inbox by mailing date and then sorts it by sender, the user naturally expects that the now-contiguous list of messages from a given sender will (still) be sorted by mailing date. 如果邮件程序的用户按邮寄日期对收件箱进行排序，然后按发件人对其进行排序，那么用户自然希望（仍然）按邮寄日期对来自给定发件人的现在连续的邮件列表进行排序。This is guaranteed only if the second sort was stable.只有在第二类是稳定的情况下才能保证这一点。

The following trivial program prints out its arguments in lexicographic (alphabetical) order.下面这个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);
    }
}

Let's run the program.让我们运行这个程序。

% java Sort i walk the line

The following output is produced.产生以下输出。

[i, line, the, walk]

The program was included only to show you that algorithms really are as easy to use as they appear to be.包含该程序只是为了向您展示，算法真的像看上去那样易于使用。

The second form of sort takes a Comparator in addition to a List and sorts the elements with the Comparator. sort的第二种形式是在列表之外使用Comparator，并使用Comparator对元素进行排序。Suppose you want to print out the anagram groups from our earlier example in reverse order of size — largest anagram group first. 假设您想按大小的相反顺序打印出我们前面示例中的字谜组—首先是最大的字谜组。The example that follows shows you how to achieve this with the help of the second form of the sort method.下面的示例向您展示了如何借助sort方法的第二种形式来实现这一点。

Recall that the anagram groups are stored as values in a Map, in the form of List instances. 回想一下，字谜组以List实例的形式存储为Map中的值。The revised printing code iterates through the Map's values view, putting every List that passes the minimum-size test into a List of Lists. Then the code sorts this List, using a Comparator that expects List instances, and implements reverse size-ordering. Finally, the code iterates through the sorted List, printing its elements (the anagram groups). The following code replaces the printing code at the end of the main method in the Anagrams example.

// 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);

Running the program on the same dictionary as in The Map Interface section, with the same minimum anagram group size (eight), produces the following output.在与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]

Shuffling洗牌

The shuffle algorithm does the opposite of what sort does, destroying any trace of order that may have been present in a List. That is, this algorithm reorders the List based on input from a source of randomness such that all possible permutations occur with equal likelihood, assuming a fair source of randomness. This algorithm is useful in implementing games of chance. For example, it could be used to shuffle a List of Card objects representing a deck. Also, it's useful for generating test cases.此外，它还可用于生成测试用例。

This operation has two forms: one takes a List and uses a default source of randomness, and the other requires the caller to provide a Random object to use as a source of randomness. 此操作有两种形式：一种是获取列表并使用默认的随机性源，另一种是要求调用方提供随机对象以用作随机性源。The code for this algorithm is used as an example in the List section. 该算法的代码在List部分用作示例。

Routine Data Manipulation常规数据操作

The Collections class provides five algorithms for doing routine data manipulation on List objects, all of which are pretty straightforward:Collections类提供了五种算法，用于对List对象执行例行数据操作，所有这些算法都非常简单：

• reverse — reverses the order of the elements in a List.反转List中元素的顺序。
• fill — overwrites every element in a List with the specified value. 用指定的值覆盖List中的每个元素。This operation is useful for reinitializing a List.此操作对于重新初始化List很有用。
• copy — takes two arguments, a destination List and a source List, and copies the elements of the source into the destination, overwriting its contents. 接受两个参数，一个目标List和一个源List，并将源的元素复制到目标中，覆盖其内容。The destination List must be at least as long as the source. 目标List必须至少与源列表一样长。If it is longer, the remaining elements in the destination List are unaffected.如果更长，则目标List中的其余元素不受影响。
• swap — swaps the elements at the specified positions in a List.在List中的指定位置交换元素。
• addAll — adds all the specified elements to a Collection. 将所有指定的元素添加到Collection中。The elements to be added may be specified individually or as an array.要添加的元素可以单独指定，也可以作为数组指定。

Searching搜索

The binarySearch algorithm searches for a specified element in a sorted List. binarySearch算法在排序List中搜索指定的元素。This algorithm has two forms. 该算法有两种形式。The first takes a List and an element to search for (the "search key"). 第一个是一个List和一个要搜索的元素（“搜索键”）。This form assumes that the List is sorted in ascending order according to the natural ordering of its elements. 这种形式假设List按照元素的自然顺序按升序排序。The second form takes a Comparator in addition to the List and the search key, and assumes that the List is sorted into ascending order according to the specified Comparator. 第二种形式除了List和搜索键之外，还采用了一个Comparator，并假设List是根据指定的Comparator按升序排序的。The sort algorithm can be used to sort the List prior to calling binarySearch.sort算法可用于在调用binarySearch之前对List进行排序。

The return value is the same for both forms. 两种形式的返回值相同。If the List contains the search key, its index is returned. 如果List包含搜索键，则返回其索引。If not, the return value is (-(insertion point) - 1), where the insertion point is the point at which the value would be inserted into the List, or the index of the first element greater than the value or list.size() if all elements in the List are less than the specified value. 如果不是，则返回值为(-(insertion point) - 1)，其中插入点是将该值插入List的点，或者如果List中的所有元素都小于指定值，则返回大于该值的第一个元素的索引或list.size()。This admittedly ugly formula guarantees that the return value will be >= 0 if and only if the search key is found. 这个公认的丑陋公式保证了当且仅当找到搜索键时，返回值将>=0。It's basically a hack to combine a boolean (found) and an integer (index) into a single int return value.基本上，将布尔(found)和整数(index)组合成一个int返回值是一种技巧。

The following idiom, usable with both forms of the binarySearch operation, looks for the specified search key and inserts it at the appropriate position if it's not already present.下面的习惯用法可用于两种形式的binarySearch操作，它会查找指定的搜索键，并将其插入到适当的位置（如果它尚未出现）。

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

Composition合成

The frequency and disjoint algorithms test some aspect of the composition of one or more Collections:频率和不相交算法测试一个或多个Collections组成的某些方面：

• frequency — counts the number of times the specified element occurs in the specified collection统计指定元素在指定集合中出现的次数
• disjoint — determines whether two Collections are disjoint; that is, whether they contain no elements in common确定两个Collections是否不相交；也就是说，它们是否不包含共同元素

Finding Extreme Values寻找极值

The min and the max algorithms return, respectively, the minimum and maximum element contained in a specified Collection. min和max算法分别返回指定Collection中包含的最小和最大元素。Both of these operations come in two forms. 这两种操作都有两种形式。The simple form takes only a Collection and returns the minimum (or maximum) element according to the elements' natural ordering. 简单表单只接受一个Collections，并根据元素的自然顺序返回最小（或最大）元素。The second form takes a Comparator in addition to the Collection and returns the minimum (or maximum) element according to the specified Comparator.第二种形式是在Collection之外使用一个Comparator，并根据指定的Comparator返回最小（或最大）元素。