随笔博文

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

2023-04-11 15:33:28 michael007js 80

今天要用到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);


首页
关于博主
我的博客
搜索