有序陣列
 | 此條目没有列出任何参考或来源。 (2025年8月5日) |
| 有序陣列 | |||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 类型 | 陣列 | ||||||||||||||||||||||||||||
| 发明时间 | 1945 | ||||||||||||||||||||||||||||
| 发明者 | 约翰·冯·诺伊曼 | ||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
有序陣列是內容依一定順序排列的陣列，是資料結構的一種。其順序可能是依字母順序、數字順序或是其他順序，在記憶體中會存放在連結位置。在计算机科学中常用有序陣列來實現查找表，其中有許多相同資料型態的資料。一般陣列可以透過排序變成有序陣列，常用在以一定方式組織資料，並且經常要查詢的場合。
簡介
[编辑]有序陣列是空間非常節省的資料結構，對於順序儲存的資料，访问局部性很好。
有序陣列裡的元素可以用二分搜尋法來查詢，時間複雜度O(log n)，因此有序陣列適用於要快速查找資料的應合，例如{{link-en|集合 (抽象資料結構)|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]。
相關條目
[编辑]參考資料
[编辑]- ^ 高德纳, 计算机程序设计艺术, vol. 3. Addison-Wesley
- ^ Operating System Concepts by Peter B. Galvin. WILEY-INDIA Pvt. limited. ISBN 978-81-265-2051-0.