/**
a
app
apple
application

baby
back
background
bad
bbbbb
bee
cafe 
cake
car
care
family
sky

**/

public static void main(String[] args) {
    String[] noP = {"Baby","apple", "car", "A", "family", "B","b", "Sky", "application", "app", "baby", "back", "background",
                    "bad", "bbbbb", "bee", "cafe", "cake", "care" };
    String[] nopTop = sortByWeights(noP);
    for (String string : nopTop) {
        System.out.print(string + ",");
    }
    System.out.println();
    System.out.println("----------------------");
    for (String string : nopTop) {
        System.out.println("weights:\t" + getStrWeights(string,0) + "\t" + string);
    }
}


/**
 *  for 权重排序
 * 
 */
public static String[] sortByWeights(String[] disorder) {

    double[] weightsArr = new double[disorder.length]; 
    HashMap<Double,Integer> recordMap = new HashMap<>();

    // 计算每个字符串的权重值
    for (int i=0; i<disorder.length ;i++) {
        weightsArr[i] = getStrWeights(disorder[i],0);
        recordMap.put(weightsArr[i],i);//保存权重值对应的字符串所在数组位置
    }

    // 将获取的权重值排序
    Arrays.sort(weightsArr);

    String[] sorderStr = new String[disorder.length];
    int orderIndex = 0;
    for (int i=0; i<sorderStr.length ;i++) {
        // 拿出排好序的索引
        orderIndex = recordMap.get(weightsArr[i]);
        sorderStr[i] = disorder[orderIndex];
    }
    return sorderStr;
}

// 权重数值
private final static double weightsNum = 53;

/**
 * for 计算字符串的权重值算法
 * @param deep
 * @param str
 * @return weights
 */
public static double getStrWeights(String str,int deep) {
    int c = str.charAt(deep);

    boolean isUppercase = true;
    if(c >= 97) {
        c = c - 32;
        isUppercase = false;
    }
    c = c - 64; // A,a -> 1; B,b -> 2

    int molecular = c*2; 
    if(isUppercase) molecular--; //if(B) -> 3;if(b) -> 4; for end [Baby,baby]

    // 这里考虑了大小写 如果字母是B 权重=3/53 小写b 权重=4/53  使小大小写也能排序

    double weights =  molecular	/ (Math.pow(weightsNum, deep));


    return ++deep >= str.length() ? weights : weights + getStrWeights(str,deep); //递归到字符串末尾
}

package javabasis.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeMap;

/**
 * 字段排序算法
 * 
 * @author Narule
 *
 */

public class StringAlgorithm {

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

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

			list = treeMap.get(cTag);
			if (list == null) {
				list = new ArrayList<>(1);
			}
			list.add(str);
			treeMap.put(cTag, list);
		}

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

				if (list.size() < 2) { // 如果只有一个字符串，不需要递归
					for (String string : list) {
						orderly[index] = string;
						index++;
					}
				} else { // 如果有两个以上字符串，开头字母相同，可能需要递归排序
					ArrayList<String> arrayList = new ArrayList<>(0);
					for (String string : list) {
						if (string.length() > 1) { // 字符串长度大于2的，需要添加到list,准备下一次递归排序用到
							arrayList.add(string.substring(1));
						} else {
							orderly[index] = string;
							index++;
						}
					}
					if (arrayList.size() > 1) {
						String[] array = new String[arrayList.size()];
						int i = 0;
						for (String string : arrayList) {
							array[i] = string;
							i++;
						}
						array = nopTop(array); // 还需要递归排序 back background -> ack ackground
						for (String string : array) {
							orderly[index] = cTag + string;
							index++;
						}
					} else if (arrayList.size() == 1) {
						orderly[index] = cTag + arrayList.get(0);
						index++;
					}
				}
			}

		}
		treeMap.clear();
		return orderly; // 排序后的字符串数组
	}

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

	}
}