按字母排序

Question

我試圖實現一種排序算法，它按給定的字母排列對單詞列表進行排序。 （例如，如果給出排列「zyxwvutsrqponmlkjihgfedcba」和單詞列表「螞蟻，熊，貓，動物園，動物」我的算法會返回「動物園，貓，熊，螞蟻，動物」）我可以想出一種方法通過比較單詞中的每個字母與另一個單詞的字母來做到這一點，但這會花費太長時間。有沒有一種實現這種算法的優化方式，以便它可以更快地排序單詞？

Answer 1

您可以使用一個HashMap實現自定義的比較：

import java.util.*; 

public class Main { 
    public static class PermutationComparator implements Comparator<String> { 
     private final Map<Character, Integer> order; 

     public PermutationComparator(String permutation) { 
      this.order = new HashMap<Character, Integer>(); 
      for (int i = 0; i < permutation.length(); i++) { 
       order.put(permutation.charAt(i), i); 
      } 
     } 

     private int getOrder(char c) { 
      Integer value = order.get(c); 
      if (value == null) return -1; 
      return value; 
     } 

     @Override 
     public int compare(String o1, String o2) { 
      for (int i = 0; i < Math.min(o1.length(), o2.length()); i++) { 
       int compare = Integer.compare(getOrder(o1.charAt(i)), getOrder(o2.charAt(i))); 
       if (compare != 0) return compare; 
      } 
      return Integer.compare(o1.length(), o2.length()); 
     } 
    } 

    public static void main(String... args) { 
     String[] strings = {"ant", "bear", "cat", "zoo", "animal"}; 
     Arrays.sort(strings, new PermutationComparator("zyxwvutsrqponmlkjihgfedcba")); 
     System.out.println(Arrays.toString(strings)); 
    } 
} 

請注意這個比較投入比你任何東西之前定義的字符其他的一切。如果你想把它們放在別的後，使用方法：

if (value == null) return order.size(); 

如果你想不區分大小寫，使用方法：

Integer value = order.get(Character.toLowerCase(c));