c++ - 寻找最快的方法来排序由 C++ 中的三个不同值组成的 2000 个项目的列表

Question

基本上，程序会得到一个项目列表，并且必须将它们分类到三个不同的“箱子”中。把它想象成你正在对三种颜色的弹珠进行分类。这些项目都是 char 类型。感谢您的帮助。

Answer 1

这实际上不是一个经典的“排序”问题……因为只有固定数量的可能值，这被称为分区问题并且存在一个有效的解决方案来解决三个问题 -方式分区称为Dutch flag sort ，首先由 Edsger Dijkstra 提出。

该算法的运行时间复杂度为 O(n)，并且只需要遍历数组一次。

该算法也可以通过开发循环不变量来相当简单地找到。