Lesson: Algorithms

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

Sorting

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

sort操作使用快速且稳定的稍微优化的合并排序算法:

  • 快速 :保证在n log(n)时间内运行,并且在几乎排序的列表上运行的速度明显更快。经验测试表明,它与高度优化的快速排序一样快。通常认为,快速排序比合并排序要快,但它不稳定并且不能保证n log(n)性能。

  • 稳定 :它不会对相等的元素重新排序。如果您对不同属性重复对同一列表进行排序,这很重要。如果邮件程序的用户按邮寄日期对收件箱进行排序,然后按发件人对其进行排序,则用户自然希望来自给定发件人的当前连续邮件列表将(仍)按邮寄日期进行排序。仅当第二种情况稳定时,才能保证这一点。

以下trivial program以字典(字母 Sequences)Sequences 打印其参数。

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对元素进行排序。假设您要按照相反的大小 Sequences 打印先前示例中的字谜组-首先是最大的字谜组。下面的示例向您展示了如何借助sort方法的第二种形式实现这一目标。

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

Map interface部分中的same dictionary一样,在the program上运行the program,并且最小的字谜组大小相同(八),将产生以下输出。

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

shuffle算法的作用与sort相反,破坏了List中可能存在的任何 Sequences 跟踪。即,该算法基于来自随机性源的 Importing 对List进行重新排序,以使所有可能的排列都以相等的可能性发生(假定随机性的公平源)。该算法在实现机会游戏中很有用。例如,它可以用于对代表甲板的Card个对象中的List个进行混洗。另外,它对于生成测试用例也很有用。

此操作有两种形式:一种采用List并使用默认的随机源,另一种则要求调用者提供一个Random对象用作随机源。该算法的代码在List section中用作示例。

常规数据处理

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

  • reverse —反转List中元素的 Sequences。

  • fill —用指定的值覆盖List中的每个元素。此操作对于重新初始化List很有用。

  • copy —接受两个参数,即目标List和源List,并将源的元素复制到目标中,从而覆盖其内容。Object 地List必须至少与来源一样 Long。如果更 Long,则目标List中的其余元素不受影响。

  • swap —交换List中指定位置的元素。

  • addAll —将所有指定的元素添加到Collection。要添加的元素可以单独指定或作为数组指定。

Searching

binarySearch算法在排序的List中搜索指定的元素。该算法有两种形式。第一个使用List和一个要搜索的元素(“搜索关键字”)。此格式假定List根据其元素的自然 Sequences 以升序排序。第二种形式除List和搜索键外还采用Comparator,并假定List根据指定的Comparator升序排列。 sort算法可用于在调用binarySearch之前对List进行排序。

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

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

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

Composition

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

  • frequency —计算指定元素在指定集合中出现的次数

  • disjoint —确定两个Collections是否不相交;也就是说,它们是否不包含共同点

寻找极致价值

minmax算法分别返回指定Collection中包含的最小和最大元素。这两种操作都有两种形式。简单形式仅需使用Collection并根据元素的自然 Sequences 返回最小(或最大)元素。第二种形式除Collection外还采用Comparator并根据指定的Comparator返回最小(或最大)元素。