文件名排序算法分析

要解决的问题

用户在上传海量图片的时候，我们希望提供能够根据图片文件名进行正序/逆序排序的功能。

但是，传统的localeCompare方法，在面对包含数字和字符的字符串数组的排序时，会遇到如下问题：

var source = ['0509_1.jpg', '0509_2.jpg', '0509_11.jpg']

经过localeCompare()排序后，会变成

var result = ['0509_1.jpg', '0509_11.jpg', '0509_2.jpg']

显然这不是我们想要的结果

natsort库分析

幸运地，我们在github上找到一个成熟的排序库natsort。

该算法中，最重要的就在于正则表达式的构建，才能准确地将数字从字符串中识别并分离出来。

下面我们分析一下它的源码，一起学习一下如何正确地比较两个字符串的大小。

Step1: 去掉空格

var tre = /^\s+|\s+$/g

function replaceWhiteSpace (s) {
  return ('' + s).replace(tre, '');
}

Step2: 将包含的数字部分进行拆分

var nre = /(0x[\da-fA-F]+|(^[\+\-]?\d+(?:\.\d*)?(?:[eE][+\-]?\d+)?(?=\D|\s|$))|\d+)/g

function splitString (s) {
  return s.replace(nre, '\0$1\0')
          .replace(/\0$/, '')
          .replace(/^\0/, '')
          .split('\0')
}

Step3: 判断是否为Hex或者日期

var hre = /^0x[0-9a-f]+$/i

function parseHex (s) {
  return parseInt(s.match(hre), 16) || null
}

var dre = /(^([\w ]+,?[\w ]+)?[\w ]+,?[\w ]+\d+:\d+(:\d+)?[\w ]?|^\d{1,4}[\/\-]\d{1,4}[\/\-]\d{1,4}|^\w+, \w+ \d+, \d{4})/

function parseDatetime (s) {
  return s.match(dre) && Date.parse(s) || null
}

Step4: 对已拆分的两个数组进行比较

代码就不贴出来了，大概的思路就是：

1. 遍历两个数组，对其中的数字转换为字符串；
2. 对转换出来的字符串使用localeCompare进行比较；

用法

参见natsort