计算机中的字符串排序算法是直接比较字符的ASCII顺序,这样得出的排序结果有时候并不符合人类思维。比如下面这个文件名排序的例子。
一组文件1.jpg 2.jpg 10.jpg 100.jpg
,排序后会得到这样的结果1.jpg 10.jpg 100.jpg 2.jpg
,显然2没有10和100大,应该排在它们的前面才对。Windows资源管理器中的按名称排序就是这样实现的(Mac修正了这个问题)。
对字符串排序时能够智能地识别出其中的数字,归属于自然排序问题。对于自然排序问题,大多数编程语言都没有原生实现。PHP中有原生方法natsort()
和strnatcmp()
提供支持,但是JavaScript却无能为力。
localeCompare
方法可以按照本地语言习惯对字符串进行比较,能够实现汉字按音序排序,但是直接使用依然无法解决包含数字的字符串的自然排序问题。幸好,新的localeCompare
标准增加了numeric
属性,用于指定是否启用数字排序。虽然这一标准目前还没有得到所有浏览器的支持,但前景是好的,语法如下:
strA.localeCompare(strB, undefined, {numeric: true})
利用localeCompare
这个新特性,我们可以很容易实现包含数字的字符串的自然排序,代码如下。
function naturalCmp(a, b) {
return a.localeCompare(b, undefined, {numeric: true, sensitivity: 'base'});
}
var a = ["1.a", "100.a", "10.a", "2.a.10.b", "2.a.2.b"];
a.sort(naturalCmp);
// ["1.a", "2.a.2.b", "2.a.10.b", "10.a", "100.a"]
这种方法的局限性是,它只能分段识别字符串中的独立数字并进行比较,如果想更智能地区分浮点数、科学计数法或者日期的话,则可以使用这个javascript-natural-sort。
在收集资料的过程中发现,早在1997年,David Koelle实现了Alphanum
算法,解决了字母数字组合字符串的自然排序问题,相比上文localeCompare
的实现方式,该算法把点号无条件当做数字中的小数点来参与数值比较,而不是智能地适时当做分隔符来处理,最终的效果不尽完美。毕竟是20多年前的实现嘛,但该算法的思想还是很值得我们借鉴的。Brian Huisman基于该算法的JS实现代码摘录如下。
Array.prototype.alphanumSort = function(caseInsensitive) {
for (var z = 0, t; t = this[z]; z++) {
this[z] = new Array();
var x = 0, y = -1, n = 0, i, j;
while (i = (j = t.charAt(x++)).charCodeAt(0)) {
var m = (i == 46 || (i >=48 && i <= 57));
if (m !== n) {
this[z][++y] = "";
n = m;
}
this[z][y] += j;
}
}
this.sort(function(a, b) {
for (var x = 0, aa, bb; (aa = a[x]) && (bb = b[x]); x++) {
if (caseInsensitive) {
aa = aa.toLowerCase();
bb = bb.toLowerCase();
}
if (aa !== bb) {
var c = Number(aa), d = Number(bb);
if (c == aa && d == bb) {
return c - d;
} else return (aa > bb) ? 1 : -1;
}
}
return a.length - b.length;
});
for (var z = 0; z < this.length; z++)
this[z] = this[z].join("");
}
参考链接:MDN上的localeCompare文档 Alphanum Algorithm