Java集合框架——算法

算法

Java平台对List实例提供了一些通用的算法，能较高效高效的实现排序、乱序、查询、极值等功能。

排序

排序是使集合中的元素按一定大小顺序排列的操作。

排序算法有两种形式：按元素自然顺序排序和自定义排序。

自然排序是按照元素的自然顺序比较大小，如下所示：

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]

The program was included only to show you that algorithms really are as easy to use as they appear to be.

自定义排序是通过自定义比较器来比较大小，如下所示：

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

乱序

乱序算法实现的功能和排序恰恰相反，它将集合中的元素打乱，使其随机排列。在前面的集合接口的有关章节有过介绍，这里就不累述了。

数据常规操作

Collections类为List提供了五中数据常规操作的算法，分别是：

1. reverse — 使List中的元素按相反的顺序排列
2. fill — 将List的所有元素赋给一个特定值，通常用来初始化List。
3. copy — 将源List中的元素拷贝到目标List中
4. swap — 交换List中两个元素的位置
5. addAll — 将所有满足特定条件的元素添加到一个集合中

查询

可以通过binarySearch函数实现对一个有序的List进行折半查找，从而快速的查询元素，如下所示：

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

Composition

Requency和disjoint算法可以用来测试集合的元素组成：

1. frequency — 获取某个元素在集合中的个数
2. disjoint — 检测两个集合是否没有共同的元素

获取极值

可以通过min和 max 函数获取集合中的极小值和极大值。