我可能开发了世界上最快的通用排序算法，比快排快 60%

た入场券 2023-10-15 02:52 20阅读 0赞

在 Flutter ConstraintLayout 中用到了计数排序，众所周知，计数排序在某些场景下可以说是最快的排序算法，它有时甚至不需要元素间两两比较。但它有个最大的问题，它不通用！只适合对小范围的整数进行排序。

于是这段时间我一直在寻思着能不能改进它，让它通用呢，终于今天灵感爆发，我做到了！

因为我姓陈，所以我把它命名为 Chen Sort。看看它的性能表现吧：

**空间复杂度恒为：O(n)，时间复杂度为 O(nlogn)，在最好的情况下，不需要元素间两两比较就能排好序。且它是稳定的。**

## 性能测试 ##

众所周知全世界公认的最快的通用排序算法是快排，我们来和它做下性能对比吧，基准如下：

**随机生成若干个范围为 \[1,4294967296\] 的正整数，使用 Chen Sort 和快排分别排序。**

这里没有生成负数，负数性能会下降一些，但仍比快排快很多。

## 100 个随机数 ##

![format_png][]

![Image 1][]

100\_compare.png

平均快了 10%。

## 10000 个随机数 ##

![format_png 1][]

![Image 1][]

10000\_compare.png

平均快了 60% 多。

## 100000 随机数 ##

![format_png 2][]

![Image 1][]

100000\_compare.png

平均快了 80% 多。

## 1000000 随机数 ##

![format_png 3][]

1000000\_compare.png

平均快了 20% 左右。

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

[format_png]: https://img-blog.csdnimg.cn/img_convert/f00ddc03bf9a784e41ca99f56ef1d886.webp?x-oss-process=image/format,png
[Image 1]: 
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/a1a812078b06809e26cdc3bbd5eb7a07.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/ec55f19c40206b169c4713316e6f4394.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/0dca91ac84679b2713122c3e38c361f6.webp?x-oss-process=image/format,png