混排(Shuffling)
混排算法所做的正好与 sort 相反: 它打乱在一个 List 中可能有的任何排列的踪迹。也就是说,基于随机源的输入重排该 List, 这样的排列具有相同的可能性(假设随机源是公正的)。这个算法在实现一个碰运气的游戏中是非常有用的。例如,它可被用来混排代表一副牌的 Card 对象的一个 List 。另外,在生成测试案例时,它也是十分有用的。
这个操作有两种形式。第一种只采用一个 List 并使用默认随机源。第二种要求调用者提供一个 Random 对象作为随机源。这个算法的一些实际代码曾在 List 课程中被作为例子使用。
常规数据操作(Routine Data Manipulation)
Collections 类为在 List 对象上的常规数据操作提供了三种算法。这些算法是十分简单明了的:
reverse: 反转在一个列表中的元素的顺序。
fill: 用特定值覆盖在一个 List 中的每一个元素。这个操作对初始化一个 List 是十分有用的。
copy: 用两个参数,一个目标 List 和一个源 List, 将源的元素拷贝到目标,并覆盖它的内容。目标 List 至少与源一样长。假如它更长,则在目标 List 中的剩余元素不受影响。
搜索(Searching)
binary search (二进制搜索)算法用二进制搜索算法在一个已排序的 List 中寻找特定元素。这个算法有两种形式。第一种采用一个 List 和一个要寻找的元素 ( "搜索键(search key)")。这种形式假设 List 是按照它的元素的自然排序排列成上升顺序的。第二种形式除采用 List 外,还采用一个 Comparator 以及搜索键,并假设 List 是按照特定 Comparator 排列成上升顺序的。 排序算法(描述见上) 可优先于 binarySearch 而被用来为List 排序。
两种形式的返回值是相同的: 假如 List 包含搜索键,它的索引将被返回;假如不包括,则返回值为 (-(insertion point) - 1), 这里的 insertion point 被定义为一个点,从这个点该值将被插入到这个 List 中:大于该值的第一个元素的位置索引,或list.size()。 选用这个不可否认的难看的公式是为了保证假如且仅假如搜索键被发现,则返回值将等于0。它基本上是一个将布尔逻辑 ("found") 和整数 ("index") 综合到单一的int返回值的大杂烩。
下列惯用程序对 binarySearch 操作的两种形式均适用,它寻找特定搜索键,假如搜索键不出现,则将它插入到适当的位置:
int pos = Collections.binarySearch(l, key);
if (pos
l.add(-pos-1, key);
寻找极值(Finding Extreme Values)
min 和 max 算法分别返回包含在特定 Collection 中的最小和最大元素。这两个操作都各有两种形式,简单形式只采用一个 Collection, 并按照元素的自然排序返回最小 (或最大) 元素;另一种形式除采用 Collection 之外,还采用一个 Comparator,并按照特定 Comparator返回最小(或最大)元素。
这些就是由Java 平台提供的作用于与 List 对象相对的任意 Collection 对象上的仅有算法,就象上面提到的 fill 算法一样,这些算法都是非常简单明了的,它们是Java平台为程序员非凡提供的便利工具。