直接访问数组排序是一种利用数据项的键作为数组索引进行排序的算法。它通过构建一个辅助的直接访问数组，将原始数据项（包含键和值）插入到对应键的索引位置，然后按索引顺序遍历辅助数组，从而高效地提取出排序后的完整数据项。该算法适用于键为非负、不重复且范围相对集中的整数场景，其时间复杂度为o(n+u)，但空间复杂度受最大键值u的影响。
直接访问数组排序原理
直接访问数组排序（Direct Access Array Sort）是一种特殊的排序算法，它利用了键的特性来实现高效排序。其核心思想是将待排序数据项的“键”（key）直接用作一个辅助数组的“索引”（index），从而在O(1)时间内完成数据项的定位和存储。由于数组索引本身是有序的，当遍历这个辅助数组时，就能按键的自然顺序取出所有数据项，实现整体排序。
该算法的关键在于，它排序的不仅仅是键本身，而是包含键和值的完整数据项（对象）。当数据项被放置到辅助数组中时，存储的是整个对象，而不是仅仅是键。
算法步骤与实现
下面我们通过一个Python示例代码来详细解析直接访问数组排序的实现过程。
def direct_access_sort(A):
"""
对数组 A 进行直接访问排序。
假设 A 中的每个元素都是一个具有 'key' 属性的对象，
且所有键都是非负且互不相同的整数。
"""
# 步骤 1: 确定键的最大值以构建直接访问数组的尺寸
# 这一步的复杂度为 O(n)，其中 n 是 A 中元素的数量。
u = 1 + max([x.key for x in A])
# 步骤 2: 创建一个直接访问数组 D，其大小为 u
# 数组 D 的索引将对应数据项的键。
# 这一步的复杂度为 O(u)，其中 u 是最大键值加一。
D = [None] * u
# 步骤 3: 将 A 中的每个数据项插入到 D 中对应的键索引位置
# 这一步的复杂度为 O(n)。
for x in A:
D[x.key] = x # 注意：这里存储的是完整的对象 x，而不是仅仅是 x.key
# 步骤 4: 从 D 中按顺序读取数据项并重新填充回 A
i = 0 # 用于跟踪 A 中的当前插入位置
# 这一步的复杂度为 O(u)。
for key in range(u):
# 检查当前键索引位置是否有数据项，因为 D 中可能存在大量 None 值
if D[key] is not None:
A[i] = D[key] # 将排序后的数据项放回 A
i += 1
return A代码解析：
- 确定最大键值 u: 算法首先遍历输入数组 A，找出所有数据项中键的最大值。u 被设置为 最大键值 + 1，以确保辅助数组 D 能够容纳所有可能的键作为索引（从0到最大键值）。这一步的目的是确定 D 的大小。
- 创建直接访问数组 D: 初始化一个大小为 u 的数组 D，所有元素初始设为 None。这个数组就是所谓的“直接访问数组”，它将利用键作为索引。
- 插入数据项: 遍历原始数组 A 中的每个数据项 x。将 x 完整地存储到 D 中以 x.key 为索引的位置。例如，如果 x.key 是 150，那么 D[150] 将存储对象 x。这是算法的关键，它将数据项“映射”到其有序位置。
-
按序提取数据项: 初始化一个计数器 i 为 0，用于跟踪在 A 中填充的位置。然后，从 0 到 u-1 遍历 D 的所有索引（即所有可能的键）。
- 在每次迭代中，检查 D[key] 是否为 None。由于不是所有的键都可能存在于原始数据中，D 中会有很多空位。
- 如果 D[key] 不为 None，这意味着在 key 这个位置存储了一个有效的数据项。此时，将 D[key] （即完整的排序后的数据项）赋值给 A[i]，并将 i 递增。通过这种方式，A 被重新填充为按键值升序排列的数据项。
示例说明
假设我们有一个人员列表，每个人员对象包含一个表示身高的 key 属性，我们要按身高对他们进行排序：
# 原始输入数组 A
A = [{key: 160, name: "Alice"}, {key: 150, name: "Bob"},
{key: 200, name: "Charlie"}, {key: 188, name: "David"}]
# 1. 确定 u
# max([x.key for x in A]) 得到 200
u = 1 + 200 = 201
# 2. 创建 D
# D = [None, None, ..., None] (长度为 201 的数组)
# 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 中按序提取并填充回 A
# i = 0
# 遍历 key 从 0 到 200
# 当 key = 150 时: D[150] is not None
# A[0] = {key: 150, name: "Bob"}
# i = 1
# 当 key = 160 时: D[160] is not None
# A[1] = {key: 160, name: "Alice"}
# i = 2
# 当 key = 188 时: D[188] is not None
# A[2] = {key: 188, name: "David"}
# i = 3
# 当 key = 200 时: D[200] is not None
# A[3] = {key: 200, name: "Charlie"}
# i = 4
# 最终 A 将变为：
# A = [{key: 150, name: "Bob"}, {key: 160, name: "Alice"},
# {key: 188, name: "David"}, {key: 200, name: "Charlie"}]可以看到，最终 A 中的数据项是按照它们的 key 值（身高）从小到大排序的，并且每个数据项的完整信息都被保留。
注意事项与局限性
-
键的特性要求:
- 非负整数: 键必须是非负整数，因为它们被用作数组索引。
- 唯一性: 键必须是唯一的。如果存在重复键，后面的数据项会覆盖前面相同键的数据项，导致数据丢失。
- 范围: 键的范围不宜过大。
-
时间复杂度:
- 最佳、平均和最坏情况下的时间复杂度均为 O(n + u)，其中 n 是输入数据项的数量，u 是最大键值加一（即直接访问数组的大小）。
- 当 u 接近 n 时（例如，键值密集且范围不大），该算法效率非常高，接近线性时间。
-
空间复杂度:
- 空间复杂度为 O(u)。这是因为需要创建一个大小为 u 的辅助数组 D。
- 当最大键值 u 远大于数据项数量 n 时（例如，排序 10 个键值在百万级别的数据项），D 会非常庞大，导致大量的内存浪费。这种情况下，直接访问数组排序变得非常不实用。
-
适用场景:
- 适用于键是小范围、密集且唯一的非负整数的场景。例如，对年龄、分数（0-100）、小范围 ID 等进行排序。
- 不适用于键值稀疏、范围巨大或为负数、浮点数、字符串等类型的情况。
总结
直接访问数组排序是一种利用键作为索引的巧妙排序技术，它在特定条件下能够提供非常高效的线性时间排序性能。其核心在于通过一个辅助数组 D，将完整的对象存储在以其键为索引的位置上，从而在遍历 D 时自然地获得排序结果。然而，其对键的严格要求（非负、唯一、范围适中）以及潜在的巨大空间开销限制了它的通用性。在选择排序算法时，开发者需要根据数据的具体特性来权衡时间、空间复杂度和算法的适用性。
