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

胖丽君_4353

胖丽君_4353

2025-11-20

350人浏览

原创

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

直接访问数组排序是一种利用键作为数组索引的线性时间排序算法。它通过构建一个辅助数组,将原始数据项(包含键和值)直接存储在与其键对应的位置。随后,按键的自然顺序遍历辅助数组,即可高效地提取出完整的、已排序的数据项,从而实现对“值”而非仅仅“键”的排序,但要求键为不重复的非负整数。

什么是直接访问数组排序?

直接访问数组排序(Direct Access Array Sort)是一种非比较排序算法,它适用于待排序数据项的键满足特定条件的情况:键必须是唯一的、非负的整数。该算法的核心思想是利用键值作为数组的索引,将数据项直接放置到辅助数组的相应位置,从而在后续遍历时,自然地按照键的顺序取出数据项。

算法原理与实现

该算法通常分为两个主要阶段:插入阶段和读取阶段。以下是其Python实现示例:

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

当代码执行 D[x.key] = x 时,它将原始数组 A 中的一个数据项 x(这个 x 是一个包含 key 和其他 value 的对象)完整地赋值给了 D 数组中 x.key 对应的索引位置。这意味着 D 数组的每个非空位置存储的都是一个完整的对象,例如 {key: 160, value: "Alice"}。

随后,在读取阶段:

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

当 D[key] 被检索时,我们得到的是之前存储的那个完整的对象。例如,如果 D[160] 存储的是 {key: 160, value: "Alice"},那么 A[i] = D[key] 就会将整个 {key: 160, value: "Alice"} 对象赋值给 A 的当前位置。由于我们是按照 key 从小到大遍历 range(u),因此,从 D 中取出的数据项自然就是按照它们的键值排好序的,同时它们所包含的“值”也随之被正确地排序了。

因此,直接访问数组排序确实实现了对数据项整体(包括键和值)的排序,只是排序的依据是数据项的键。

Biopython
Biopython

全面的分子生物学工具集。适用于序列操作、文件解析(FASTA/GenBank/PDB)、系统发育分析,以及通过 Bio.Entrez 以编程方式访问 NCBI/

下载

示例演示

假设我们有一个包含人员信息的列表,每个人员对象有 key(身高)和 value(姓名)。

# 初始输入数组,包含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}]

从输出可以看出,原始数据项(包括姓名,即 value)已经根据身高(即 key)进行了排序。

性能分析

  • 时间复杂度:
    • 查找最大键:O(n),其中n是数据项的数量。
    • 创建直接访问数组:O(u),其中u是最大键值加一。
    • 插入数据项:O(n)。
    • 读取数据项:O(u)。
    • 总时间复杂度为 O(n + u)。
  • 空间复杂度:
    • 直接访问数组 D 需要 O(u) 的额外空间。

适用场景与注意事项

  1. 键的特性: 直接访问数组排序要求键必须是:

    • 唯一的: 如果键不唯一,则后插入的数据项会覆盖先插入的,导致数据丢失或排序不正确。
    • 非负整数: 键作为数组索引,必须是非负整数。
    • 范围有限: 键的范围 u 不宜过大。
  2. 稀疏性问题: 如果数据项的数量 n 远小于键的范围 u(例如,只有10个数据项,但键的范围是0到1,000,000),那么 D 数组将非常稀疏,大部分空间会被 None 填充,导致极大的内存浪费。在这种情况下,其 O(u) 的时间复杂度也会变得非常高,效率甚至不如 O(n log n) 的比较排序算法。

  3. 与计数排序的关系: 直接访问数组排序与计数排序(Counting Sort)有相似之处,两者都利用了键的整数特性。计数排序通常用于对整数本身进行排序或作为基数排序的子过程,它通过统计每个键出现的次数来确定元素在输出数组中的位置。而直接访问数组排序则是将完整的对象直接放置到键对应的位置。

  4. 实际应用: 当键的范围相对较小且键值密集时,直接访问数组排序可以提供非常高效的线性时间排序。例如,对分数、年龄等有限范围内的整数键进行排序。

总结

直接访问数组排序是一种简单而高效的线性时间排序算法,它通过将数据项的键作为辅助数组的索引,实现了对完整数据项的排序。其核心在于直接访问数组存储的是数据项本身,而非仅仅键值。尽管它具有 O(n+u) 的优秀时间复杂度,但其适用性受到键值范围和唯一性的严格限制。在实际应用中,需要根据具体的数据特性权衡其内存消耗和性能表现。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
sort排序函数用法
sort排序函数用法

sort排序函数的用法:1、对列表进行排序,默认情况下,sort函数按升序排序,因此最终输出的结果是按从小到大的顺序排列的;2、对元组进行排序,默认情况下,sort函数按元素的大小进行排序,因此最终输出的结果是按从小到大的顺序排列的;3、对字典进行排序,由于字典是无序的,因此排序后的结果仍然是原来的字典,使用一个lambda表达式作为key参数的值,用于指定排序的依据。

2023.09.04

1158

7

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7296

4

vb中怎么连接access数据库
vb中怎么连接access数据库

vb中连接access数据库的步骤包括引用必要的命名空间、创建连接字符串、创建连接对象、打开连接、执行SQL语句和关闭连接。本专题为大家提供连接access数据库相关的文章、下载、课程内容,供大家免费下载体验。

2023.10.09

3187

5

vb连接access数据库的方法
vb连接access数据库的方法

vb连接access数据库方法:1、使用ADO连接,首先导入System.Data.OleDb模块,然后定义一个连接字符串,接着创建一个OleDbConnection对象并使用Open() 方法打开连接;2、使用DAO连接,首先导入 Microsoft.Jet.OLEDB模块,然后定义一个连接字符串,接着创建一个JetConnection对象并使用Open()方法打开连接即可。

2023.10.16

3033

3

asp连接access数据库的方法
asp连接access数据库的方法

连接的方法:1、使用ADO连接数据库;2、使用DSN连接数据库;3、使用连接字符串连接数据库。想了解更详细的asp连接access数据库的方法,可以阅读本专题下面的文章。

2023.10.18

3353

4

access和trunk端口的区别
access和trunk端口的区别

access和trunk端口的区别是Access端口用于连接终端设备,提供单个VLAN的接入,而Trunk端口用于连接交换机之间,提供多个VLAN的传输;Access端口只传输属于指定VLAN的数据,而Trunk端口可以传输多个VLAN的数据,并使用VLAN标签进行区分。想了解更多access和trunk端口相关内容,可以阅读本专题下面的文章。

2023.10.31

448

3

access怎么导入数据
access怎么导入数据

access导入数据步骤:1. 选择数据源 2. 选择要导入的文件 3. 指定导入选项 4. 选择导入目标 5. 预览数据 6. 导入数据即可。想了解更多access的相关内容,可以阅读本专题下面的文章。

2024.04.10

5345

10

access数据库用途
access数据库用途

access数据库是一种关系型数据库管理系统,主要用途包括:数据存储和管理;数据查询和检索;报告和表单设计;应用程序开发。想了解更多access数据库的相关内容,可以阅读本专题下面的文章。

2024.04.10

12188

16

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程