如果大小为n的数组只有3个值0,1和2（重复任意次数），那么对它们进行排序的最佳方法是什么。 最好表示复杂性。 考虑空间和时间复杂性
计算每个数字的出现次数，然后用正确的计数填充数组，这是O(n)
声音很像Dijkstra的荷兰国旗问题。
如果您需要不使用计数的解决方案，请查看https://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
未经测试的C风格解决方案：
int count[3] = {0, 0, 0}; for (int i = 0; i < n; ++i) ++count[array[i]]; int pos = 0; for (int c = 0; c < 3; ++c) for (int i = array[c]; i; --i) array[pos++] = c;
Haskell双线：
count xs = Map.toList $ Map.fromListWith (+) [ (x, 1) | x <- xs ] countingSort xs = concatMap ( (x, n) -> replicate nx) (count xs) > countingSort [2,0,2,1,2,2,1,0,2,1] [0,0,1,1,1,2,2,2,2,2]
以上就是c/c++开发分享排序大小为n的数组相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/545701.html