有序陣列

有序陣列是內容依一定順序排列的陣列，是資料結構的一種。其順序可能是依字母順序、數字順序或是其他順序，在記憶體中會存放在連結位置。在計算機科學中常用有序陣列來實現查找表，其中有許多相同資料型態的資料。一般陣列可以透過排序變成有序陣列，常用在以一定方式組織資料，並且經常要查詢的場合。

有序陣列
類型	陣列
發明時間	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）