直接访问数组排序：键值分离与排序原理解析

直接访问数组排序是一种利用键值作为数组索引的线性时间排序算法。它通过创建一个足够大的辅助数组，将待排序对象的键值映射为该数组的索引，从而实现对象的直接存储。在遍历辅助数组时，按索引顺序提取对象，即可得到排序后的结果。本文将详细解析其工作原理，包括键与值的存储方式、算法步骤、时间空间复杂度及适用场景，澄清其对完整对象的排序能力。

直接访问数组排序概述

直接访问数组排序（Direct Access Array Sort）是一种基于特定假设的排序算法，它适用于待排序元素具有唯一、非负整数键的情况。其核心思想是利用这些键作为辅助数组的索引，将每个元素直接放置到其键对应的位置上。由于数组索引天然有序，通过遍历这个辅助数组，即可按键的顺序提取出所有元素，从而完成排序。这种方法避免了比较操作，因此在满足条件时可以达到线性时间复杂度。

算法工作原理与步骤

以下是直接访问数组排序算法的详细步骤，结合Python代码进行解析：

def direct_access_sort(A):
    "Sort A assuming items have distinct non-negative keys"
    # 1. 找到最大键值，确定辅助数组大小
    u = 1 + max([x.key for x in A]) # O(n) find maximum key

    # 2. 创建直接访问数组 D
    D = [None] * u # O(u) direct access array

    # 3. 将元素插入到直接访问数组 D
    for x in A: # O(n) insert items
        D[x.key] = x # 注意：这里存储的是整个对象 x，而不仅仅是它的键

    # 4. 从 D 中按顺序读出元素并放回原数组 A
    i = 0
    for key in range(u): # O(u) read out items in order
        if D[key] is not None: # 检查该键对应的位置是否有元素
            A[i] = D[key] # 将完整的对象放回原数组
            i += 1

1. 确定辅助数组大小 u: 算法首先遍历输入数组 A，找出所有元素中最大的键值。然后，将 u 设置为 max_key + 1。这个 u 值决定了直接访问数组 D 的大小，确保所有可能的键都有对应的索引位置。这一步的时间复杂度为 O(n)，其中 n 是输入数组 A 中元素的数量。

2. 初始化直接访问数组 D: 创建一个大小为 u 的新数组 D，并用 None 或其他默认值填充。这个数组就是我们的“直接访问数组”，它将用于存储待排序的元素。这一步的时间复杂度为 O(u)。

3. 插入元素到 D: 遍历输入数组 A 中的每一个元素 x。对于每个元素，使用其键 x.key 作为索引，将整个元素 x 存储到 D[x.key] 的位置上。这一步的关键在于，D 存储的是包含键和值在内的完整对象，而不是仅仅是键本身。这一步的时间复杂度为 O(n)。

4. 从 D 中按序读出元素: 初始化一个计数器 i = 0，用于跟踪在 A 中插入元素的位置。 接着，从 0 到 u-1 遍历 D 的所有索引（即 key）。 对于每个 key，检查 D[key] 是否不为 None。如果 D[key] 存在一个元素，这意味着这个 key 是输入数组 A 中某个元素的键。 将 D[key] 中存储的完整元素赋值给 A[i]，然后将 i 递增。 由于我们是按键的自然顺序（0, 1, 2, ...）遍历 D，所以当元素被放回 A 时，它们将按照其键的大小有序排列。这一步的时间复杂度为 O(u)。

澄清：排序的是键还是值？

关于“排序的是键还是值”的疑问，答案是：直接访问数组排序通过对键的排序，实现了对完整对象的排序。

让我们通过一个具体的例子来理解：假设我们有一个包含人员信息的数组 A，每个对象包含一个 key（表示身高）和一个 name（表示姓名）。我们希望按身高对人员进行排序。

# 初始输入数组 A
A = [
    {"key": 160, "name": "Alice"},
    {"key": 150, "name": "Bob"},
    {"key": 200, "name": "Charlie"},
    {"key": 188, "name": "David"}
]

1. 找到最大键值 u: max_key 为 200，所以 u = 201。

2. 创建 D: D 将是一个包含 201 个 None 的数组。

3. 插入元素到 D:

   • D[160] = {"key": 160, "name": "Alice"}
   • D[150] = {"key": 150, "name": "Bob"}
   • D[200] = {"key": 200, "name": "Charlie"}
   • D[188] = {"key": 188, "name": "David"} 此时，D 数组中只有索引 150, 160, 188, 200 处存储了完整的对象，其他位置仍为 None。

4. 从 D 中按序读出元素:

   • 当 key = 150 时，D[150] 不为 None。将 {"key": 150, "name": "Bob"} 赋值给 A[0]。i 变为 1。
   • 当 key = 160 时，D[160] 不为 None。将 {"key": 160, "name": "Alice"} 赋值给 A[1]。i 变为 2。
   • 当 key = 188 时，D[188] 不为 None。将 {"key": 188, "name": "David"} 赋值给 A[2]。i 变为 3。
   • 当 key = 200 时，D[200] 不为 None。将 {"key": 200, "name": "Charlie"} 赋值给 A[3]。i 变为 4。

最终，A 将变为：

A = [
    {"key": 150, "name": "Bob"},
    {"key": 160, "name": "Alice"},
    {"key": 188, "name": "David"},
    {"key": 200, "name": "Charlie"}
]

可以看到，整个对象（包括 name 这个“值”）都按照 key（身高）的大小进行了排序。因此，该算法确实实现了对包含键和值的完整对象的排序。

时间与空间复杂度

• 时间复杂度:

  • 查找最大键：O(n)
  • 初始化 D：O(u)
  • 插入元素：O(n)
  • 读出元素：O(u) 综合来看，总时间复杂度为 O(n + u)。其中 n 是输入元素的数量，u 是最大键值加一。

• 空间复杂度: 主要消耗在于创建了辅助数组 D，其大小为 u。因此，空间复杂度为 O(u)。

适用场景与注意事项

直接访问数组排序的效率高度依赖于键的特性：

1. 键的范围限制: 该算法要求键是非负整数。如果键是负数、浮点数或字符串，则无法直接用作数组索引。
2. 键的唯一性: 算法假设键是唯一的。如果存在重复键，后面的插入会覆盖前面的元素，导致数据丢失。若需处理重复键，D[x.key] 处需存储一个列表或链表来保存所有具有该键的元素。
3. 键的稀疏性: 如果键的范围 u 远大于元素的数量 n（即键非常稀疏，例如排序 10 个元素，但最大键值是 100 万），那么创建和遍历 D 将消耗大量的内存和时间，导致效率低下。在这种情况下，O(u) 的时间/空间复杂度会非常高，远不如基于比较的排序算法（如快速排序、归并排序）或更高级的线性排序算法（如基数排序）。
4. 最佳应用场景: 当键的范围 u 相对较小，或者 u 与 n 处于同一数量级时，直接访问数组排序可以提供非常高效的线性时间排序。例如，对年龄（0-150）进行排序，或者对小型哈希表中的键进行排序。

总结

直接访问数组排序是一种简洁而高效的线性时间排序算法，它通过利用键作为数组索引，实现了对包含键和值的完整对象的排序。其核心优势在于避免了元素间的比较，从而在特定条件下达到 O(n + u) 的时间复杂度。然而，其适用性受到键为非负整数、键的唯一性以及键值范围不能过大的严格限制。在实际应用中，开发者需要根据数据的特性权衡其优势与局限性，选择最合适的排序策略。