在处理算法问题的示例代码时,我遇到了我正在对输入数组进行排序的情况,即使我只需要将相同的元素组合在一起,但不是按任何特定顺序排列,例如:
{1,2,4,1,4,3,2}→{1,1,2,2,4,4,3}或{1,1,2,2,3,4,4}或{3 ,1,1,2,2,4,4}或......
这让我想知道:是否有可能将数组中相同的元素组合在一起比排序数组更有效？
一方面,元素不需要移动到特定位置的事实意味着更自由地找到需要更少交换的订单.另一方面,跟踪组中每个元素的位置以及最佳最终位置是什么,可能需要比简单排序数组更多的计算.
逻辑候选者将是一种计数排序,但如果数组长度和/或值范围不切实际大,该怎么办？
为了论证,假设数组很大(例如一百万个元素),包含32位整数,每个值的相同元素数可以是1到100万.
更新:对于支持词典的语言,萨尔瓦多·达利的回答显然是要走的路.我仍然有兴趣听听老式的比较和交换方法,或者使用更少空间的方法,如果有的话.