1
package javabasis.algorithm;
2

3
import java.util.ArrayList;
4
import java.util.List;
5
import java.util.Set;
6
import java.util.TreeMap;
7

8
/**
9
 * 字段排序算法
10
 *
11
 * @author Narule
12
 *
13
 */
14

15
public class StringAlgorithm {
16

17
  /**
18
   * 逐个字母比较排序
19
   *
20
   * @param disorder
21
   * @return orderly
22
   */
23
  public static String[] nopTop(String[] disorder) {
24
    int index = 0;
25
    int end = disorder.length;
26
    String[] orderly = new String[end]; // 新建排序后的数组
27
    TreeMap<Character, List<String>> treeMap = new TreeMap<>(); // 排序工具类，key是按照大小排序的
28
    List<String> list = null;
29

30
    // 收集字符串首字母信息
31
    for (String str : disorder) {
32
      char cTag = str.charAt(0);
33

34
      list = treeMap.get(cTag);
35
      if (list == null) {
36
        list = new ArrayList<>(1);
37
      }
38
      list.add(str);
39
      treeMap.put(cTag, list);
40
    }
41

42
    // 通过收集的首字母信息给字符串排序
43
    Set<Character> keySet = treeMap.keySet();
44
    for (char cTag : keySet) {
45
      list = treeMap.get(cTag);
46
      if (list != null && list.size() > 0) {
47

48
        if (list.size() < 2) { // 如果只有一个字符串，不需要递归
49
          for (String string : list) {
50
            orderly[index] = string;
51
            index++;
52
          }
53
        } else { // 如果有两个以上字符串，开头字母相同，可能需要递归排序
54
          ArrayList<String> arrayList = new ArrayList<>(0);
55
          for (String string : list) {
56
            if (string.length() > 1) { // 字符串长度大于2的，需要添加到list,准备下一次递归排序用到
57
              arrayList.add(string.substring(1));
58
            } else {
59
              orderly[index] = string;
60
              index++;
61
            }
62
          }
63
          if (arrayList.size() > 1) {
64
            String[] array = new String[arrayList.size()];
65
            int i = 0;
66
            for (String string : arrayList) {
67
              array[i] = string;
68
              i++;
69
            }
70
            array = nopTop(array); // 还需要递归排序 back background -> ack ackground
71
            for (String string : array) {
72
              orderly[index] = cTag + string;
73
              index++;
74
            }
75
          } else if (arrayList.size() == 1) {
76
            orderly[index] = cTag + arrayList.get(0);
77
            index++;
78
          }
79
        }
80
      }
81

82
    }
83
    treeMap.clear();
84
    return orderly; // 排序后的字符串数组
85
  }
86

87
  public static void main(String[] args) {
88
    String[] noP = { "apple", "car", "a", "family", "sky", "application", "app", "baby", "back", "background",
89
        "bad", "bbbbb", "bee", "cafe", "cake", "care" };
90
    String[] nopTop = nopTop(noP);
91
    for (String string : nopTop) {
92
      System.out.println(string);
93
    }
94

95
  }
96
}