我可能开发了世界上最快的通用排序算法,比快排快 60% | 您所在的位置:网站首页 › pid算法实现 › 我可能开发了世界上最快的通用排序算法,比快排快 60% |
在 Flutter ConstraintLayout 中用到了计数排序,众所周知,计数排序在某些场景下可以说是最快的排序算法,它有时甚至不需要元素间两两比较。但它有个最大的问题,它不通用!只适合对小范围的整数进行排序。 于是这段时间我一直在寻思着能不能改进它,让它通用呢,终于今天灵感爆发,我做到了! 因为我姓陈,所以我把它命名为 Chen Sort。看看它的性能表现吧: 空间复杂度恒为:O(n),时间复杂度为 O(nlogn),在最好的情况下,不需要元素间两两比较就能排好序。且它是稳定的。 性能测试众所周知全世界公认的最快的通用排序算法是快排,我们来和它做下性能对比吧,基准如下: 随机生成若干个范围为 [1,4294967296] 的正整数,使用 Chen Sort 和快排分别排序。 这里没有生成负数,负数性能会下降一些,但仍比快排快很多。 100 个随机数 100_compare.png平均快了 10%。 10000 个随机数 10000_compare.png平均快了 60% 多。 100000 随机数 100000_compare.png平均快了 80% 多。 1000000 随机数 1000000_compare.png平均快了 20% 左右。 目前的实现语言是 Dart,晚点用 Java 实现一下,并和 Tim Sort 做个对比。应该也会快很多。 代码已开源到 GitHub,目前放在 Flutter ConstraintLayout 的 example/chen_sort.dart 中,后续再把它抽出来。欢迎多多转发。 |
CopyRight 2018-2019 实验室设备网 版权所有 |