当直接访问数组排序对键而不是值进行排序时，它是如何工作的？

Question

在观看MIT OpenCourseWare 5. Linear Sorting时，教授谈到了Direct Access Array排序：

def direct_access_sort(A):
    "Sort A assuming items have distinct non-negative keys"
    u = 1 + max([x.key for x in A]) # O(n) find maximum key
    D = [None] * u # O(u) direct access array
    for x in A: # O(n) insert items
        D[x.key] = x
    i = 0
    for key in range(u): # O(u) read out items in order
        D[key] is not None:
            A[i] = D[key]
            i += 1

假设所有键都是范围 {0, . 。 。 , u − 1}，因此 n ≤ u， 这里描述的算法基本上是：

1. 将每个项目插入到大小为 u 的直接访问数组中
2. 按照 θ(u) 中直接访问数组中出现的顺序返回项目

我想知道如何将其描述为“排序”，因为在我看来，这里唯一排序的是key而不是value。

Answer 1

数组

D

将存储

A

中项目的完整对象（键和值）， 所以当插入回

A

时，它是完整的对象：

A[i] = D[key]

示例： 假设我们正在按身高对一组人进行排序，每个人都有一个等于他们身高的键。 输入看起来像这样（为了简单起见，不包括其他属性）：

A = [{key: 160}, {key: 150}, {key: 200}, {key: 188}]

此行查找 A 中的最大高度：

u = 1 + max([x.key for x in A]) # O(n) find maximum key

在我们的例子中，是 200。

这一行创建了一个大小为

u

的新数组，因此即使我们在

A

中只有 4 个元素，也是一个大小为 200 的数组：

D = [None] * u # O(u) direct access array

此循环将整个对象（包括键）插入到该数组中，位于键的索引处。

for x in A: # O(n) insert items
    D[x.key] = x

所以它是一个大小为 200 的数组，但只有 4 个索引有值（这些索引是高度 150、160、188、200）。 剩下的都是

None

。

向数组中插入元素时，我们需要一个计数器 - 这就是

i

的用途，所以它从 0 开始。

i = 0

现在我们从 0 迭代到最大键 (200)。

for key in range(u):

由于我们只有 4 个位置的值，因此我们需要检查我们正在测试的当前高度是否是这 4 个位置之一：

D[key] is not None: # (I think this line needs an `if` in front of it)

如果键在数组中，我们用具有该高度的对象覆盖

A

中的当前索引 (i)。

A[i] = D[key]

这首先是当 i = 0 并且 key = 150 时（因为当从 0 到 200 时，150 将是第一个匹配）

最后，

i

会递增，这样我们就不会在同一位置多次插入。

i += 1

因此插入时的值将是这样的：

i = 0, key = 150
i = 1, key = 160
i = 2, key = 188
i = 3, key = 160

考虑启动调试器，并查看运行时对象的样子。 它实现了很大的线性度，但要求输入是“明显的非负”。 此外，想象一下用数百万/数十亿的键对 10 个元素进行排序 - 数组和迭代会变得非常大。