Collections框架中sort自然排序binarySearch二分查找详解

今天要用到Collections的binarySearch方法的查找功能，但是要是用二分查找的List必须是有序的，也就是使用 Collections中的sort方法进行自然排序。

在对List中的数据查找的时候我们经常会用到contains、find、indexOf等线性查找方法，已经有很多前辈对线性查找和二分查找的性能做过测试，我们就站在前辈的肩膀上直接得出我们的结论，有兴趣的同学可以自己做实验。

• 线性查找方式在数据量小的时候比较快，性能相对有优势

• 在数据量比较大的时候二分查找的性能比较好，性能优势比较明显。结论我们大家现在应该很清楚如何运用二分查找和线性查找了。

List元素自然排序

• sort方法使用的算法是TimSort(归并排序做了大量优化的版本)算法

  假定，我们的 TimSort 是进行升序排序。TimSort 为了减少对升序部分的回溯和对降序部分的性能倒退，将输入按其升序和降序特点进行了分区。排序的输入的单位不是一个个单独的数字了，而一个个的分区。其中每一个分区我们叫一个“run“。针对这个 run 序列，每次我们拿一个 run 出来进行归并。每次归并会将两个 runs 合并成一个 run。归并的结果保存到 “run_stack” 上。如果我们觉得有必要归并了，那么进行归并，直到消耗掉所有的 runs。这时将 run_stack 上剩余的 runs 归并到只剩一个 run 为止。这时这个仅剩的 run 即为我们需要的排好序的结果。

• 对List中的数据进行自然排序

      List<Integer> list = Arrays.asList(6,7,5,8,4,3,9,2,0,1,12,34,56,78,94);

      System.out.println(list);
      Collections.sort(list);
      System.out.println(list);12345

输出结果是：

[6, 7, 5, 8, 4, 3, 9, 2, 0, 1, 12, 34, 56, 78, 94]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 34, 56, 78, 94]12

• 带有比较器的sort排序降序排列

      List<Integer> list = Arrays.asList(6,7,5,8,4,3,9,2,0,1,12,34,56,78,94);

      System.out.println(list);
      Collections.sort(list, new Comparator<Integer>() {

          @Override
          public int compare(Integer o1, Integer o2) {
              if(o1.compareTo(o2) > 0) {
                  return -1;
              } else if(o1.compareTo(o2) < 0){
                  return 1;
              } else {
                  return 0;
              }
          }
      });
      System.out.println(list);1234567891011121314151617

输出结果：

[6, 7, 5, 8, 4, 3, 9, 2, 0, 1, 12, 34, 56, 78, 94]
[94, 78, 56, 34, 12, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]12

二分查找

• 使用二分搜索法搜索指定列表，以获得指定对象。在进行此调用之前，必须根据列表元素的自然顺序对列表进行升序排序，也就是使用sort进行自然升序排列。

• 如果没有对列表进行排序，则结果是不确定的。如果列表包含多个等于指定对象的元素，则无法保证找到的是哪一个。

• 使用默认的二分查找方法查找List中的元素

      List<Integer> list = Arrays.asList(6,7,5,8,4,3,9,2,0,1,12,34,56,78,94);

      System.out.println(list);
      Collections.sort(list, new Comparator<Integer>() {

          @Override
          public int compare(Integer o1, Integer o2) {
              if(o1.compareTo(o2) > 0) {
                  return 1;
              } else if(o1.compareTo(o2) < 0){
                  return -1;
              } else {
                  return 0;
              }
          }
      });
      System.out.println(list);
      int index = Collections.binarySearch(list, 9);
      System.out.println(index);