有序陣列

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

簡介
有序陣列是空間非常節省的資料結構，對於順序儲存的資料，访问局部性很好。

有序陣列裡的元素可以用二分搜尋法來查詢，時間複雜度O(log n)，因此有序陣列適用於要快速查找資料的應合，例如（set）或多重集（multiset）。其查詢的時間複雜度和平衡树相同。

有些資料結構中是用陣列實現。此時，可以用相同的排序方程用某鍵值，針對資料進行排序，例如依姓名或學號來排序學生資料等。

若是使用有序的动态数组，就可以插入元素或刪除元素。有序陣列插入資料或刪除資料的時間複雜度是O(n)，因為需要移動所有在該元素之後的資料。而平衡树插入資料和刪除資料的時間複雜度是O(log n)。若其要插入或刪除的元素是在最後一個，有序陣列依平摊分析下的複雜度是O(1)，而平衡树仍是O(log n)。

有序陣列中的資料可以隨機存取，時間複雜度是O(1)，像其他較複雜的資料結構，存取的時間複雜度是O(log n)或 O(n)。

歷史
约翰·冯·诺伊曼在1945年寫了第一個陣列排序程式（使用归并排序），當時第一個可以儲存程式的電腦（EDVAC）仍在構建中高德纳, 计算机程序设计艺术, vol. 3. Addison-Wesley。

相關條目
 排序算法
 二分搜尋
 堆積：一種資料結構


參考資料

Category:数组