算法

  面对不同元素类型的集合和不同的集合类型，可能相同的一个算法的实现方式不止一个。
  然而，泛型集合接口有一个很大的优点，即算法只需要实现一次。这正是集合接口的用武之地---为了高效地使用某个算法提供所需要的最小集合接口。
  这是一个非常重要的概念，标准的C++类库中已经有几十种非常有用的算法，每个算法都是在泛型集合上操作的。Java类库的算法没有如此丰富，但也包含了基本的排序、二分查找等实用的算法。

1.排序与混乱

  Collections类中的sort方法可以对实现了List接口的集合进行排序。

List<String> staff = new LinkedList<>()；
Collections.sort(staff)；

  这个方法假定列表元素实现了Comparable接口。如果想采用其他方式对列表进行排序，可以使用List接口的sort方法并传入一个Comparator对象。

staff.sort(Comparator.comparingDouble(Employee::getSalary))；

  人们可能对sort方法所采用的排序手段感到好奇。通常介绍的都是有关数组的排序算法，而且使用的是随机访问方式。但是对列表进行随机访问的效率很低。实际上，可以使用归并排序对列表进行高效地排序。然而，Java并不是这样实现的，它直接将所有元素转入一个数组，对数组进行排序，然后再将排序后的序列复制回列表。
  集合类库中使用的排序算法比快速排序要慢一些，快速排序是通用排序算法的传统选择。但是，归并排序有一个主要的优点：稳定，即不需要交换相同的元素。

  Collections类有一个算法shuffle，随机地混排列表中元素的顺序。如果提供的列表没有实现RandomAccess接口，shuffle方法将元素复制到数组中，然后打乱数组元素的顺序，最后再将打乱顺序后的元素复制回列表。

2.二分查找

  要想在数组中查找一个对象，通常要依次访问数组中的每个元素，直到找到匹配的元素为止。然而，如果数组是有序的，就可以直接查看位于数组中间的元素，看一看是否大于要查找的元素。如果是，用同样的方法在数组的前半部分继续查找；否则，用同样的方法在数组的后半部分继续查找。
  Collections类的binarySearch方法实现了这个算法。注意，集合必须是排好序的，否则算法将返回错误的答案。要想查找某个元素，必须提供集合以及要查找的元素。如果集合没有采用Comparable接口的compareTo方法进行排序，就还要提供一个比较器对象。
  如果binarySearch方法返回的数值大于等于0，则表示匹配对象的索引。如果返回负值，则表示没有匹配的元素。
  可以利用返回值计算应该将所查找的元素插入到集合的哪个位置，以保持集合的有序性。插入的位置是：-i-1。

  只有采用随机访问，二分查找才有意义。如果必须利用迭代方式一次次地遍历链表的一半元素来找到中间位置的元素，二分查找就完全失去了优势。因此，如果为binarySearch算法提供一个链表，它将自动地变为线性查找。

3.简单算法

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

简单算法.jpg

default void repalceAll(UnaryOperator<E> op)
//对这个列表的所有元素应用这个操作

4.集合与数组的转换

  由于Java平台API的大部分内容都是在集合框架创建之前设计的，所以，有时候需要在传统的数组和比较现代的集合之间进行转换。
  如果需要把一个数组转换为集合，Arrays.asList包装器可以达到这个目的：

String[] valuse = ...；
HashSet<String> staff = new HashSet<>(Arrays.asList(values))；

  从集合得到数组会更困难一些。可以使用toArray方法：

Object[] values = staff.toArray();

  不过，这样做的结果是一个对象数组。toArray方法返回的数组是一个Object[]数组，不能改变它的类型。实际上，必须使用toArray方法的一个变体形式，提供一个所需类型而且长度为0的数组。这样一来，返回的数组就会创建为相同的数组类型：

String[] valuse = staff.toArray(new String[0]);

5.编写自己的算法

  如果编写自己的算法(实际上，是以集合为参数的任何方法)，应该尽可能地使用接口，而不要使用具体的实现。并且应该使用能完成这项工作的最通用的集合接口。

//具体
void fillMenu(JMenu menu, ArrayList<JMenuItem> items) {
      for (JMenuItem item: items)
          menu.add(item);
}

//通用
void fillMenu(JMenu menu, Collection<JMenuItem> items) {
      for (JMenuItem item: items)
          menu.add(item);
}

  如果编写了一个返回集合的方法，最好返回一个集合接口，而不是具体的集合类。因为这样做可以在日后改变想法，并用另一个集合重新实现这个方法。

List<JMenuItem> getAllItems(JMenu menu) {
      List<JMenuItem> items = new Arraylist<>() 
          for (int i = 0; i < menu.getItemCount(); i++)
                items.add(menu.getItem(i));  
        return items;
}

  日后，当想做出修改方法时，可以直接返回匿名类。

List<JMenuItem> getAllItems (final JMenu menu) {
      return new AbstractList<>() {
              public JMenuItem get(int i) {
                   return menu.getItem(i);
                }
               public int size() {
                   return menu.getItemCount();
                }
          };
}