在 Flutter ConstraintLayout 中用到了計(jì)數(shù)排序，眾所周知，計(jì)數(shù)排序在某些場(chǎng)景下可以說(shuō)是最快的排序算法，它有時(shí)甚至不需要元素間兩兩比較。但它有個(gè)最大的問(wèn)題，它不通用！只適合對(duì)小范圍的整數(shù)進(jìn)行排序。
于是這段時(shí)間我一直在尋思著能不能改進(jìn)它，讓它通用呢，終于今天靈感爆發(fā)，我做到了！
因?yàn)槲倚贞悾晕野阉麨?Chen Sort。看看它的性能表現(xiàn)吧：
空間復(fù)雜度恒為：O(n)，時(shí)間復(fù)雜度為 O(nlogn)，在最好的情況下，不需要元素間兩兩比較就能排好序。且它是穩(wěn)定的。
性能測(cè)試
眾所周知全世界公認(rèn)的最快的通用排序算法是快排，我們來(lái)和它做下性能對(duì)比吧，基準(zhǔn)如下：
隨機(jī)生成若干個(gè)范圍為 [1,4294967296] 的正整數(shù)，使用 Chen Sort 和快排分別排序。
這里沒有生成負(fù)數(shù)，負(fù)數(shù)性能會(huì)下降一些，但仍比快排快很多。
100 個(gè)隨機(jī)數(shù)
平均快了 10%。
10000 個(gè)隨機(jī)數(shù)
平均快了 60% 多。
100000 隨機(jī)數(shù)
平均快了 80% 多。
1000000 隨機(jī)數(shù)
平均快了 20% 左右。
目前的實(shí)現(xiàn)語(yǔ)言是 Dart，晚點(diǎn)用 Java 實(shí)現(xiàn)一下，并和 Tim Sort 做個(gè)對(duì)比。應(yīng)該也會(huì)快很多。
代碼已開源到 GitHub，目前放在 Flutter ConstraintLayout 的 example/chen_sort.dart 中，后續(xù)再把它抽出來(lái)。歡迎多多轉(zhuǎn)發(fā)。
