數(shù)組在任何一種編程語言中寒亥，都是一種基礎的數(shù)據(jù)結構。大家提到數(shù)組荧关，都不會感到陌生，甚至會拍拍胸脯自信地說：這很簡單啊褂傀。
大家有沒有想過：數(shù)組為什么從 0 開始編號呢忍啤，為什么不從 1 開始呢？希望你帶著這個疑問去看接下去的文章。
文中會涉及到時間復雜度的分析同波，不懂的朋友可以先看看這篇鳄梅。
復雜度分析
什么是數(shù)組？
數(shù)組(Array)是一種線性表數(shù)據(jù)結構未檩。它用一組連續(xù)的內存空間戴尸，來存儲一組具有相同數(shù)據(jù)類型的數(shù)據(jù)。
這句話里有幾個關鍵詞冤狡，下面我就來給你解讀一下孙蒙。
1. 線性表（Linear List)。顧名思義悲雳，線性表就是數(shù)據(jù)排成一條線一樣的結構挎峦。鏈表、隊列合瓢、棧等數(shù)據(jù)結構也是線性表結構坦胶，我會在后文中一一講解，敬請關注哦晴楔。而堆顿苇、樹、圖等則是非線性的税弃，即數(shù)據(jù)間不是簡單的前后關系岖圈。
2. 連續(xù)的內存空間，相同的數(shù)據(jù)類型钙皮。正是由于數(shù)組的這個殺手锏特性蜂科，數(shù)組可以實現(xiàn)隨機訪問，但是任何一種數(shù)據(jù)結構都是有其適用場合的短条，有利有弊的导匣。數(shù)據(jù)的插入和刪除操作，為了保證連續(xù)性茸时，需要做大量的工作贡定。
而數(shù)組的隨機訪問由尋址方式實現(xiàn)：
a[i]_address = base_address + i * data_type_size
data_type_size 為數(shù)組中每個元素的大小，如果數(shù)組中存儲 int 類型數(shù)據(jù)可都， data_type_size 為 4 個字節(jié)缓待。
舉個例子：現(xiàn)在我們創(chuàng)建一個長度為 5 的 int 類型的數(shù)組，int[] a = new int[5]; 計算機會在內存中給數(shù)組 a[5] 分配一塊連續(xù)的內存渠牲，我們設內存塊的首地址為 base_address 為 1000旋炒，即
| int a[5] | 內存地址 |
|---|---|
| a[0] | 1000~1003 |
| a[1] | 1004~1007 |
| a[2] | 1008~1011 |
| a[3] | 1012~1015 |
| a[4] | 1016~1019 |
當計算機需要訪問元素 a[1] 時，它會根據(jù)上面的尋址公式签杈，即：
a[i]_address = base_address + i * data_type_size
來計算出 a[1] 的內存地址瘫镇，從而實現(xiàn)隨機訪問，根據(jù)下標訪問時間復雜度為 O(1)。
另外在面試中面試官經常會問數(shù)組和鏈表的區(qū)別铣除，我們可以這樣回答：
鏈表適合插入谚咬、刪除，時間復雜度為 O(1)尚粘；數(shù)組適合查找择卦，但是查找的時間復雜度并不為 O(1)，即使是排好序的數(shù)組郎嫁，你用二分查找秉继，時間復雜度也是 O(logn)。
數(shù)組支持隨機訪問行剂，根據(jù)下標隨機訪問的時間復雜度為 O(1)秕噪。
數(shù)組的插入和刪除操作
我們先來看插入操作。
如果我們在數(shù)組的末尾插入數(shù)據(jù)厚宰，我們不需要移動數(shù)據(jù)腌巾，時間復雜度為 O(1)。我們在數(shù)組的開頭插入數(shù)據(jù)铲觉，需要移動 n 個數(shù)據(jù)澈蝙，時間復雜度為 O(n)。假設我們在數(shù)組的任何位置插入數(shù)據(jù)的概率是相同的撵幽，則平均時間復雜度為 （1+2+3+···+n) / n = O(n)灯荧。
我們再來看刪除操作，和插入類似盐杂，刪除數(shù)組最后一個數(shù)據(jù)逗载，時間復雜度為 O(1)。刪除開頭第一個數(shù)據(jù)链烈，需要移動 n 個數(shù)據(jù)厉斟，時間復雜度為 O(n)。平均時間復雜度為 （1+2+3+···+n) / n = O(n)强衡。
我們看到數(shù)組的插入和刪除操作都是比較低效的擦秽，而這都是數(shù)組的連續(xù)性帶來的。實際上漩勤，在某些特殊場景里感挥，我們不一定會去追求數(shù)組中數(shù)據(jù)的連續(xù)性，如果我們可以將多次的刪除集中在一起執(zhí)行呢越败？如果這樣做的話触幼，執(zhí)行效率是不是高了很多呢？
我們繼續(xù)延用上面的例子給你解釋：
假設數(shù)組 a[5] 存儲了 5 個元素：1眉尸， 2域蜗， 3巨双， 4噪猾， 5∶够觯現(xiàn)在，我們要依次刪除 1袱蜡， 2丝蹭， 3 三個元素。我們可以先記錄下已經刪除的數(shù)據(jù)坪蚁，每次的刪除操作并不是真正地搬移數(shù)據(jù)，只是刪除記錄數(shù)據(jù)。當數(shù)組沒有更多空間存儲數(shù)據(jù)時芒篷，我們觸發(fā)一次真正的刪除操作威根，這樣執(zhí)行效率大大增加。
假如你了解 JVM 的垃圾回收算法嘴脾，你會發(fā)現(xiàn)這就是它的核心思想男摧。
數(shù)據(jù)結構與算法的最大魅力莫過于此，我們可以在很多地方發(fā)現(xiàn)他的影子译打，是程序的靈魂耗拓，也會有很多我們意想不到的「騷操作」。
容器能否代替數(shù)組
我們知道很多語言都提供了容器類奏司，由于筆者比較熟悉 Java乔询，這里我拿 Java 舉例，java 中的 ArrayList 作為 Java 工程師幾乎天天都在使用韵洋。我們知道 ArrayList 封裝了很多數(shù)組操作的細節(jié)竿刁，改用方法代替，還有就是支持動態(tài)擴容搪缨，我們完全不用擔心底層邏輯食拜，當我們的空間不夠用時，ArrayList 會自動幫我們將空間擴容成 1.5 倍勉吻。
但是 ArrayList 是無法存儲基本類型的监婶，如 int、long齿桃，需要封裝成 Integer惑惶、Long 類，另外對于數(shù)據(jù)大小我們事先已知短纵，數(shù)據(jù)操作較為簡單带污，我們可以優(yōu)先考慮數(shù)組，畢竟我們不需要用到 ArrayList 提供的大多數(shù)方法香到。
最后鱼冀，我來回答大家這個問題：數(shù)組為什么從 0 開始編號呢报破，為什么不從 1 開始呢？
答曰：歷史原因千绪，因為 C 語言的設計者設計數(shù)組時是從 0 開始的充易，后來 Java 等高級語言都效仿 C 語言，再說荸型，也讓 C 語言學習者轉入其他高級語言的學習減少了成本盹靴。怪不得，學校老師總是要求大家好好學 C 語言呢瑞妇？
今天數(shù)組的學習就到這里了稿静，我留個小問題，請你思考一下辕狰，二維數(shù)組的尋址是怎樣的呢改备？
歡迎留言與我分享！
System.out.println("點個喜歡蔓倍！歡迎關注我悬钳！");
