有序数组

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

有序数组
类型	数组
发明时间	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）