深入理解直接访问数组排序：原理与实现

直接访问数组排序是一种利用数据项的键值作为数组索引来对数据进行排序的算法。它适用于具有唯一、非负整数键的场景，通过构建一个足够大的直接访问数组来存储完整的对象，然后按键的自然顺序遍历该数组，从而高效地重建一个有序的数据序列。本文将详细解析其工作原理、实现步骤，并通过示例代码阐明其如何实现对完整对象的排序，并探讨其适用场景与局限性。

直接访问数组排序原理

直接访问数组排序（Direct Access Array Sort）的核心思想是利用数据项的键（key）作为数组的索引。当所有数据项的键都是唯一且非负的整数时，我们可以创建一个足够大的辅助数组（即直接访问数组），其大小能够覆盖所有可能的键值范围。然后，将每个数据项直接放置到辅助数组中对应其键的索引位置上。由于数组索引的自然有序性，当遍历辅助数组时，我们就能按键的升序依次取出数据项，从而实现对原始数据项的排序。

这种方法之所以能对“值”进行排序，是因为它存储在辅助数组中的是完整的“数据项”（通常是包含键和值的对象），而不仅仅是键本身。键的作用是确定数据项在辅助数组中的位置，而一旦数据项被放置到位，它就带着其所有属性（包括值）一同被“排序”了。

算法实现步骤

直接访问数组排序算法通常包含以下四个主要步骤：

1. 确定键值范围

首先，需要遍历输入数组 A，找出所有数据项中的最大键值。这个最大键值将决定直接访问数组 D 的大小 u（通常是 最大键值 + 1）。这一步的时间复杂度为 O(n)，其中 n 是输入数组 A 的长度。

2. 构建直接访问数组

创建一个新的辅助数组 D，其大小为 u，并用一个占位符（如 None）初始化所有位置。这个数组 D 就是我们所说的“直接访问数组”。这一步的空间复杂度为 O(u)。

3. 插入数据项

遍历输入数组 A 中的每一个数据项 x。对于每个 x，将其完整地存储到直接访问数组 D 中，其位置由 x.key 决定，即 D[x.key] = x。这一步的时间复杂度为 O(n)。

4. 有序提取

初始化一个计数器 i = 0，用于跟踪原始数组 A 中下一个可插入的位置。然后，从索引 0 到 u-1 遍历直接访问数组 D。对于 D 中的每一个位置 key，如果 D[key] 不为 None（即该位置存储了一个实际的数据项），则将该数据项 D[key] 复制回原始数组 A 的 A[i] 位置，并递增 i。这一步的时间复杂度为 O(u)。

示例代码与详细解析

以下是直接访问数组排序的Python实现示例，我们将通过一个具体的例子来详细解析其工作流程。

Delphi 7应用编程150例 全书内容 CHM版

Delphi 7应用编程150例 CHM全书内容下载，全书主要通过150个实例，全面、深入地介绍了用Delphi 7开发应用程序的常用方法和技巧，主要讲解了用Delphi 7进行界面效果处理、图像处理、图形与多媒体开发、系统功能控制、文件处理、网络与数据库开发，以及组件应用等内容。这些实例简单实用、典型性强、功能突出，很多实例使用的技术稍加扩展可以解决同类问题。使用本书最好的方法是通过学习掌握实例中的技术或技巧，然后使用这些技术尝试实现更复杂的功能并应用到更多方面。本书主要针对具有一定Delphi基础知识

0

查看详情

class Item:
    """模拟一个包含键和值的通用数据项"""
    def __init__(self, key, value=None):
        self.key = key
        self.value = value if value is not None else f"data_{key}"

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

def direct_access_sort(A):
    """
    直接访问数组排序算法
    假设数据项具有唯一且非负的整数键。
    """
    if not A:
        return A

    # 步骤一：确定键值范围
    # 查找输入数组A中所有项的最大键，并据此确定直接访问数组D的大小u。
    # O(n) 时间复杂度。
    max_key = 0
    for x in A:
        if x.key > max_key:
            max_key = x.key
    u = max_key + 1 # 直接访问数组的大小

    print(f"最大键值: {max_key}, 直接访问数组D的大小: {u}")

    # 步骤二：构建直接访问数组
    # 创建一个大小为u的数组D，并用None填充。
    # O(u) 空间复杂度。
    D = [None] * u
    print(f"初始化直接访问数组D (大小 {u}): {D}")

    # 步骤三：插入数据项
    # 遍历输入数组A中的每个数据项x，将其完整地放入D中以x.key为索引的位置。
    # O(n) 时间复杂度。
    print("\n--- 插入数据项到D ---")
    for x in A:
        D[x.key] = x
        print(f"插入 {x} 到 D[{x.key}]")
    print(f"插入后的D: {D}")

    # 步骤四：有序提取
    # 初始化一个计数器i，用于跟踪A中下一个可插入的位置。
    i = 0
    print("\n--- 从D有序提取数据项 ---")
    # 遍历直接访问数组D从索引0到u-1。
    # O(u) 时间复杂度。
    for key in range(u):
        # 检查当前索引key处是否有实际的数据项（即不是None）。
        if D[key] is not None:
            # 如果有数据项，将其按顺序放回原始数组A。
            A[i] = D[key]
            print(f"从 D[{key}] 提取 {D[key]} 到 A[{i}]")
            # 递增计数器，为下一个有序项准备。
            i += 1
    print(f"排序完成后的A: {A}")
    return A

# 示例数据：假设我们有一组人员，以身高（厘米）作为键进行排序
# 这里我们只关注key，value可以是一个占位符
input_data = [
    Item(key=160, value="Alice"),
    Item(key=150, value="Bob"),
    Item(key=200, value="Charlie"),
    Item(key=188, value="David")
]

print("原始输入数组 A:", input_data)
sorted_data = direct_access_sort(input_data)
print("最终排序结果 A:", sorted_data)

运行上述代码，我们将看到以下详细的执行过程：

1. 原始输入数组 A: [{key: 160, value: 'Alice'}, {key: 150, value: 'Bob'}, {key: 200, value: 'Charlie'}, {key: 188, value: 'David'}]

2. 步骤一：确定键值范围

   • 遍历 A，找到最大键为 200。
   • 因此，u = 200 + 1 = 201。直接访问数组 D 的大小将是 201。

3. 步骤二：构建直接访问数组

   • 创建一个包含 201 个 None 的数组 D。
   • D = [None, None, ..., None] (共201个)

4. 步骤三：插入数据项

   • 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 中只有 D[150], D[160], D[188], D[200] 存储了实际数据，其余位置仍为 None。

5. 步骤四：有序提取

   • i = 0
   • 遍历 key 从 0 到 200：
     • 当 key = 150 时，D[150] 不为 None。将 {key: 150, value: 'Bob'} 赋给 A[0]。i 变为 1。
     • 当 key = 160 时，D[160] 不为 None。将 {key: 160, value: 'Alice'} 赋给 A[1]。i 变为 2。
     • 当 key = 188 时，D[188] 不为 None。将 {key: 188, value: 'David'} 赋给 A[2]。i 变为 3。
     • 当 key = 200 时，D[200] 不为 None。将 {key: 200, value: 'Charlie'} 赋给 A[3]。i 变为 4。
   • 其他 key 值处 D[key] 均为 None，跳过。

最终排序结果 A: [{key: 150, value: 'Bob'}, {key: 160, value: 'Alice'}, {key: 188, value: 'David'}, {key: 200, value: 'Charlie'}]。 可以看到，原始的复杂对象（包含键和值）已经根据键的顺序成功排序。

适用场景与注意事项

适用场景

• 键为唯一非负整数: 这是该算法最基本且严格的要求。如果键不唯一，则需要额外的处理（如链表存储冲突），这会使其退化为桶排序或哈希表。
• 键的范围相对较小: 当键的最大值 u 与数据项数量 n 相近时，直接访问数组排序的效率非常高。其时间复杂度为 O(n + u)，空间复杂度为 O(u)。在理想情况下（u ≈ n），它可以达到线性的 O(n) 时间复杂度。

注意事项与局限性

• 键的唯一性: 如果键不唯一，D[x.key] = x 操作会覆盖掉相同键的先前数据项，导致数据丢失。
• 键的非负性: 数组索引不能为负数。
• 键的整数性: 数组索引必须是整数。
• 空间效率: 当键的范围 u 远大于数据项的数量 n 时，会造成大量的空间浪费。例如，如果只有10个数据项，但它们的键值分布在0到1,000,000之间，那么 D 数组将需要1,000,001个位置，其中绝大部分是空的，这在内存上是不可接受的。
• 时间效率: 即使空间不是问题，当 u 远大于 n 时，最后一步的遍历 D 的操作也会变得非常耗时，导致 O(n+u) 的时间复杂度中的 u 部分占据主导，性能下降。
• 与计数排序/基数排序的联系: 直接访问数组排序可以看作是计数排序的一种简化形式，尤其是在键值本身就是我们需要排序的唯一属性时。它也是基数排序的基础之一，基数排序通过多次直接访问数组排序来处理多位数键。

总结

直接访问数组排序是一种简洁高效的排序算法，尤其适用于键值范围有限且键为唯一非负整数的特定场景。它通过将键作为直接索引，实现了对完整数据项的快速定位和有序重构。然而，其对键的严格要求以及在键值范围过大时可能导致的巨大空间和时间开销，限制了其普适性。理解其工作原理和局限性，有助于在合适的场景中选择并应用这一强大的排序技术。

以上就是深入理解直接访问数组排序：原理与实现的详细内容，更多请关注php中文网其它相关文章！