数组可以比排序更有效地分组吗？

Question

在处理算法问题的示例代码时，我遇到了对输入数组进行排序的情况，尽管我只需要将相同的元素组合在一起，但不需要按任何特定顺序排列，例如：

{1,2,4,1,4,3,2} → {1,1,2,2,4,4,3} or {1,1,2,2,3,4,4} or {3,1,1,2,2,4,4} or ...

这让我想知道：是否有可能比对数组排序更有效地将数组中的相同元素组合在一起？

一方面，元素不需要移动到特定位置这一事实意味着可以更自由地找到需要更少交换的顺序。另一方面，跟踪组中每个元素的位置以及最佳最终位置可能需要比简单排序数组更多的计算。

一个合乎逻辑的候选者是一种计数排序，但如果数组长度and/or值范围大得不切实际怎么办？

为了论证，假设数组很大（例如一百万个元素），包含 32 位整数，并且每个值的相同元素数可以是从 1 到百万.

更新：对于支持字典的语言，萨尔瓦多·达利的答案显然是正确的选择。我仍然有兴趣了解老式的比较和交换方法，或者使用较少的方法 space，如果有的话。

Answer 1

是的，你需要做的就是创建一个字典并计算你每次有多少个元素。之后只需遍历该字典中的键并输出该键与该键的值相同的次数。

快速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) 额外的 space 对所有元素进行分组。这比排序更有效（就时间复杂度而言），后者将在 O(n logn) 时间内实现并可以就地完成。

Answer 2

既然你询问了基于比较的方法，我将做出通常的假设，即 (1) 元素可以比较但不能散列 (2) 唯一感兴趣的资源是三向操作。

从绝对意义上讲，分组比排序更容易。这是使用一次比较的三个元素的分组算法（排序需要三个）。给定输入 x, y, z，如果 x = y，则 return x, y, z。否则，return 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's theorem，偏序有两条链覆盖了整个输入。通过考虑将这些链合并为一个总顺序的所有可能方式，最多有 n choose m ≤ 2^n 个映射到每个叶子的排列。因此叶子的数量至少是 n!/2^n = 3^Omega(n log n).

Answer 3

任何排序算法，即使是最高效的排序算法，都需要您多次遍历数组。另一方面，分组可以在一次迭代中完成，具体取决于您坚持将结果格式化为两种格式的方式：

groups = {}
for i in arr:
    if i not in groups:
        groups[i] = []
    groups[i].append(i)

这是一个极其原始的循环，它忽略了您选择的语言中可能提供的许多优化和习语，但仅在一次迭代后就会产生这样的结果：

{1: [1, 1], 2: [2, 2], 3: [3], 4: [4, 4]}

如果你有复杂的对象，你可以选择任意属性作为字典键进行分组，所以这是一个非常通用的算法。

如果您坚持要结果是一个平面列表，您可以轻松实现：

result = []
for l in groups:
    result += l

（同样，忽略特定的语言优化和习语。）

所以你有一个恒定时间的解决方案，最多需要一次完整的输入迭代和一次较小的中间分组数据结构迭代。 space 要求取决于语言的具体情况，但通常只是字典和列表数据结构产生的任何一点开销。

Answer 4

如何使用二维数组，第一维是每个值的频率，第二维是值本身。我们可以利用布尔数据类型和索引。这也允许我们立即对原始数组进行排序，同时在原始数组上精确循环一次，从而为我们提供 O(n) 解决方案。我认为这种方法可以很好地翻译成其他语言。观察以下基本 R 代码（N.B。在 R 中有比下面更有效的方法，我只是给出一个更通用的方法）。

GroupArray <- function(arr.in) {

    maxVal <- max(arr.in)

    arr.out.val <- rep(FALSE, maxVal)  ## F, F, F, F, ...
    arr.out.freq <- rep(0L, maxVal)     ## 0, 0, 0, 0, ... 

    for (i in arr.in) {
        arr.out.freq[i] <- arr.out.freq[i]+1L
        arr.out.val[i] <- TRUE
    }

    myvals <- which(arr.out.val)   ## "which" returns the TRUE indices

    array(c(arr.out.freq[myvals],myvals), dim = c(length(myvals), 2), dimnames = list(NULL,c("freq","vals")))
}

上面代码的小例子：

set.seed(11)
arr1 <- sample(10, 10, replace = TRUE)

arr1                                    
[1]  3  1  6  1  1 10  1  3  9  2     ## unsorted array

GroupArray(arr1)    
     freq vals       ## Nicely sorted with the frequency
[1,]    4    1
[2,]    1    2
[3,]    2    3
[4,]    1    6
[5,]    1    9
[6,]    1   10

更大的例子：

set.seed(101)
arr2 <- sample(10^6, 10^6, replace = TRUE)

arr2[1:10]       ## First 10 elements of random unsorted array
[1] 372199  43825 709685 657691 249856 300055 584867 333468 622012 545829

arr2[999990:10^6]     ## Last 10 elements of random unsorted array
[1] 999555 468102 851922 244806 192171 188883 821262 603864  63230  29893 664059

t2 <- GroupArray(arr2)
head(t2)
     freq vals        ## Nicely sorted with the frequency
[1,]    2    1
[2,]    2    2
[3,]    2    3
[4,]    2    6
[5,]    2    8
[6,]    1    9

tail(t2)
          freq    vals 
[632188,]    3  999989
[632189,]    1  999991
[632190,]    1  999994
[632191,]    2  999997
[632192,]    2  999999
[632193,]    2 1000000

数组可以比排序更有效地分组吗？

Can an array be grouped more efficiently than sorted?

language-agnostic

sorting

algorithm

performance