题目：https://leetcode.com/problems/sort-characters-by-frequency/#/description
特殊的排序，对频率排序。
1.常规思路，先遍历一遍，把频数存入map，再把map的entry存入priorityqueue，最后逐一出队即可。代码：
public String frequencySort1(String s) { Map<Character, Integer> map = new HashMap<>(); for(char c : s.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1); PriorityQueue<Entry<Character, Integer>> pri = new PriorityQueue<>(new Comparator<Entry<Character, Integer>>(){ public int compare(Entry<Character, Integer> e1, Entry<Character, Integer> e2){ return Integer.valueOf(e1.getValue()).compareTo(Integer.valueOf(e2.getValue())); } }); for(Entry<Character, Integer> entry : map.entrySet()){ pri.add(entry); } String r = ""; while(!pri.isEmpty()){ Entry<Character, Integer> entry = pri.poll(); int num = entry.getValue(); char c = entry.getKey(); for(int i = 0; i < num; i++){ r = c + r; } } return r; } 复杂度分析：建立map需要On。对队列的操作，考虑worst case，所有都出现一次，那么队列大小为n，则出队开销为logn + log(n-1) + ... + log1。这个是nlogn复杂度。所以这个思路整体是Onlogn的。
《算法导论》中给出了结论，排序算法的时间下界是nlogn。但这不意味着这个题目也是这样。因为这个题目有特殊点，是对频数排序。最大频数是On的。因此可以把频数作为数组下标，数组值存该频数的字母，这里可能包含多个，因此是一个string。然后遍历这个数组即可。时间是On的空间也是On的。
这个思路有点类似于桶排，总之就是假设对k1,k2,...,kn排序，如果ki最大值可以保证不是是很大，那么可以把ki作为数组索引，最后遍历数组。这个方法是On级别的。但是空间需要较大。
代码：
public String frequencySort(String s) { Map<Character, Integer> map = new HashMap<>(); int max = 0; for(char c : s.toCharArray()){ map.put(c, map.getOrDefault(c, 0) + 1); max = Math.max(max, map.get(c)); } StringBuffer[] pos = new StringBuffer[max + 1]; for(Entry<Character, Integer> entry : map.entrySet()){ int count = entry.getValue(); if(pos[count] == null) pos[count] = new StringBuffer(); pos[count].append(entry.getKey()); } StringBuffer r = new StringBuffer(); for(int i = pos.length - 1; i >= 0; i--){ if(pos[i] != null){ for(char c : pos[i].toString().toCharArray()){ for(int j = 0; j < i; j++){ r.append(c); } } } } return r.toString(); }下面是对logi求和的证明：
可以采用夹逼法，求出上届和下界。
