前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >前端常见排序方式及其性能比较

前端常见排序方式及其性能比较

作者头像
一粒小麦
发布2020-07-10 12:42:09
1.2K0
发布2020-07-10 12:42:09
举报
文章被收录于专栏:一Li小麦

前端常见排序方式及其性能比较


这是笔者正在进行中的前端基础项目的实验性探究之一。

实验方法:随机生成1000条(0-999)整数数据。分别对其在不同数据量进行排序10次。统计平均时间。

1. 冒泡排序

无论学习什么编程语言,接触到的第一种排序算法应该就是冒泡排序。这里借用了一张动画进行说明。

1.相邻两个数两两相比,n[i]跟n[j+1]比,如果n[i]>n[j+1],则将两个数进行交换,2.j++, 重复以上步骤,第一趟结束后,最大数就会被确定在最后一位,这就是冒泡排序又称大(小)数沉底,3.i++,重复以上步骤,直到结束,排序完成。

由此可写出排序的js代码:

代码语言:javascript
复制
const sort = (function () {    return {        // 冒泡排序        buble(data) {            for (let i = 0; i < data.length; i++) {                for (let j = 0; j < data.length - i; j++) {                    if (data[j] > data[j + 1]) {                        let tmp = data[j];                        data[j] = data[j + 1];                        data[j + 1] = tmp;                    }                }            }
            return data;        }}

网上还有采用es6解构来表达交换位置的写法,看起来很优雅:

代码语言:javascript
复制
        // 冒泡排序2        buble2(data) {            for (let i = 0; i < data.length ; i++) {                for (let j = 0; j < data.length - i; j++) {                    if (data[j] > data[j + 1]) {                        [data[j], data[j + 1]] = [data[j + 1], data[j]] /*交换元素*/                    }                    //console.log(data)                }            }
            return data;        },

那我们也把它纳入到sort类中,计算一下:

数据量

buble排序用时(ms)

buble2排序用时(ms)

1000

7.9

15.8

5000

77.3

90.1

10000

321.4

342.1

25000

2097.7

2118.1

100000

34270.6

未测

125000

54216.5

未测

625000

爆栈

未测

可见buble2中es6+ 的写法,在耗时方面的性能表现稍差。接下来涉及数组互换的内容将采用传统的写法。

buble排序与数据量自然对数(lnN)与时间做拟合:

也就说 冒泡排序 平均耗费时间 t 与 数据量 N 关系大致为

【注】此处拟合仅代表基本趋势分析,难以体现时间复杂度的准确关系。下同。

2. 选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

•初始状态:无序区为R[1..n],有序区为空;•第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;•n-1趟结束,数组有序化了。

javascript 的实现如下:

代码语言:javascript
复制
// 选择排序select(data) {    for (let i = 0; i < data.length; i++) {        for (let j = i; j < data.length; j++) {            if (data[i] > data[j]) {                let tmp = data[i];                data[i] = data[j];                data[j] = tmp;             }        }    }
    return data;}

数据量

select排序用时(ms)

1000

7.2

5000

47.0

10000

148.3

25000

786.8

100000

11480.8

125000

17882.6

625000

未全测 440s左右

也就说 因此选择排序 耗费时间 t 与 数据量 N 关系大致为

选择排序也是表现最稳定的排序算法之一,无论什么数据进去都是O(n2)的时间复杂度,不占用额外的内存空间,适用较小规模的数据排序。

3. 插入排序

插入排序核心--扑克牌思想:就想着自己在打扑克牌,接起来一张,放哪里无所谓,再接起来一张,比第一张小,放左边,继续接,可能是中间数,就插在中间....

简单来讲就是以第一个插入的数为基数,小的往左放大的往右放,然后不断循环基数如果第一个最小,那么就从第二个开始比较,依次循环。

在这里,有序区范围不断扩大。等“完全占领”无序区,就排好了。

JavaScript实现方案如下

代码语言:javascript
复制
// 插入排序(扑克牌法)insert(data) {    for (let i = 1; i < data.length; i++) {        for (let j = i; j > 0; j--) {            if (data[j] < data[j - 1]) {                let tmp = data[j];                data[j] = data[j - 1];                data[j - 1] = tmp;            }else{                break;            }        }    }
    return data;},

运行测试结果

数据量

insert排序用时(ms)

1000

6.1

5000

28.6

10000

97.5

25000

587.3

100000

9291.7

125000

14520.5

625000

未测

也就说 因此插入排序 平均耗费时间 t 与 数据量 N 关系大致为

4. 快速排序

前面的比较在快速排序面前看来,就显得是菜鸡互啄了。

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

算法描述 快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

从数列中挑出一个元素,称为 “基准”(pivot);重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码语言:javascript
复制
// 快速排序quick(arr) {    if(arr.length <= 1) {        return arr;  //递归出口    }    var left = [],        right = [],        current = arr.splice(0,1); //注意splice后,数组长度少了一个    for(let i = 0; i < arr.length; i++) {        if(arr[i] < current) {            left.push(arr[i])  //放在左边        } else {            right.push(arr[i]) //放在右边        }    }    // console.log(this)    return this.quick(left).concat(current,this.quick(right)); //递归}

运行测试结果

数据量

quick排序用时(ms)

1000

11.1

5000

35.7

10000

80.0

25000

279.0

100000

2878.3

125000

4255.8

625000

97497.3

在拟合方案上,采用二项式建模

也就说 因此快速排序 平均耗费时间 t 与 数据量N的大致关系为

结论

在综合各个算法理论上的时间复杂度后,汇总得表:

不考虑机器性能,在较少数据量(小于10000)时,插入排序可以获得比较好的效果。在数据量较多时,快速排序的时间处理效率优势明显。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-07-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 一Li小麦 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前端常见排序方式及其性能比较
    • 1. 冒泡排序
      • 2. 选择排序
        • 3. 插入排序
          • 4. 快速排序
            • 结论
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档