剑指Offer——巧妙使用sort(List<T>,Comparator<? super T>)比较器

先入为主

  

   

    

     

    
    

     

      package cn.edu.ujn.offersword;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      import java.util.ArrayList;
     
    
   

    

     

    
    

     

      import java.util.Collections;
     
    
   

    

     

    
    

     

      import java.util.Comparator;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public class C5_33_SortArrayForMinNumber {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * @date 2016-09-15
     
    
   

    

     

    
    

     

       * @number 04
     
    
   

    

     

    
    

     

       * @author SHQ
     
    
   

    

     

    
    

     

       * 把数组排成最小的数
     
    
   

    

     

    
    

     

       * 题目描述
     
    
   

    

     

    
    

     

       * 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
     
    
   

    

     

    
    

     

       * 例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
     
    
   

    

     

    
    

     

       * 思路
     
    
   

    

     

    
    

     

       * 通过Collection.sort()方法中的自定义比较器实现。若mn>nm，则说明nm满足要求。
     
    
   

    

     

    
    

     

       * 时间复杂度 O(nlogn);
     
    
   

    

     

    
    

     

       * 空间复杂度O(2);
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      public static void main(String[] args) {
     
    
   

    

     

    
    

     

      int[] numbers = {3,5,1,4,2};
     
    
   

    

     

    
    

     

      System.out.println(PrintMinNumber(numbers));
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 private static String PrintMinNumber(int [] numbers) {
     
    
   

    

     

    
    

     
 if(numbers == null || numbers.length == 0){
     
    
   

    

     

    
    

     
 return null;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       ArrayList<Integer> list = new ArrayList<Integer>();
     
    
   

    

     

    
    

     
 for(int i = 0; i < numbers.length; i++){
     
    
   

    

     

    
    

     

       list.add(numbers[i]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 // 升序(自定义比较器)
     
    
   

    

     

    
    

     

       Collections.sort(list, new Comparator<Integer>() {
     
    
   

    

     

    
    

     
 @Override
     
    
   

    

     

    
    

     
 public int compare(Integer str1, Integer str2) {// 实现接口中的方法 
     
    
   

    

     

    
    

     
 return (str1+""+str2).compareTo(str2+""+str1);  
     
    
   

    

     

    
    

     

       }  
     
    
   

    

     

    
    

     

      });
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       StringBuffer sb = new StringBuffer();
     
    
   

    

     

    
    

     
 for(int str : list){
     
    
   

    

     

    
    

     

       sb.append(str);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return sb.toString();
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

注  sort讲解

    翻翻 API 会发现， Arrays.sort 还有种重载形式：sort(T[] a, Comparator<？ super T> c) ，这个方法参数的写法用到了泛型，我们还没讲到。我们可以把它理解成这样的形式： sort(Object[] a, Comparator c) ，这个方法的意思是按照比较器 c 给出的比较排序算法，对 Object 数组进行排序。Comparator 接口中定义了两个方法： compare(Object o1, Object o2) 和 equals 方法，由于 equals 方法所有对象都有的方法，因此当我们实现 Comparator 接口时，我们只需重写 compare 方法，而不需重写 equals 方法。Comparator 接口中对重写 equals 方法的描述是：“注意，不重写 Object.equals(Object) 方法总是安全的。然而，在某些情况下，重写此方法可以允许程序确定两个不同的 Comparator 是否强行实施了相同的排序，从而提高性能。”。我们只需知道第一句话就OK了，也就是说，可以不用去想应该怎么实现 equals 方法，因为即使我们不显示实现 equals 方法，而是使用Object类的 equals 方法，代码依然是安全的。

    排序算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。此算法提供可保证的 n log(n) 性能。指定列表必须是可修改的，但不必是可大小调整的。此实现将指定列表转储到一个数组中，并对数组进行排序，在重置数组中相应位置每个元素的列表上进行迭代。这避免了由于试图原地对链接列表进行排序而产生的 n2 log(n) 性能。

    参数：

    list - 要排序的列表。

    c - 确定列表顺序的比较器。null 值指示应该使用元素的自然顺序。

  抛出：

      ClassCastException - 如果列表中包含不可使用指定比较器相互比较 的元素。

      UnsupportedOperationException - 如果指定列表的列表迭代器不支持 set 操作。

美文美图

文章来源: shq5785.blog.csdn.net，作者：No Silver Bullet，版权归原作者所有，如需转载，请联系作者。

原文链接：shq5785.blog.csdn.net/article/details/52554746