在 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 中，后续再把它抽出来。欢迎多多转发。