如何对字符串版本号构成的数组进行排序？

[hengg]

在 segmentfault 有一个经典的面试题：

有一组版本号如下['0.1.1', '2.3.3', '0.302.1', '4.2', '4.3.5', '4.3.4.5']。

现在需要对其进行排序，排序的结果为 ['4.3.5','4.3.4.5','2.3.3','0.302.1','0.1.1']

问题链接

其中 zzgzzg00 的回答大意如下，非常简洁也非常有意思：

const arr=['0.1.1', '2.3.3', '0.302.1', '4.2', '4.3.5', '4.3.4.5'];
arr.sort((a,b)=>a>b?-1:1);
console.log(arr); // ['4.3.5','4.3.4.5','2.3.3','0.302.1','0.1.1']

于是问题来了：

为什么字符串比较能够轻松的实现排序？

在JavaScript中，字符串之间无疑也是可以比较的。猜猜看下面这段代码输出的结果是什么？

console.log('5'>'1')
console.log('5'>'10')

答案是true、true。

比较字符串是比较它们的 Unicode 值

这是因为在两个字符串进行比较时，是使用基于标准字典的 Unicode 值来进行比较的。通过String.prototype.codePointAt()方法我们能拿到字符串的 Unicode 值。所以'5'>'1'的结果是true;

而当字符串长度大于1的时候比较则是逐位进行，因此'5'>'10'进行比较时，首先比较第一位也就是'5'>'1'，如果有结果则返回，没有结果则继续比较第二位。所以'5'>'10'的结果与'5'>'1'相同，也是true。

回过头来看问题，就不难理解了：.的 Unicode 值为 46，0的 Unicode 值为 48，其它数字在此基础上递增。所以在比较的时候10.1是要大于1.1的。

字符串比较法适用范围很小

上文解释了为什么题目中的 case 能够通过字符串比较来实现。但是机智如你一定会发现，这种比较是存在问题的：如果修改题目中的arr如下:

const arr=[
    '0.5.1',
    '0.1.1',
    '2.3.3',
    '0.302.1',
    '4.2',
    '4.3.5',
    '4.3.4.5'
];

那字符串比较法会出错：期望中版本号'0.302.1'应该大于'0.5.1'，但实际比较的结果则是相反的，原因就在于逐位比较。

所以字符串比较这个技巧需要限定条件为各个版本号均为1位数字，它得出的结果才是准备的，而常见的版本号并不符合这个条件。那么有没有适用性更强又简洁的比较方式呢？

“大数”加权法

比较npm规则版本号

假设版本号遵循 npm 语义化规则，即版本号由MAJOR.MINOR.PATCH几个部分组成：：

const arr=['2.3.3', '4.3.4', '0.3.1'];

通过如下公式得出待比较的目标版本号：

MAJOR*p² + MINOR*p + PATCH

代码如下：

const p = 1000;
const gen = (arr) => 
    arr.split('.').reduce(reducer,0);

const reducer = (acc,value,index) => 
    acc+(+value)*Math.pow(p,arr.length-index-1);

arr.sort((a,b)=> gen(a)>gen(b)?-1:1);

console.log(arr)

其中p为常量，它的取值要大于MAJOR/MINOR/PATCH三者中最大值至少一个量级。譬如待比较的版本号为1.0.1、'0.302.1'，此时如果p取值为 10 那么计算出来的结果显然会不符合预期。而p取1000就能够避免各个子版本加权之后产生污染。

同理，有类似规则的版本号（如'1.0.1.12'）都可以通过上述方法进行排序。

更多的版本号

如果版本号数组如下:

const arr=[
    '1.1',
    '2.3.3',
    '4.3.5',
    '0.3.1',
    '0.302.1',
    '4.20.0',
    '4.3.5.1',
    '1.2.3.4.5'
];

上述数组不但不遵循MAJOR.MINOR.PATCH规则，其长度也没有明显的规则，这时该如何比较呢？

可以在固定规则比较的方法基础上进行扩展，首先需要获取到版本号数组中子版本号最多有几位maxLen。这里我们通过Math.max()获取：

const maxLen = Math.max(
    ...arr.map((item)=>item.split('.').length)
);

拿到maxLen之后即可改写 reducer 方法:

const reducer = (acc,value,index) => 
    acc+(+value)*Math.pow(p,maxLen-index-1);

const gen = (arr) =>
    arr.split('.').reduce(reducer,0);

arr.sort((a,b)=> gen(a)>gen(b)?-1:1);

console.log(arr)

上述方法足够用于常规版本号的比较了。但是我们知道，JavaScript 的 number 类型为双精度64位浮点类型，如果maxLen特别大、每一位的值又很大（比如某个子版本号用时间戳来标记），那么上述方法则存在溢出而导致比较结果不准确的问题。

不过BigInt提案已经进入stage3规范，它能够表示任意大的整数。可以预见的是，在不久的将来我们无需考虑版本号取值范围带来的影响。

循环比较法

相对字符串比较法和大数加权法，循环比较法的适用性更强。思路仍然是逐位比较子版本号：如果当前版本号相同则比较下一位；如果版本号位数不相等而前几位值一致则认为位数多的版本号大。

代码如下：

arr.sort((a, b) => {
    let i = 0;
    const arr1 = a.split('.');
    const arr2 = b.split('.');

    while (true) {
        const s1 = arr1[i];
        const s2 = arr2[i++];

        if (s1 === undefined || s2 === undefined) {
            return arr2.length - arr1.length;
        }

        if (s1 === s2) continue;

        return s2 - s1;
    }
});

console.log(arr)

思考

我们总结并且对比了几种用来比较版本号的方法，在不同的场景可以选择合适的方式：

• 字符串比较法
• 大数加权法
• 循环比较法

但是，我们知道生产环境中软件的版本号通常并不全由数组组成。比如我们可以在npm上发布诸如1.0.0-beta或者6.0.0-alpha等格式的包，此时该如何比较版本号？

[cMing1997]

文章比较久远，我还是刷到了 ，哈哈哈哈 😆 😆😆
对于 博主 的疑惑，我前段时间刚刷到一个视频，也是讲到了这个版本号比对
人家给出了一种解法，就是使用 Generator 去对版本号 进行解析

function* walk(str) {
    let part = '';
    let terminals = ['.', '-'];
    for (let i = 0; i < str.length; i++) {
        if (terminals.includes(str[i])) {
            yield part;
            part = '';
        } else {
            part += str[i];
        }
    }
    if (part) yield part;
}

然后拿到 解析之后的版本号 直接去去 value 进行比对，如果上一位相同，再比较下一位的，如果相同位的比出大小了，就不往下跑了，就可以直接抛出结果

如果是 数组 需要进行 版本号排序的话，那可以进行冒泡排序之类的操作，内部循环里面进行 版本号比对，进行位置替换

function sortTags(tags) {
    const length = tags.length;
    for (let i = 0; i < length - 1; i++) {
        for (let j = 0; j < length - i - 1; j++) {
            const walkPre = walk(tags[j])
            const walkNext = walk(tags[j + 1]);

            let pre = walkPre.next(), next = walkNext.next();
            let flag = false;
            while (!pre.done && !next.done) {  // 只比较相同位
                let preV = ~~pre.value;
                let nextV = ~~next.value;
                if (preV == nextV) {
                    // 同一位的版本相同，就继续比较
                    pre = walkPre.next();
                    next = walkNext.next();
                } 
               // 这里就可以扩展 博主所说的 beta 、alpha、 rc 之类的版本比对了
               else {
                    // 同一位版本比出大小，则停止本次循环
                    flag = preV > nextV;
                    break
                }
            }
            if (flag) {
                const temp = tags[j + 1];
                tags[j + 1] = tags[j];
                tags[j] = temp;

            }
        };
    };
    return tags;
}