m69*_*g'' 6 language-agnostic sorting algorithm performance
在处理算法问题的示例代码时,我遇到了我正在对输入数组进行排序的情况,即使我只需要将相同的元素组合在一起,但不是按任何特定顺序排列,例如:
{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万.
更新:对于支持词典的语言,萨尔瓦多·达利的回答显然是要走的路.我仍然有兴趣听听老式的比较和交换方法,或者使用更少空间的方法,如果有的话.
既然你问过基于比较的方法,我会做出通常的假设,即(1)元素可以比较而不是散列(2)唯一感兴趣的资源是三向操作.
从绝对意义上说,分组比分类更容易.这是一个使用一个比较的三个元素的分组算法(排序需要三个).给定输入x, y, z,if x = y,然后返回x, y, z.否则,返回x, z, y.
然而,渐近地,分组和排序都需要Omega(n log n)比较.下界技术是信息论的:我们证明,对于表示为决策树的每个分组算法,都有3^Omega(n log n)叶子,这意味着树的高度(因此算法的最坏情况运行时间)是Omega(n log n).
修复决策树的任意叶子,其中没有发现输入元素相等.输入位置由发现的不等式部分排序.
相反,假设i, j, k是成对无比的输入位置.出租x = input[i], y = input[j], z = input[k]的可能性x = y < z和y = z < x和z = x < y均与算法已经观察到的东西是一致的.这是不可能的,因为它是不可能由叶选择了一个为了把x旁边的y旁边的z旁边x.我们得出结论,偏序没有基数三的反共.
根据Dilworth定理,偏序有两条链覆盖整个输入.通过考虑将这些链合并为总顺序的所有可能方法,最多n choose m ? 2^n排列映射到每个叶子.因此叶子的数量至少是n!/2^n = 3^Omega(n log n).
是的，您需要做的就是创建一个字典并计算每次有多少个元素。之后，只需迭代该字典中的键并输出该键与该键的值相同的次数。
快速Python实现：
from collections import Counter
arr = [1,2,4,1,4,3,2]
cnt, grouped = Counter(arr), [] # counter create a dictionary which counts the number of each element
for k, v in cnt.iteritems():
grouped += [k] * v # [k] * v create an array of length v, which has all elements equal to k
print grouped
O(n)这将使用潜在的O(n)额外空间及时对所有元素进行分组。O(n logn)这比及时实现这一点并且可以就地完成的排序更有效（就时间复杂度而言） 。