直接访问数组排序：基于键实现对象排序的机制与实践

class Item:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value # 假设每个数据项除了键还有其他值

    def __repr__(self):
        return f"{{key: {self.key}, value: {self.value}}}"

def direct_access_sort(A):
    """
    使用直接访问数组对列表A进行排序。
    假设A中的每个元素都是一个包含'key'属性的对象，
    且键是唯一的、非负整数。
    """
    if not A:
        return []

    # 1. 确定最大键值 (O(n))
    # 找到所有数据项中的最大键，以确定直接访问数组的大小。
    max_key = max([x.key for x in A])
    u = max_key + 1 # 数组大小为 max_key + 1，以包含从0到max_key的所有键

    # 2. 创建直接访问数组 (O(u))
    # 初始化一个大小为u的数组D，所有位置初始为None。
    D = [None] * u

    # 3. 插入数据项到直接访问数组 (O(n))
    # 遍历原始数组A，将每个数据项x根据其键x.key放置到D的相应索引处。
    for x in A:
        D[x.key] = x # 注意：这里存储的是整个数据项x，而非仅仅是x.key

    # 4. 按顺序从直接访问数组中读取数据项 (O(u))
    # 初始化一个计数器i，用于填充排序后的数组A。
    i = 0
    # 遍历D数组的每个索引（即可能的键值）。
    for key in range(u):
        # 如果D[key]不为None，说明该键对应位置有数据项。
        if D[key] is not None:
            # 将D[key]（即完整的排序后的数据项）放回原始数组A的当前位置。
            A[i] = D[key]
            i += 1 # 移动到下一个待填充位置
    return A

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

for key in range(u): # O(u) read out items in order
    if D[key] is not None:
        A[i] = D[key]
        i += 1

# 初始输入数组，包含key和value
A = [
    Item(key=160, value="Alice"),
    Item(key=150, value="Bob"),
    Item(key=200, value="Charlie"),
    Item(key=188, value="David")
]

print("原始数组A:", A)
# 原始数组A: [{key: 160, value: Alice}, {key: 150, value: Bob}, {key: 200, value: Charlie}, {key: 188, value: David}]

# 1. 确定最大键值
# max_key = max([160, 150, 200, 188]) = 200
# u = 200 + 1 = 201

# 2. 创建直接访问数组
# D = [None, None, ..., None] (长度为201)

# 3. 插入数据项到直接访问数组
# 遍历A:
#   x = {key: 160, value: "Alice"} => D[160] = {key: 160, value: "Alice"}
#   x = {key: 150, value: "Bob"}   => D[150] = {key: 150, value: "Bob"}
#   x = {key: 200, value: "Charlie"} => D[200] = {key: 200, value: "Charlie"}
#   x = {key: 188, value: "David"} => D[188] = {key: 188, value: "David"}
# 此时，D数组在索引150, 160, 188, 200处有值，其余为None。

# 4. 按顺序从直接访问数组中读取数据项
# i = 0
# for key in range(201):
#   key = 0, D[0] is None
#   ...
#   key = 150, D[150] is not None. A[0] = D[150] => A[0] = {key: 150, value: "Bob"}. i = 1
#   key = 151, D[151] is None
#   ...
#   key = 160, D[160] is not None. A[1] = D[160] => A[1] = {key: 160, value: "Alice"}. i = 2
#   ...
#   key = 188, D[188] is not None. A[2] = D[188] => A[2] = {key: 188, value: "David"}. i = 3
#   ...
#   key = 200, D[200] is not None. A[3] = D[200] => A[3] = {key: 200, value: "Charlie"}. i = 4
#   ...
# 最终，A数组被更新为排序后的结果。

sorted_A = direct_access_sort(A)
print("排序后数组A:", sorted_A)
# 排序后数组A: [{key: 150, value: Bob}, {key: 160, value: Alice}, {key: 188, value: David}, {key: 200, value: Charlie}]