乐趣区

关于javascript:面试官如何对字符串版本号构成的数组进行排序

jiezi

在 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*p2 + 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 ? -1 : 1;
    }
});

console.log(arr)

思考

咱们总结并且比照了几种用来比拟版本号的办法，在不同的场景能够抉择适合的形式：

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

然而，咱们晓得生产环境中软件的版本号通常并不全由数组组成。比方咱们能够在 npm 上公布诸如 1.0.0-beta 或者 6.0.0-alpha 等格局的包，此时该如何比拟版本号？置信聪慧而又怠惰的你肯定有本人的思路，无妨留言讨论一下。

退出移动版