算法：文件名排序 - 哈喽比特 - https://www.hellobit.com.cn

445次阅读 | 发布于3年以前

1、背景

一般来说对文本进行排序的时候使用文本字符的 ASCII 码即可，但是对于文件名称排序，当文件名中包含数字的时候排序实现起来会有所区别：

当数字签名的字符串相同的时候需要比较数字大小；
当数字以 0 开头的时候需要将前缀 0 忽略掉，所以无法使用 ASCII 排序。

比如文件名列表，

A__01__02, A__2__02, A__1__23, A__11__23, A__3++++, 
B__1__02, B__22_13, 1_22_2222, 12_222_222, 2222222222,
1.sadasdsadsa, 11.asdasdasdasdasd, 2.sadsadasdsad, 22.sadasdasdsadsa,
3.asdasdsadsadsa, adsadsadsasd1, adsadsadsasd10, adsadsadsasd3,
adsadsadsasd02

的排序结果是，

Win10 中的排序结果

2、两种思路

2.1 先使用正则表达式分割再比较

第一种思路是采用正则表达式将字符串中的数字和文本分开，缓存到本地数据对象的列表中，然后在排序的时候再根据列表的顺序从队首到队尾依次进行比较，

public class FileNameComparatorByRegex implements Comparator<FileNameComparatorByRegex.StringWithRegex> {

    // 测试
    public static void main(String...args) {
        Pattern p = Pattern.compile("[^\\d]+|\\d+");
        Matcher m = p.matcher("0asd123sad45678");
        while (m.find()) {
            String s = m.group();
            System.out.print(s + " ");
        }
    }

    @Override
    public int compare(StringWithRegex left, StringWithRegex right) {
        int pos = 0;
        String leftPart = safeGet(left.parts, pos);
        String rightPart = safeGet(right.parts, pos);
        while (leftPart != null && rightPart != null) {
            int compareResult = leftPart.compareTo(rightPart);
            if (compareResult != 0)
                return compareResult;
            pos++;
            leftPart = safeGet(left.parts, pos);
            rightPart = safeGet(right.parts, pos);
        }
        if (leftPart == null && rightPart == null)
            return 0;
        return leftPart == null ? 1 : -1;
    }

    private static final Pattern PATTERN = Pattern.compile("[^\\d]+|\\d+");

    public static List<StringWithRegex> covert(List<String> list) {
        List<StringWithRegex> ret = new ArrayList<>(list.size());
        list.forEach(s -> {
            List<String> parts = getParts(s);
            StringWithRegex regex = new StringWithRegex(parts, s);
            ret.add(regex);
        });
        return ret;
    }

    private static String safeGet(List<String> list, int position) {
        if (position >= list.size()) return null;
        return list.get(position);
    }

    private static List<String> getParts(String from) {
        List<String> parts = new ArrayList<>(8);
        Matcher m = PATTERN.matcher(from);
        while (m.find()) {
            String s = m.group();
            parts.add(s);
        }
        return parts;
    }

    public static class StringWithRegex {
        private List<String> parts;
        private String original;

        public StringWithRegex(List<String> parts, String original) {
            this.parts = parts;
            this.original = original;
        }

        public String getOriginal() {
            return original;
        }
    }
}

这里提供了 covert() 方法用于将文件名 String 映射为 StringWithRegex 类型。这里采用正则表达式分割的方式，使用数字将字符串分割并将其存储到 StringWithRegex 的 parts 中。

当进行比较的时候从 parts 的第 0 位开始依次进行比较，当比较结果不为 0 或者某一方达到末尾的时候说明比较到了终点，返回结果即可。

上面的算法存在一点瑕疵，实际上上面在比较数字字符串的时候使用的是字符的 ASCII 码，但是假如某个数字字符串以 0 开头，此时会出现，比如 011 小于 02 的情况。所以，上面分割之后还需要做数组的移除首位 0 字符的处理。由于性能问题，这个算法不是我们介绍的重点。

2.2 使用字符逐位进行比较

另一种实现方式是采用字符串逐位进行比较的方式。在这种实现方式中，每当遇到一个字符的时候，我们需要根据字符是数字还是字符进行处理。这种方式实现代码如下，

public class FileNameComparatorByChar implements Comparator<String> {

    private static final int SPAN_OF_CASES = 'a' - 'A';

    private final boolean caseSensitive;

    public FileNameComparatorByChar(boolean caseSensitive) {
        this.caseSensitive = caseSensitive;
    }

    @Override
    public int compare(String left, String right) {
        char[] csLeft = left.toCharArray(), csRight = right.toCharArray();
        int diff, i=0, j=0, lenLeft=csLeft.length, lenRight=csRight.length;
        char cLeft, cRight;
        for (; i<lenLeft && j<lenRight; i++, j++) {
            cLeft = getCharByCaseSensitive(csLeft[i]);
            cRight = getCharByCaseSensitive(csRight[j]);
            boolean isNumberLeft = isNumeric(cLeft);
            boolean isNumberRight = isNumeric(cRight);
            // Remove prefix '0', should keep the last number.
            if (isNumberLeft && (i == 0 || !isNumeric(csLeft[i-1]))) {
                while (i < lenLeft-1 && cLeft == '0' && /* keep at lease one 0, for case 000 */ isNumeric(csLeft[i+1])) {
                    cLeft = getCharByCaseSensitive(csLeft[++i]);
                }
                isNumberLeft = isNumeric(cLeft);
            }
            if (isNumberRight && (j == 0 || !isNumeric(csRight[j-1]))) {
                while (j < lenRight-1 && cRight == '0' && isNumeric(csRight[j+1])) {
                    cRight = getCharByCaseSensitive(csRight[++j]);
                }
                isNumberRight = isNumeric(cRight);
            }
            diff = cLeft - cRight;
            if (diff != 0) {
                if (isNumberLeft && isNumberRight) {
                    // The longer one is bigger.
                    int leftNumberLengthLeft = leftNumberLength(csLeft, i);
                    int leftNumberLengthRight = leftNumberLength(csRight, j);
                    int lengthDiff = leftNumberLengthLeft-leftNumberLengthRight;
                    if (lengthDiff != 0) {
                        return lengthDiff > 0 ? 1 : -1;
                    } // Else, same length, use diff.
                } else if (isNumberLeft != isNumberRight) {
                    boolean isNumberLastLeft = isNumberLast(csLeft, i);
                    boolean isNumberLastRight = isNumberLast(csRight, j);
                    // The last two chars should be the same, if not, they might be prefix '0' and '1' etc.
                    boolean isNumberLast = isNumberLastLeft && isNumberLastRight;
                    return isNumberLast ? (isNumberLeft ? 1 : -1) : (isNumberLeft ? -1 : 1);
                }
                // If diff not equal 0, it's sure to return.
                return diff;
            }
        }
        // At lease one of two strings hit the end. The longer is greater.
        boolean isLeftEnd = i == lenLeft;
        boolean isRightEnd = i == lenLeft;
        if (i == lenLeft) i--;
        if (j == lenRight) j--;
        return isLeftEnd && isRightEnd
                ? (csLeft[i] - csRight[j])
                : (isLeftEnd ? -1 : 1);
    }

    private boolean isNumeric(char c) {
        return c >= '0' && c <= '9';
    }

    private int leftNumberLength(char[] arr, int current) {
        int left = 0;
        for (int i=current+1, len=arr.length; i<len; i++) {
            if (isNumeric(arr[i])) {
                left++;
            }
        }
        return left;
    }

    private boolean isNumberLast(char[] arr, int current) {
        if (current <= 0) return false;
        return isNumeric(arr[current-1]);
    }

    private char getCharByCaseSensitive(char c) {
        return caseSensitive ? c : (c >= 'A' && c <= 'Z' ? (char) (c + SPAN_OF_CASES) : c);
    }
}

这里的实现思路是：

对参与比较的两个字符串对应的数组从位置 0 开始逐个字符进行比较。
当参与对比的两个数字都是数字的时候，首先做移除数字字符串前面的数字字符的操作。这里做移除操作的时候判断条件比较多，主要是为了处理各种情况，比如 ‘000’ 就需要保留一个至少一个 '0' 字符等。
然后计算下此时两个字符的差值，如果两个字符相等，那么比较下一个字符即可；如果两个字符不相等，那么：
如果当前参与比较的两个字符都是数字，那么我们通过比较其分别剩余的数字字符串长度作为他们大小的判断依据，即剩余数字长度比较多的字符串比较大，比如 1234 和 124；如果两个相等，说明当前的位可以作为其大小判断依据，比如 1234 和 1235.
如果当前参与比较的一方是数字。首先，比较到了这一位说明前面的前一位字符是相等的，或者一方是 0 另一方是字符。对于两个都是数字的情况，为数字的较大，比如 '15' 和 '1c'；如果两个都是字符或者其中一方为 0，那么为数字的较小，比如 'a5' 和 ‘ac’ 以及 ‘b05’ 和 'bc'。
最后是两个都是字符的情况，此时比较两者大小即可。
如果从上述循环中跳出，那么意味着至少其中某一方遍历到了数组末尾，并且此前的内容相等。此时又分成几种情况：
如果两个都到了末尾，那么比较当前字符大小即可。
如果其中一方到了末尾，那么没有到末尾的那个字符串（较长的），比较大。

3、总结

使用正则表达式的方式思路更加简洁一些，并且因为提前对数据做了缓存，所以当参与比较的数据量特别大的时候比较有优势。这体现的是空间换时间的思想。第二种实现方式中，判断条件比较多，需要做大量的数据测试，否则容易出现如下异常，

java.lang.IllegalArgumentException: Comparison method violates its general contract

所以，写诸如此类的算法的时候，除了逻辑的梳理，多 mock 数据做数据测试也是很有必要的。