很多程序员不用js自带的sort函数而要自己手写排序呢?
看了很多js排序代码,为什么很多程序员不用js自带的sort函数而要自己手写排序呢?
首先这个想法,肯定是很多人都有的,也是特别正常的,就好比我们看到一辆跑车
第一时间,想到的能不能买地起~
如果买了,第一时间肯定是看开的爽不爽,后头率高不高~
但是作为一名工程师,研发汽车那种,可能会想到这辆车的内部结构,是几座的、发动机是哪个厂家的、百公里加速需要几秒、自主研发大概需要多久……
考虑的内容会很不一样,下面我们回到正题。 排序
js自带的是sort排序,这个排序也特别好用,普通人用sort能实现效果就可以了,更加资深或者想变成资深的程序员,可能会思考sort是怎么写的呢、内部是怎么实现的、性能是不是真的高、能不能适应所有场景......
那么接下来 我们来看看这个sort。
其内部原理,首先:内部利用递归进行比较,例如: let list = [1,3,4,2]
比较的逻辑为:
第一轮
1和3比 ->[1,3,4,2]
1和4比 ->[1,3,4,2]
1和2比 ->[1,3,4,2]
第二轮
3和4比 ->[1,3,4,2]
3和2比 ->[1,2,4,3]
第三轮
4和3比 ->[1,2,3,4]
其次,里面会有一个compare方法,用来比较两个值,判断两个值的大小,然后交换。 测试sort的性能问题
先准备一个1到10000的集合: let list = [] for(let i=0;i<10000;i++){ list.push(i) }
再将数组乱序排序,这里就可以用sort来排序。我们声明了一个count来计数,得到的结果是114434次。 let count = 0 list.sort(()=>{ count++ return Math.random()-0.5 }) console.log(count)
我们在用自己封装的洗牌算法来进行一次,得到的计算是 10000次数。 function shuffle(arr) { let count = 0; for (let i = arr.length - 1; i >= 0; i--) { count++; let rIndex = Math.floor(Math.random() * (i + 1)); let temp = arr[rIndex]; arr[rIndex] = arr[i]; arr[i] = temp; } console.log(count); return arr; } shuffle(list)
得到的结论是 :用sort来进行的乱序排列,和自己封装的排序,性能上相差10倍,并且随着 数据量越大,sort性能相对会弱一点。
补充一下,算法的复杂度: O (log n) 对数时间 二分查找 O (n) 线性时间 简单的循环查找 O(n*logn) 快速排序 O(n2) n的平方 选择排序 O(n!) 排列组合
可以根据实际情况,进行使用,选择使用。
算法的速度:不是指时间,而是操作数的。
得到同样的结果,循环比较的次数越低,其性能越好。
所以在前端领域,我们对于算法的要求会越来越高,甚至有些地方的算法难度会超过后端,比如js的人脸识别等。