算法
2022年6月19日大约 3 分钟约 901 字
C++ 的 STL 库已经有几十种非常有用的算法，每个算法都应用于泛型集合，Java 类库中的算法虽没有如此丰富，都也包含了一些基本的算法：排序、二分查找、交换等有一些实用算法。
1. 排序
显然，排序算法主要针对的是 List。
通常而言，在查看有关算法书籍中的排序算法时，介绍的大多是有关数组的排序算法，即使用的是随机访问方式。那么，对于链表这种随机访问效率很低的列表而言，尽管可以使用一种归并排序对链表高效地排序，但 Java 语言不是这样做的，Java 选择先将所有元素转入一个数组，对数组进行排序，然后再将排序后的序列复制回链表。
Collections 类中包含有如下相关静态方法：
| 方法 | 作用 |
|---|---|
<T extends Comparable<? super T>> void sort(List<T> list) | 根据元素的自然顺序排序 |
<T> void sort(List<T> list, Comparator<? super T> c) | 根据指定 Comparator 产生的顺序排序 |
void reverse(List<?> list) | 反转元素顺序 |
void shuffle(List<?> list) | 随机排序 |
void shuffle(List<?> list, Random rnd) | 随机排序，以 rnd 为随机数种子 |
2. 二分查找
二分查找只有在列表有序、支持随机访问的前提下才的意义。如果必须利用迭代方式查找的一半元素来找到中间元素，二分查找就完全失去了优势，因此算法将自动退化为线性查找。
<T> int binarySearch(List<? extends Comparable<? super T>> list, T key)：使用二分法查找指定List中的指定元素<T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
3. 其他算法
Collections 类中还有其他一些常用的简单算法：
| 方法 | 作用 |
|---|---|
<T extends Comprable<? super T>> T min(Collection<T> coll) | 根据元素的自然顺序，返回给定集合中的最小元素 |
<T extends Comprable<? super T>> T max(Collection<T> coll) | 根据元素的自然顺序，返回给定集合中的最大元素 |
<T> min(Collection<T> coll, Comparator<? super T> comp) | 根据 Comparator 指定的顺序，返回给定集合中的最小元素 |
<T> max(Collection<T> coll, Comparator<? super T> comp) | 根据 Comparator 指定的顺序，返回给定集合中的最大元素 |
<T> void copy(List<? super T> to, List<T> from) | 将原列表中的所有元素复制到目标列表的相应位置上。目标列表的长度至少要与原列表一样 |
<T> void fill(List<? super T> list, T value) | 使用指定元素替换指定 List 集合中的所有元素 |
<T> boolean addAll(Collection<? super T> c, T... values) | 将所有的值添加到给定的集合中。如果集合改变了，则返回 true |
<T> boolean replaceAll(List<T> list, T oldVal, T newVal) | 使用一个新值 newVal 替换 list 中所有值为 oldVal 的元素 |
int indexOfSubList(List<?> src, List<?> target) | 返回子 List 对象在父 List 对象中第一次出现的位置索引。若不存在，返回-1 |
int lastIndexOfSubList(List<?> src, List<?> target) | 返回子 List 对象在父 List 对象中最后一次出现的位置索引。若不存在，返回-1 |
void swap(List<?> list, int i, int j) | 交换 List 中索引 i 和索引 j 处的元素 |
void rotate(List<?> list, int distance) | 若 distance > 0，将后 distance 个元素整体移到前面；若 distance < 0，将前 distance 个元素整体移到后面 |
int frequency(Collection<?> c, Object o) | 返回指定集合中指定元素的出现次数 |
boolean disjoint(Collection<?> c1, Collection<?> c2) | 如果两个集合没有共同的元素，则返回 true |