我大概开辟了天下上最快的通用排序算法，比快排快 60%

计算机软件开发 · 2024-9-7 00:48:22

在 Flutter ConstraintLayout 中用到了计数排序，众所周知，计数排序在某些场景下可以说是最快的排序算法，它偶然以致不须要元素间两两比力。但它有个最大的标题，它不通用！只恰当对小范围的整数进行排序。
于是这段时间我一直在寻思着能不能改进它，让它通用呢，终于本日灵感发作，我做到了！
由于我姓陈，以是我把它定名为 Chen Sort。看看它的性能体现吧：
空间复杂度恒为：O(n)，时间复杂度为 O(nlogn)，在最好的环境下，不须要元素间两两比力就能排好序。且它是稳固的。
性能测试

众所周知全天下公认的最快的通用排序算法是快排，我们来和它做下性能对比吧，基准如下：
随机天生多少个范围为 [1,4294967296] 的正整数，利用 Chen Sort 和快排分别排序。
这里没有天生负数，负数性能会降落一些，但仍比快排快很多。
100 个随机数

匀称快了 10%。
10000 个随机数

匀称快了 60% 多。
100000 随机数

匀称快了 80% 多。
1000000 随机数

匀称快了 20% 左右。
现在的实现语言是 Dart，晚点用 Java 实现一下，并和 Tim Sort 做个对比。应该也会快很多。
代码已开源到 GitHub，现在放在 Flutter ConstraintLayout 的 example/chen_sort.dart 中，后续再把它抽出来。欢迎多多转发。

我大概开辟了天下上最快的通用排序算法，比快排快 60%

所属分类: 问答交流

新帖推荐: 30日

推荐作品