有序阵列

有序阵列是内容依一定顺序排列的阵列，是资料结构的一种。其顺序可能是依字母顺序、数字顺序或是其他顺序，在记忆体中会存放在连结位置。在计算机科学中常用有序阵列来实现查找表，其中有许多相同资料型态的资料。一般阵列可以透过排序变成有序阵列，常用在以一定方式组织资料，并且经常要查询的场合。

有序阵列
类型	阵列
发明时间	1945
发明者	约翰·冯·诺伊曼
用大O符号表示的时间复杂度 算法 平均 最差 搜索 O(log n) O(log n) 插入 O(n) O(n) 删除 O(n) O(n) 用大O符号表示的空间复杂度 空间 O(n) O(n)

简介

有序阵列是空间非常节省的资料结构，对于顺序储存的资料，访问局部性很好。

有序阵列里的元素可以用二分搜寻法来查询，时间复杂度O(log n)，因此有序阵列适用于要快速查找资料的应合，例如集合（英语：Set (computer science)）（set）或多重集（multiset）。其查询的时间复杂度和平衡树相同。

有些资料结构中是用阵列实现。此时，可以用相同的排序方程用某键值，针对资料进行排序，例如依姓名或学号来排序学生资料等。

若是使用有序的动态数组，就可以插入元素或删除元素。有序阵列插入资料或删除资料的时间复杂度是O(n)，因为需要移动所有在该元素之后的资料。而平衡树插入资料和删除资料的时间复杂度是O(log n)。若其要插入或删除的元素是在最后一个，有序阵列依平摊分析下的复杂度是O(1)，而平衡树仍是O(log n)。

有序阵列中的资料可以随机存取，时间复杂度是O(1)，像其他较复杂的资料结构，存取的时间复杂度是O(log n)或 O(n)。

历史

约翰·冯·诺伊曼在1945年写了第一个阵列排序程式（使用归并排序），当时第一个可以储存程式的电脑（EDVAC）仍在构建中^[1][2]。

相关条目

• 排序算法
• 二分搜寻
• 堆积：一种资料结构
• 搜寻资料结构（英语：Search data structure）