在 Flutter ConstraintLayout 中用到了計(jì)數(shù)排序凯沪，眾所周知，計(jì)數(shù)排序在某些場(chǎng)景下可以說是最快的排序算法买优，它有時(shí)甚至不需要元素間兩兩比較妨马。但它有個(gè)最大的問題，它不通用杀赢！只適合對(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)的最快的通用排序算法是快排，我們來和它做下性能對(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ù)再把它抽出來昧捷。歡迎多多轉(zhuǎn)發(fā)闲昭。
