探究Java自然排序算法

natSort

说明

现实生活中有很多场景需要用到“自然排序”的算法，比如对金钱表示的排序：“￥165.2，￥-365.03，￥+0.80”，还比如对日志文件名称排序“version1.0.log，version1.1.log1，version01.1.log2”等。这种情况下使用常规的字符串排序得到的结果是与实际业务不符合的，即使查阅了一些第三方的开源框架，也没有找到很好解决这个问题的方式（主要是业务性比较强），所以不得已自己花了些时间写了一个满足“自然排序”算法。

代码

/**
 * <自然排序算法>
 * <详细介绍>
 *
 * @author Uncle阳zzZ
 * @since 设计wiki | 需求wiki
 */
public class NatSortComparator implements Comparator<Object> {

    private boolean careCase = false;

    private Pattern patternA;
    private Pattern patternB;


    /**
     * careCase
     * @param careCase
     */
    public NatSortComparator(boolean careCase)  {
        this.careCase = careCase;

        String pattern = "(-|\\+)?\\d+(.\\d+)?"; //^
        patternA = Pattern.compile(pattern);
        patternB = Pattern.compile(pattern);
    }

    /**
     * 比较算法
     * @param a
     * @param b
     * @return
     */
    @Override
    public int compare(Object a, Object b) {

        // simple compare
        if (a == b) {
            return 0;
        }

        if (a == null) {
            return -1;
        }

        if (b == null) {
            return 1;
        }

        if (a.equals(b)) {
            return 0;
        }

        String strA = a.toString();
        String strB = b.toString();

        Matcher matcherA = patternA.matcher(strA);
        Matcher matcherB = patternB.matcher(strB);

        Map<Integer, Integer> indexMapA = new HashMap<Integer, Integer>();
        Map<Integer, Integer> indexMapB = new HashMap<Integer, Integer>();

        while (matcherA.find()) {
            indexMapA.put(matcherA.start(), matcherA.end());
        }

        while (matcherB.find()) {
            indexMapB.put(matcherB.start(), matcherB.end());
        }

        int iA = 0;
        int iB = 0;


        while (true) {

            Character cA = getCharacter(strA, iA);
            Character cB = getCharacter(strB, iB);

            while (isSpaceChar(cA)) {
                cA = getCharacter(strA, ++iA);
            }

            while (isSpaceChar(cB)) {
                cB = getCharacter(strB, ++iB);
            }

            if (indexMapA.containsKey(iA) && indexMapB.containsKey(iB)) {
                String tempA = strA.substring(iA, indexMapA.get(iA));
                String tempB = strB.substring(iB, indexMapB.get(iB));

                int compareResult = Double.compare(Double.parseDouble(tempA), Double.parseDouble(tempB));
                if (compareResult != 0) {
                    return compareResult;
                }

                iA = indexMapA.get(iA);
                iB = indexMapB.get(iB);

                continue;
            }

            if (cA == null && cB == null) {
                return 0;
            }

            if (cA == null) {
                return -1;
            }

            if (cB == null) {
                return 1;
            }

            if (!careCase) {
                cA = Character.toUpperCase(cA);
                cB = Character.toUpperCase(cB);
            }

            int tempResult = cA.compareTo(cB);
            if (tempResult != 0) {
                return tempResult;
            }

            ++iA;
            ++iB;
        }
    }


    /**
     * 获取字符
     * @param var
     * @param index
     * @return
     */
    private Character getCharacter(String var, int index) {
        if (var == null || index >= var.length()) {
            return null;
        }

        return var.charAt(index);
    }

    /**
     * 判断是否是空格
     * @param var
     * @return
     */
    private boolean isSpaceChar(Character var) {
        return var != null && Character.isSpaceChar(var);
    }

}

问题

由于把‘-’号和‘+’号作为了数字匹配的因素之一，所以在应对诸如时间格式如“2017-04-25”或者非数字语义的字符串如“中国-1个美丽的国度”时，会出现排序结果非我所愿的情况。看样子直接通过某一算法来达到完全智能的排序是不可能的，解决办法可以针对不同的业务场景来装配不同的比较器，或者用不同的Wrapper包装对象达到期望的结果。

github：https://github.com/zhencygo/java/tree/master/algorithm