陣列

陣列（Array）是一種線性的資料結構，用一組連續的記憶體空間，來存盤一組具有相同型別的資料，

線性表

資料排列像一條線一樣的結構，線性表上的資料最多只有前后兩個方向，典型的線性表除了陣列，還有鏈表，佇列，堆疊等，

二叉樹，圖等都不是線性表，

這種好處是支持隨機訪問，相同型別表示每個元素的大小是固定的，通過下標就能直接找到元素的記憶體地址，

定義一個10個數字的int陣列a.

int[] a = new int[10];

假定首地址是1000（base_address），一個int占4位，所以a的記憶體空間是1000--1039.

每一個陣列元素的地址base_address+i * dataTypeSize，本例中dataType位int，所以dataTypeSize位4，

a[i]_address=base_address + i * dataTypeSize

高效的查詢

通過上面的存盤結構就可以知道，通過下標訪問陣列只需要O(1)的時間，但是查找本身是需要O(logn)【采用二分查找法】，

低效的插入

陣列記憶體的連續性決定了其插入和洗掉的低效，因為插入和洗掉都涉及到陣列記憶體的移動，

末尾插入，效率最高，O（1），其他地方插入需要移動，最壞為O（n），平均復雜度為O（n），

插入優化：對于無需的陣列，插入一個元素，可以將當前的元素移動到末尾，然后在當前元素的位置插入待插入的元素，這樣插入的復雜度便變成了O(1)，

上圖中插入X，把c移動到了末尾，X插入c的位置，避免了大量元素的移動，復雜度為常數級O（1），

低效的洗掉

和插入類似，洗掉也需要搬移資料，保證記憶體的連續性，

洗掉默認元素，效率最高，復雜度為O(1)，其他地方洗掉需要移動，最壞為O（n），平均復雜度為O（n），

洗掉優化

多個洗掉操作可以集中在一起操作，這個就會減少資料搬移的次數，從而提高效率，

具體操作是將需要洗掉的資料先進行標識，等到一定程度后一次性進行洗掉和記憶體搬遷，

上圖中a，b，c是分三次洗掉的，先進行標識，等到一定條件后一次性進行真正的洗掉，這樣d，e，f，g，h只需要搬移一次，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/283113.html

標籤：其他