數(shù)組概念:
數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)穿扳，它用一組連續(xù)的內(nèi)存空間秆麸，來存儲一組具有相同類型結(jié)構(gòu)的數(shù)據(jù)本砰。
關(guān)鍵詞:
線性:顧名思義爵政，線性表就是數(shù)據(jù)排成像一條線一樣的數(shù)據(jù)結(jié)構(gòu)仅讽。每個(gè)線性表上的數(shù)據(jù)最多只有前后兩個(gè)方向。其實(shí)除了數(shù)組钾挟，鏈表洁灵，隊(duì)列，棧等也是線性表結(jié)構(gòu)
而與它相對立的概念就是非線性表掺出，比如說二叉樹徽千，堆，圖汤锨。之所以叫非線性双抽，是因?yàn)椋诜蔷€性表中闲礼，數(shù)據(jù)之間并不是簡單的前后關(guān)系牍汹。
第二個(gè)是連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)。正是因?yàn)檫@兩個(gè)限制柬泽，它才有了一個(gè)堪稱“殺手锏”的特性：“隨機(jī)訪問”慎菲。但有利就有弊，隨機(jī)訪問對應(yīng)的就是查詢很快聂抢，但是當(dāng)插入和刪除的時(shí)候钧嘶，為了保證連續(xù)性，需要對數(shù)據(jù)進(jìn)行大量的遷移工作琳疏。
接下來我們來看下插入操作
數(shù)組長度為n,現(xiàn)在我們要將一個(gè)數(shù)據(jù)插入到數(shù)組中的第k個(gè)位置有决。為了把第k個(gè)位置空出來，就需要把k后面所有的數(shù)據(jù)依次往后面移動一位空盼，如果我們是在數(shù)組開頭插入數(shù)據(jù)书幕，那么就需要把所有的數(shù)據(jù)都順序往后面移動，這個(gè)時(shí)候時(shí)間復(fù)雜度就是O(n)揽趾，如果是在數(shù)組末尾插入一個(gè)數(shù)據(jù)台汇，那么就不需要移動數(shù)據(jù)，時(shí)間復(fù)雜度就是O(1)，所以最壞情況下的時(shí)間復(fù)雜度是O(n)苟呐，
最好情況下的時(shí)間復(fù)雜度是O(1)痒芝，但是其實(shí)在真正的工作當(dāng)中，出現(xiàn)這兩種情況的幾率很小牵素，大多數(shù)都是在數(shù)組開頭到結(jié)尾的位置插入數(shù)據(jù)严衬，那么平均算下來時(shí)間復(fù)雜度就是O(n)。
我們再來看刪除操作
跟插入數(shù)據(jù)類似笆呆，如果我們要刪除第k個(gè)位置的數(shù)據(jù)请琳，為了內(nèi)存的連續(xù)性，也需要搬移數(shù)據(jù)赠幕，不然中間就會出現(xiàn)空洞俄精，內(nèi)存就不連續(xù)了。
和插入類似榕堰，如果刪除數(shù)組末尾的數(shù)據(jù)竖慧，則最好情況時(shí)間復(fù)雜度為O(1)，如果刪除開頭的數(shù)據(jù)局冰，則最壞情況時(shí)間復(fù)雜度為O(n)测蘑；平均情況時(shí)間復(fù)雜度也為O(n)灌危。
實(shí)際上在某些特殊情況下康二，我們并不一定非得追求數(shù)組中數(shù)據(jù)的連續(xù)性。如果我們將多次刪除操作集中在一起執(zhí)行勇蝙，刪除的效率是不是會提高很多呢沫勿？
數(shù)組a[10]中存儲了8個(gè)元素：a,b,c,d,e,f,g,h。現(xiàn)在我們要依次刪除a,b,c三個(gè)元素
為了避免搬移三次數(shù)據(jù)味混，我們可以給這三個(gè)數(shù)據(jù)打上已刪除的標(biāo)示产雹，當(dāng)數(shù)組沒有更多空間存儲數(shù)據(jù)時(shí)，我們在觸發(fā)一次真正的刪除操作翁锡，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移蔓挖。
內(nèi)容小結(jié)
我們今天學(xué)習(xí)了數(shù)組。它可以說是最基礎(chǔ)馆衔，最簡單的數(shù)據(jù)結(jié)構(gòu)了瘟判。數(shù)組用一塊連續(xù)的內(nèi)存空間，來存儲相同類型的一組數(shù)據(jù)角溃，最大的特點(diǎn)就是支持隨機(jī)訪問拷获，但插入，刪除操作也因此變得比較低效减细，平均情況時(shí)間復(fù)雜度為O(n)匆瓜。在平時(shí)的業(yè)務(wù)開發(fā)中，我們可以直接使用編程語言中提供的容器類，但是驮吱，如果是特別底層的開發(fā)茧妒，直接使用數(shù)組可能會更合適。
