有一组版本号如下['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']

参考答案

本题目的实现有很多不同的思路,在这里先给大家介绍一种非常简洁,也非常有意思的实现方案:

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')

答案是truetrue

比较字符串是比较它们的 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 那么计算出来的结果显然会不符合预期。而p1000就能够避免各个子版本加权之后产生污染。

同理,有类似规则的版本号(如'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)

思考

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

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

以上答案由 “前端面试题宝典” (官网地址:https://fe.ecool.fun/ )整理收集