首页 > 代码库 > JavaScript排序,不只是冒泡
JavaScript排序,不只是冒泡
做编程,排序是个必然的需求。前端也不例外,虽然不多,但是你肯定会遇到。
不过说到排序,最容易想到的就是冒泡排序,选择排序,插入排序了。
冒泡排序
依次比较相邻的两个元素,如果后一个小于前一个,则交换,这样从头到尾一次,就将最大的放到了末尾。
从头到尾再来一次,由于每进行一轮,最后的都已经是最大的了,因此后一轮需要比较次数可以比上一次少一个。虽然你还是可以让他从头到尾来比较,但是后面的比较是没有意义的无用功,为了效率,你应该对代码进行优化。
图片演示如下:
代码实现:
|
选择排序
选择排序我觉得是最简单的了,大一学VB的时候,就只记住了这个排序方法,原理非常简单:每次都找一个最大或者最小的排在开始即可。
首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
重复第二步,直到所有元素均排序完毕。
动图演示:
代码演示:
|
插入排序
插入排序也比较简单。就像打扑克一样,依次将拿到的元素插入到正确的位置即可。
将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
动图演示:
代码示例:
|
简单的代价是低效
上面三种都是非常简单的排序方法,简单的同时呢,效率也会比较低,还是拿这本书里的对比图来说明:
时间复杂度都高达 O(n^2) ,而它们后面的一些排序算法时间复杂度基本都只有 O(n log n) 。
我的强迫症又犯了,我想要高效率一点的排序方法。
归并排序
简单把这本书的内容过了一遍,当时就理解了这个归并排序,因此这里就谈一下这个归并排序吧。
基本原理是分治法,就是分开并且递归来排序。
步骤如下:
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
- 重复步骤 3 直到某一指针达到序列尾;
- 将另一序列剩下的所有元素直接复制到合并序列尾。
动图演示:
代码示例:
|
既然是个爱折腾的人,折腾了总得看看效果吧。
效率测试
由于我学这个来进行排序不是对简单数组,数组内都是对象,要对对象的某个属性进行排序,还要考虑升降序。
因此我的代码实现如下:
|
需要对哪个属性进行排序是不确定,可以随意指定,因此写成了参数。有由于不想让这些东西在每次循环都进行判断,因此代码有点冗余。
关于降序的问题,也没有加入参数中,而是简单的升序后再逆序输出。原因是不想让每次循环递归里都去判断条件,所以简单处理了。
下面就是见证效率的时候了,一段数据模拟:
|
实际测试来啦:
|
进行了五次,效果如下:
|
最低4倍,最高近16倍的效率之差还是比较满意的。
虽然 1000 条数据让前端排序的可能性不大,但是几十上百条的情况还是有的。另外由于node, JavaScript 也能运行的服务端了,这个效率的提升也还是有用武之地的。
一点疑问
归并排序里面使用了递归,在《数据结构与算法 JavaScript 描述》中,作者给出了自下而上的迭代方法。但是对于递归法,作者却认为:
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。
gitbook上这本书的作者对此有疑问,我也有疑问。
归并中虽然用了递归,但是他是放在 return 后的呀。关于在renturn后的递归是有尾递归优化的呀。
关于尾递归优化是指:本来外层函数内部再调用一个函数的话,由于外层函数需要等待内层函数返回后才能返回结果,进入内层函数后,外层函数的信息,内存中是必须记住的,也就是调用堆栈。而内部函数放在 return 关键字后,就表示外层函数到此也就结束了,进入内层函数后,没有必要再记住外层函数内的所有信息。
上面是我的理解的描述,不知道算不算准确。 chrome 下已经可以开启尾递归优化的功能了,我觉得这个递归是不该影响他在 JavaScript 下的使用的。
最后
有兴趣的话,推荐读读这本书,进行排序的时候,可以考虑一些更高效的方法。
不过需要注意的是,这些高效率的排序方法,一般都需要相对较多的额外内存空间,需要权衡一下。
另外,非常小规模的数据就没有必要了。一是影响太小,而是我们人的效率问题,一分钟能从头写个冒泡、选择、插入的排序方法,而换成是归并排序呢?
来自:http://blog.cdswyda.com/post/javascript/2017-03-22-js-sort-not-only-bubblesort
JavaScript排序,不只是冒泡