5 算法

Wu Jun 2019-12-31 14:22:47
05 Java > 00 Java 基础 > 06 集合

泛型集合接口有一个很大的优点,即算法只需要实现一次。

1 排序与混排

1.1 排序

Collections.sort()

底层使用了数组的归并排序。即先转化集合为数组,排好序以后在复制回以前的集合。

归并排序相较于快速排序,速度慢,但是稳定,它不需要交换相同的元素。

排序传递的列表必须是可修改的,不必要是可改变大小的。

1.2 混排

Collections.shuffle(List)

随机的打乱列表中元素的顺序。每次都不一样。

2 二分查找

Collections.binarySearch

集合必须是排好序的。返回的数值大于等于0,则表示匹配对象的索引。返回负值,则表示没有匹配的元素。可以利用返回值计算应该将element插入到集合的位置(-i-1),以保持集合的有序性。

只有采取随机访问,二分查找才有意义,如果必须利用迭代一次次的遍历链表的一般元素来找到中间元素的位置,二分查找就失去了它的优势,因此,如果传入的是LinkedList链表,它将自动转换成线性查找。

3 简单算法

在Collections类中包含了几个简单且很有用的算法。

max、min、copy、fill、addAll、replaceAll、swap、reverse、rotate、frequency、disjoint

indexOfSubList、lastIndexOfSubList

4 批操作

可避免频繁地使用迭代器。

指 Set 的 removeAll、retainAll 操作。对于 Map,也可 keySet().removeAll()。

5 集合与数组之间的转换

数组转集合:利用 Arrays.adList 的包装器。

String[] arr = {"aaa","bbb"};
List<String> list = new ArrayList<>(Arrays.asList(arr));

集合转数组:list.toArray(new String[]);

String[] strArr = list.toArray(new String[0]);
String[] strArr = list.toArray(new String[list.size()]);

6 编写自己的算法

如果编写以集合作为参数的任何方法,应该尽可能地使用接口,而不要使用具体的实现。