对数组元素进行排序（包含数字的字符串），自然排序

Question

我有一个类似于这样的数组：

["IL0 Foo", "PI0 Bar", "IL10 Baz", "IL3 Bob says hello"]

需要对它进行排序，以便它看起来像这样;

["IL0 Foo", "IL3 Bob says hello", "IL10 Baz", "PI0 Bar"]

我尝试了一个排序函数;

function compare(a,b) {
  if (a < b)
     return -1;
  if (a > b)
    return 1;
  return 0;
}

但这会给出命令

["IL0 Foo", "IL10 Baz", "IL3 Bob says hello", "PI0 Bar"]

我已经尝试想出一个正则表达式，但是无法理解它。
如果有帮助的话，格式总是2个字母，x个数字，然后任意数量的字符。

- Rooneyl

---

先字母还是数字？ - Brad Christie

@BradChristie，是的，按前两个字母和数字排序，其他字符不是必需的（但最好有）。 - Rooneyl

在理想的世界中，IL10 Bob。 - Rooneyl

@RyanGates 除此之外，这并不是按字母顺序排序，并且与DOM中的元素无关。 - Anthony Grist

这回答您的问题吗？Javascript：字母数字字符串的自然排序 - Ivar

Answer 1

这被称为“自然排序”，可以在JS中这样实现：

function naturalCompare(a, b) {
    var ax = [], bx = [];

    a.replace(/(\d+)|(\D+)/g, function(_, $1, $2) { ax.push([$1 || Infinity, $2 || ""]) });
    b.replace(/(\d+)|(\D+)/g, function(_, $1, $2) { bx.push([$1 || Infinity, $2 || ""]) });
    
    while(ax.length && bx.length) {
        var an = ax.shift();
        var bn = bx.shift();
        var nn = (an[0] - bn[0]) || an[1].localeCompare(bn[1]);
        if(nn) return nn;
    }

    return ax.length - bx.length;
}

/////////////////////////

test = [
    "img12.png",
    "img10.png",
    "img2.png",
    "img1.png",
    "img101.png",
    "img101a.png",
    "abc10.jpg",
    "abc10",
    "abc2.jpg",
    "20.jpg",
    "20",
    "abc",
    "abc2",
    ""
];

test.sort(naturalCompare)
document.write("<pre>" + JSON.stringify(test,0,3));

要按相反的顺序排序，只需交换参数：

test.sort(function(a, b) { return naturalCompare(b, a) })

或者简单地说

test = test.sort(naturalCompare).reverse();

- georg

---

似乎更喜欢以字母字符开头的字符串而不是数字字符。通过将“$1 || 0”替换为“typeof($1) == 'undefined' ? Infinity : $1”来修复。 - colllin

有人能帮忙实现对数组进行升序和降序排序吗？ - anusreemn

请注意，.reverse 将再次迭代数组。 - Rafael Herscovici

有人能详细解释一下正则表达式替换/无穷大的情况吗？然后是带有移位机制的while循环？我不完全理解那里发生了什么。 - DRobertE

我只是想问一下，对于时间空间复杂度/大O表示法，这将是O(n)对吗？ - Malcolm Salvador

如果您还希望排序不区分大小写，可以将分配nn的行替换为var nn = (an[0] - bn[0]) || an[1].localeCompare(bn[1], undefined, {sensitivity: 'base'});。 - Tim Angus

Answer 2

您可以使用 String#localeCompare 与 options。

sensitivity

哪些字符串差异应导致非零结果值。可能的值为：

• "base"：仅以基础字母不同的字符串比较为不相等。例如：a ≠ b，a = á，a = A。
• "accent"：仅以基础字母或重音和其他变音符号不同的字符串比较为不相等。例如：a ≠ b，a ≠ á，a = A。
• "case"：仅以基础字母或大小写不同的字符串比较为不相等。例如：a ≠ b，a = á，a ≠ A。
• "variant"：具有基础字母、重音和其他变音符号或大小写不同的字符串比较为不相等。其他差异也可能被考虑。例如：a ≠ b，a ≠ á，a ≠ A。

对于 "sort" 的用法来说，默认值为 "variant"；对于 "search" 的用法来说则取决于地区设置。

numeric

是否应该使用数字排序，即 "1" < "2" < "10"。可能的值为 true 和 false；默认值为 false。可以通过 options 属性或 Unicode 扩展键设置此选项；如果两者都提供，则 options 属性优先。实现不需要支持此属性。

var array = ["IL0 Foo", "PI0 Bar", "IL10 Baz", "IL3 Bob says hello"];

array.sort(function (a,b) {
    return a.localeCompare(b, undefined, { numeric: true, sensitivity: 'base' });
});

console.log(array);

- Nina Scholz

---

如果数组包含未定义或空值，它会起作用吗？我猜它会忽略它们，而不是根据排序类型将它们放在前面或后面。 - Umang

很抱歉，@Umang，localeCompare仅适用于字符串。参数会被转换为字符串。 - Nina Scholz

Answer 3

var re = /([a-z]+)(\d+)(.+)/i;
var arr = ["IL0 Foo", "PI0 Bar", "IL10 Baz", "IL3 Bob says hello"];
var order = arr.sort( function(a,b){
    var ma = a.match(re),
        mb = b.match(re),
        a_str = ma[1],
        b_str = mb[1],
        a_num = parseInt(ma[2],10),
        b_num = parseInt(mb[2],10),
        a_rem = ma[3],
        b_rem = mb[3];
    return a_str > b_str ? 1 : a_str < b_str ? -1 : a_num > b_num ? 1 : a_num < b_num ? -1 : a_rem > b_rem;  
});

- epascarello

Answer 4

给字符串中的数字加前导零，然后进行正常排序。

var naturalSort = function (a, b) {
    a = ('' + a).replace(/(\d+)/g, function (n) { return ('0000' + n).slice(-5) });
    b = ('' + b).replace(/(\d+)/g, function (n) { return ('0000' + n).slice(-5) });
    return a.localeCompare(b);
}

var naturalSortModern = function (a, b) {
    return ('' + a).localeCompare(('' + b), 'en', { numeric: true });
}

console.dir((["IL0 Foo", "PI0 Bar", "IL10 Baz", "IL3 Bob says hello"].sort(naturalSort)));

console.dir((["IL0 Foo", "PI0 Bar", "IL10 Baz", "IL3 Bob says hello"].sort(naturalSortModern)));

- axfree

Answer 5

我非常喜欢georg的解决方案，但是我需要下划线（“_”）在数字之前排序。这是我修改他的代码的方法：

var chunkRgx = /(_+)|([0-9]+)|([^0-9_]+)/g;
function naturalCompare(a, b) {
    var ax = [], bx = [];
    
    a.replace(chunkRgx, function(_, $1, $2, $3) {
        ax.push([$1 || "0", $2 || Infinity, $3 || ""])
    });
    b.replace(chunkRgx, function(_, $1, $2, $3) {
        bx.push([$1 || "0", $2 || Infinity, $3 || ""])
    });
    
    while(ax.length && bx.length) {
        var an = ax.shift();
        var bn = bx.shift();
        var nn = an[0].localeCompare(bn[0]) || 
                 (an[1] - bn[1]) || 
                 an[2].localeCompare(bn[2]);
        if(nn) return nn;
    }
    
    return ax.length - bx.length;
}

/////////////////////////

test = [
    "img12.png",
    "img10.png",
    "img2.png",
    "img1.png",
    "img101.png",
    "img101a.png",
    "abc10.jpg",
    "abc10",
    "abc2.jpg",
    "20.jpg",
    "20",
    "abc",
    "abc2",
    "_abc",
    "_ab_c",
    "_ab__c",
    "_abc_d",
    "ab_",
    "abc_",
    "_ab_cd",
    ""
];

test.sort(naturalCompare)
document.write("<pre>" + JSON.stringify(test,0,3));

- Chaim Leib Halbert

Answer 6

您可以使用以下正则表达式来获取字符串的非数字和数字部分：

var s = "foo124bar23";
s.match(/[^\d]+|\d+/g)

返回：["foo", "124" , "bar" , "23"]

然后在您的比较函数中，您可以遍历两个字符串的部分逐个进行比较。第一个不匹配的部分确定了整体比较的结果。对于每个部分，检查该部分是否以数字开头，如果是，则在比较之前将其解析为数字。

- Tim Goodman

Answer 7

添加另一种选择（为什么不呢）：

var ary = ["IL0 Foo", "PI0 Bar", "IL10 Hello", "IL10 Baz", "IL3 Bob says hello"];

// break out the three components in to an array
// "IL10 Bar" => ['IL', 10, 'Bar']
function getParts(i){
    i = i || '';
    var parts = i.match(/^([a-z]+)([0-9]+)(\s.*)$/i);
    if (parts){
        return [
            parts[1],
            parseInt(parts[2], 10),
            parts[3]
        ];
    }
    return []; // erroneous
}
ary.sort(function(a,b){
    // grab the parts
    var _a = getParts(a),
        _b = getParts(b);

    // trouble parsing (both fail = no shift, otherwise
    // move the troubles element to end of the array)
    if(_a.length == 0 && _b.length == 0) return 0;
    if(_a.length == 0) return -1;
    if(_b.length == 0) return 1;

    // Compare letter portion
    if (_a[0] < _b[0]) return -1;
    if (_a[0] > _b[0]) return 1;
    // letters are equal, continue...

    // compare number portion
    if (_a[1] < _b[1]) return -1;
    if (_a[1] > _b[1]) return 1;
    // numbers are equal, continue...

    // compare remaining string
    if (_a[2] < _b[2]) return -1;
    if (_a[2] > _b[2]) return 1;
    // strings are equal, continue...

    // exact match
    return 0;
});

jsfiddle example

的英译中文为：

{{链接1：jsfiddle示例}}

。

- Brad Christie

Answer 8

不太美观，但是检查前两个字符代码。如果全部相等，则解析并比较数字：

var arr = ["IL0 Foo", "IL10 Baz", "IL3 Bob says hello", "PI0 Bar"];
arr.sort(function (a1, b1) {
    var a = parseInt(a1.match(/\d+/g)[0], 10),
        b = parseInt(b1.match(/\d+/g)[0], 10),
        letterA = a1.charCodeAt(0),
        letterB = b1.charCodeAt(0),
        letterA1 = a1.charCodeAt(1),
        letterB1 = b1.charCodeAt(1);
    if (letterA > letterB) {
        return 1;
    } else if (letterB > letterA) {
        return -1;
    } else {
        if (letterA1 > letterB1) {
            return 1;
        } else if (letterB1 > letterA1) {
            return -1;
        }
        if (a < b) return -1;
        if (a > b) return 1;
        return 0;
    }
});

示例

- Joe

---

给我这个顺序：["IL0 Foo", "IL10 Baz", "IL3 Bob says hello", "PI0 Bar"]。IL3 应该是第二个元素。 - Rooneyl