“閱讀本文大概需要6分鐘”

前言：

你好，我是久遠(yuǎn)，前面兩篇文章：

• 【久遠(yuǎn)講算法①】什么是時(shí)間復(fù)雜度

• 【久遠(yuǎn)講算法】什么是空間復(fù)雜度？
  

我們對(duì)算法以及時(shí)空復(fù)雜度進(jìn)行了詳細(xì)的講解，但是，這其實(shí)是遠(yuǎn)遠(yuǎn)不夠的，時(shí)空復(fù)雜度只是我們算法學(xué)習(xí)中的冰山一角，下面讓我們通過(guò)數(shù)組的學(xué)習(xí)來(lái)正式打開(kāi)算法與數(shù)據(jù)結(jié)構(gòu)的大門(mén)吧！

以下是我之后文章的具體走向，感興趣的小伙伴可以跟著路線進(jìn)行自學(xué)哦！

基礎(chǔ)篇暫定走向?yàn)椋簲?shù)組→鏈表→棧和隊(duì)列→樹(shù)→遞歸

基礎(chǔ)篇更完以后我將會(huì)開(kāi)啟力扣刷題套路篇哦，帶大家一起提高對(duì)編程語(yǔ)言以及算法的熟練度。

什么是數(shù)組

關(guān)于數(shù)組，雖然它是數(shù)據(jù)結(jié)構(gòu)世界里最常用以及最簡(jiǎn)單的，但是之前仍有同學(xué)向我反饋：數(shù)組難以理解！那我們就來(lái)對(duì)數(shù)組進(jìn)行詳細(xì)的講解，幫助大家解惑。

首先我們?cè)诖寺暶?，python 本身的庫(kù)中其實(shí)是沒(méi)有數(shù)組這個(gè)內(nèi)置類(lèi)型的，但存在有列表 ( list )這個(gè)內(nèi)置類(lèi)型，列表和數(shù)組在長(zhǎng)相以及實(shí)際應(yīng)用上是相似的，因此我嘗試拿列表來(lái)進(jìn)行數(shù)組相關(guān)知識(shí)的講解。（實(shí)際上在 python 的 numpy 庫(kù)中是存在有數(shù)組這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)的，之后我們會(huì)專(zhuān)門(mén)寫(xiě)一篇文章來(lái)分析數(shù)組和列表的異同。）

在計(jì)算機(jī)科學(xué)中，數(shù)組數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱(chēng)數(shù)組，英文名為 array ，是由相同類(lèi)型的元素的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)的內(nèi)存來(lái)存儲(chǔ)。利用元素的索引可以計(jì)算出該元素對(duì)應(yīng)的存儲(chǔ)地址。

是不是看完這一長(zhǎng)串理論，已經(jīng)開(kāi)始暈了？那我們現(xiàn)在提煉這段話并就來(lái)用現(xiàn)實(shí)生活的例子來(lái)解析這段話，帶大家認(rèn)識(shí)到底什么是數(shù)組。

假設(shè)我們是指揮官，我們編程時(shí)使用數(shù)組，就相當(dāng)于我們作為指揮官給指定人數(shù)的士兵布置了一個(gè)團(tuán)隊(duì)任務(wù)。而這個(gè)指定人數(shù)的隊(duì)伍，就可以視為一個(gè)數(shù)組。

• 數(shù)組由相同類(lèi)型的元素的集合所組成。這就像是現(xiàn)實(shí)中的一列士兵，他們的職業(yè)都是軍人，即所謂的類(lèi)型相同，他們都是同一個(gè)連或者同一個(gè)團(tuán)的，即同一個(gè)集合。

• 數(shù)組分配一塊連續(xù)的內(nèi)存來(lái)存儲(chǔ)。即同一列士兵，在做任務(wù)時(shí)，一般都會(huì)吃住在同一片區(qū)域。

• 利用元素的索引可以計(jì)算出該元素對(duì)應(yīng)的存儲(chǔ)地址。士兵每天訓(xùn)練時(shí)要進(jìn)行有序的排隊(duì)，當(dāng)喊到第幾號(hào)士兵時(shí)，可以通過(guò)這位士兵的回答，得知他的各種信息，例如執(zhí)行任務(wù)期間，住在哪片區(qū)域具體哪個(gè)位置。我們從平常計(jì)數(shù)報(bào)數(shù)都是從 1 開(kāi)始，而計(jì)算機(jī)默認(rèn)是從 0 開(kāi)始，這點(diǎn)要記清楚，以防之后進(jìn)行和數(shù)組相關(guān)的操作產(chǎn)生混亂。

因此我們可知，數(shù)組就如同一列整齊的士兵，他們都是正規(guī)的軍人，他們?cè)陉?duì)伍里有指定的位置，且通過(guò)叫號(hào)，可以知曉他們的訊息。正如軍隊(duì)里的士兵存在編號(hào)一樣，數(shù)組中的每一個(gè)元素也有著自己的下標(biāo)，只不過(guò)這個(gè)下標(biāo)從 0 開(kāi)始，一直到數(shù)組長(zhǎng)度 -1。

數(shù)組一般用來(lái)存儲(chǔ)具有 "一對(duì)一" 邏輯關(guān)系數(shù)據(jù)的線性存儲(chǔ)結(jié)構(gòu)，即是在內(nèi)存中順序存儲(chǔ)，因此可以很好地實(shí)現(xiàn)邏輯上的順序表。

數(shù)組在內(nèi)存中的順序存儲(chǔ)，具體是什么樣子呢？

內(nèi)存是由一個(gè)個(gè)連續(xù)的內(nèi)存單元組成的，每一個(gè)內(nèi)存單元都有自己的地址。在這些內(nèi)存單元中，有些被其他數(shù)據(jù)占用了，有些是空閑的。數(shù)組中的每一個(gè)元素，都存儲(chǔ)在小小的內(nèi)存單元中，并且元素之間緊密排列，既不能打亂元素的存儲(chǔ)順序，也不能跳過(guò)某個(gè)存儲(chǔ)單元進(jìn)行存儲(chǔ)。

這就像是宿舍分配的床位，每個(gè)宿舍有幾個(gè)指定的床位，床位號(hào)一般都是連續(xù)的，每個(gè)床位號(hào)對(duì)應(yīng)一個(gè)學(xué)生，這些學(xué)生可能有人每天都在宿舍住，有的可能搬出去住。床位號(hào)都是按順序來(lái)的，進(jìn)行安排時(shí)也不會(huì)考慮跳過(guò)哪個(gè)號(hào)進(jìn)行床位分配。

理論性的介紹先告一段落，單單了解數(shù)組的理論知識(shí)還遠(yuǎn)遠(yuǎn)不夠，接下來(lái)我們將系統(tǒng)性的介紹數(shù)組在編程中的使用。

數(shù)組的使用

任何數(shù)據(jù)結(jié)構(gòu)的操作基本離不開(kāi)，增刪改查這四種情況。接下來(lái)就讓我給大家介紹數(shù)組的增刪改查怎么實(shí)現(xiàn)。

數(shù)組元素的查詢(xún)

// 初始化
String[] array = new String[]{'red', 'green', 'blue', 'yellow', 'white', 'black'};
// 通過(guò)下標(biāo)進(jìn)行索引
System.out.println(array[0]);
System.out.println(array[1]);
System.out.println(array[2]);

list_array=['red', 'green', 'blue', 'yellow', 'white', 'black']
print( list_array[0] )#red
print( list_array[1] )#green
print( list_array[2] )#blue

對(duì) python 代碼進(jìn)行講解：

我們新建了一個(gè)長(zhǎng)度為 6 的數(shù)組，并查詢(xún)數(shù)組 list_array 下標(biāo)為 0，1，2的元素，并將他們打印出來(lái)。

對(duì)于數(shù)組來(lái)說(shuō)，讀取元素是最簡(jiǎn)單的操作。由于數(shù)組在內(nèi)存中順序存儲(chǔ)，所以只要給出一個(gè)數(shù)組下標(biāo)，就可以讀取到對(duì)應(yīng)的數(shù)組元素。

例如我們當(dāng)前新建的 list_array 數(shù)組，我們要讀取數(shù)組下標(biāo)為 3 的元素，就寫(xiě)作 array_list[3]；讀取的元素即為 ?yellow ，讀取數(shù)組下標(biāo)為 5 的元素，就寫(xiě)作 array_list[5]，讀取的數(shù)組為 black ，需要注意的是，輸入的下標(biāo)必須在數(shù)組的長(zhǎng)度范圍之內(nèi)，否則會(huì)出現(xiàn)數(shù)組越界。

• tips:

  在 python 中，使用 list 進(jìn)行數(shù)組的新建，然后索引時(shí)，它其實(shí)是不會(huì)報(bào)錯(cuò)的，這也是數(shù)組和列表的一大區(qū)別，其實(shí)本質(zhì)還是因?yàn)榱斜眍?lèi)似于動(dòng)態(tài)數(shù)組，我們?cè)趧e的編程語(yǔ)言中使用的數(shù)組，明確而言是有指定的長(zhǎng)度的， 超越指定的長(zhǎng)度時(shí)，它會(huì)進(jìn)行越界報(bào)錯(cuò)，而動(dòng)態(tài)數(shù)組的長(zhǎng)度是沒(méi)有準(zhǔn)確規(guī)定，只要不超出內(nèi)存，即可在數(shù)組末尾一直添加元素，這點(diǎn)是不是和python中的列表很像呢？

數(shù)組元素的更改

String[] array = new String[]{'red', 'green', 'blue', 'yellow', 'white', 'black'};
array[0] = 'orange';

list_array=['red', 'green', 'blue', 'yellow', 'white', 'black']
list_array[0] = 'orange' 

對(duì) python 代碼進(jìn)行講解：

依舊是我們的 list_array ?,現(xiàn)在我想把第一位的紅色變成橘色，那么我們直接使用下標(biāo)索引，找到 'red' ,然后將其賦值為 'orange' 即可。

要把數(shù)組中某一個(gè)元素的值改為一個(gè)新值，也是非常簡(jiǎn)單的操作。我們直接利用下標(biāo)索引到它，然后將其賦值為新的值就可以了。

時(shí)間復(fù)雜度分析

• tips:

  關(guān)于時(shí)間復(fù)雜度的講解，參考我之前的文章。

數(shù)組元素的插入

數(shù)組元素的插入分為以下幾種：

• 尾部插入
• 中間插入
• 超范圍插入

• 尾部插入

在 java 和 c 語(yǔ)言中，尾部插入是最簡(jiǎn)單的方法,我們只需要對(duì)數(shù)組進(jìn)行一次循環(huán)找到要插入的位置，然后進(jìn)行賦值即可。

• 中間插入

而進(jìn)行中間的插入時(shí)，我們就要考慮這些：

• 確認(rèn)數(shù)組本身是否還有空余的位置。如果沒(méi)有空余的位置，那么我們就要進(jìn)行超范圍插入了。如果有空余的位置，我們進(jìn)行下面的操作。
• 挪位置。先為了給這個(gè)元素讓出一個(gè)位置，這個(gè)元素指定的位置之后的元素都要向后移動(dòng)一個(gè)位置，不然的話，是沒(méi)有位置留給插入的那個(gè)元素的。
• 將元素放進(jìn)騰出的那個(gè)位置。原來(lái)的元素進(jìn)行挪位操作后，該元素進(jìn)行賦值歸位，這樣元素就插入成功了。
• 數(shù)組長(zhǎng)度+1，正因?yàn)槌晒Σ迦肓艘粋€(gè)元素，所以數(shù)組的長(zhǎng)度進(jìn)行了變化。
• 超范圍插入

什么是超范圍插入？比如我定義了一個(gè)數(shù)組，長(zhǎng)度為 6 ，而從 0 到 5 這6個(gè)位置，都有元素，數(shù)組已經(jīng)滿了，但是我們依舊想要向其中插入插入元素，這個(gè)時(shí)候我們就需要擴(kuò)大數(shù)組的長(zhǎng)度了，可是數(shù)組的長(zhǎng)度在創(chuàng)建時(shí)就已經(jīng)確定了，不是說(shuō)變就可以輕易的改變的，所以我們通常的操作便是，創(chuàng)建一個(gè)新數(shù)組，長(zhǎng)度是舊數(shù)組的 2 倍，再把舊數(shù)組中的元素統(tǒng)統(tǒng)復(fù)制過(guò)去，這樣就實(shí)現(xiàn)了數(shù)組的擴(kuò)容。

以下是 java 代碼實(shí)現(xiàn)的，新建一個(gè)數(shù)組，對(duì)其進(jìn)行插入操作。雖然和我上面說(shuō)的步驟幾乎是一樣的，但是代碼量可以說(shuō)是很多了。

private int[] array;
private int size;

public MyArray(int capacity){
    this.array = new int[capacity];
    size = 0;
}

/**
 * 數(shù)組插入元素
 * * index 插入的位置
 * element 插入的元素
 */
public void insert(int index, int element)  {
    //判斷訪問(wèn)下標(biāo)是否超出范圍
    if(index<0 || index>size){
        System.out.println("超出數(shù)組實(shí)際元素范圍！");
    }
    //如果實(shí)際元素達(dá)到數(shù)組容量上限，則對(duì)數(shù)組進(jìn)行擴(kuò)容
    if(size >= array.length){
        resize();
    }
    //從右向左循環(huán)，將元素逐個(gè)向右挪1位
    for(int i=size-1; i>=index; i--){
        array[i+1] = array[i];
    }
    //騰出的位置放入新元素
    array[index] = element;
    size++;
}
/**
* 數(shù)組擴(kuò)容
*/
public void resize(){
    int[] arrayNew = new int[array.length*2];
    //從舊數(shù)組復(fù)制到新數(shù)組
    System.arraycopy(array, 0, arrayNew, 0, array.length);
    array = arrayNew;
}

/**
* 輸出數(shù)組
*/
public void output(){
    for(int i=0; i        System.out.println(array[i]);
    }
}

public static void main(String[] args) {
    MyArray myArray = new MyArray(10);
    myArray.insert(0,7);
    myArray.insert(1,5);
    myArray.insert(2,9);
    myArray.insert(3,8);
    myArray.insert(1,4);
    myArray.output();
}

而在 python 中，我們?cè)诂F(xiàn)實(shí)的使用過(guò)程中，無(wú)需擔(dān)心自己是否也要像使用 java 那樣，只為處理一個(gè)插入操作，就寫(xiě)了如此多的代碼，我們只要調(diào)用列表自帶的方法就可以了。

• 列表中的 append 方法

列表中的 append 方法，對(duì)應(yīng)數(shù)組中的尾部插入，它的底層實(shí)現(xiàn)形式類(lèi)似于上文提到的java中的實(shí)現(xiàn)形式。

list_array = ['red', 'green', 'blue']
list_array.append('black')
print ("更新后的列表 : ", list_array) 
#更新后的列表為['red', 'green', 'blue','black']

對(duì) python 代碼進(jìn)行講解：

我們新生成的列表對(duì)其直接使用append方法，在其中輸入我們要添加的元素即可，然后我們的元素就被添加到了列表的末尾了。

• 列表中的 insert 方法

列表中的 insert 方法，對(duì)應(yīng)數(shù)組中的中間插入，只需要一步調(diào)用方法，即可完成 java 中那么多的判斷以及元素的插入，可見(jiàn) python 的強(qiáng)大。又因?yàn)榱斜肀旧砜梢砸暈閯?dòng)態(tài)數(shù)組，其實(shí)對(duì)于長(zhǎng)度的要求并沒(méi)有數(shù)組那么苛刻，它是可以隨意插入元素的，無(wú)需擔(dān)心長(zhǎng)度，容量問(wèn)題。

list_array = ['red', 'green', 'blue']
list_array.insert(0, 'black')
print ('列表插入元素后為 : ', list_array)
#更新后的列表為 ['black', 'red', 'green', 'blue']

對(duì) python 代碼進(jìn)行講解：

對(duì)新生成的列表使用 insert 方法，insert 方法有兩個(gè)參數(shù)，第一個(gè)參數(shù)為，我們要將元素插入到列表的哪個(gè)位置，第二個(gè)參數(shù)為元素內(nèi)容。該段代碼即為使用 insert 方法將 'black' 插入到列表的頭部。

• 列表中的 extend 方法

列表中的 extend 方法，用于在列表末尾一次性追加另一個(gè)序列中的多個(gè)值（用新列表擴(kuò)展原來(lái)的列表）?？梢砸暈槭菙?shù)組擴(kuò)容的一種特殊情況。

list_array = ['red', 'green', 'blue']
list2=list(range(5)) # 創(chuàng)建 0-4 的列表
list1.extend(list2)  # 擴(kuò)展列表
print ("擴(kuò)展后的列表：", list1)
#擴(kuò)展后的列表：['red', 'green', 'blue', 0, 1, 2, 3, 4]

數(shù)組元素的刪除

數(shù)組的刪除操作和插入操作的過(guò)程相反，如果是在數(shù)組的最后刪除元素，那么直接去除元素即可，但是如果是在頭部或者數(shù)組的中間刪除元素，那么其后的元素都需要向前挪動(dòng) 1 位。

刪除簡(jiǎn)單的地方在于，我們無(wú)需關(guān)心下標(biāo)是否會(huì)越界，容量是肯定不會(huì)超過(guò)申請(qǐng)的大小的。

public int delete(int index)  {
    //判斷訪問(wèn)下標(biāo)是否超出范圍
    if(index<0 || index>=size){
        System.out.println("超出數(shù)組實(shí)際元素范圍！");
    }
    int deleted= array[index];
    //從左向右循環(huán)，將元素逐個(gè)向左挪1位
    for(int i=index; i1; i++){
        array[i] = array[i+1];
    }
    size--;
    return deleted;
}

python 列表中有兩種方法和數(shù)組的刪除操作匹配，即 pop 和 remove 方法。

• 列表中的pop方法

pop() 函數(shù)用于移除列表中的一個(gè)元素（默認(rèn)最后一個(gè)元素），并且返回該元素的值。

list1 = ['red', 'green', 'blue']
list1.pop()
print ("列表現(xiàn)在為 : ", list1)
#列表現(xiàn)在為 :  ['red', 'green']
list1.pop(1)
print ("列表現(xiàn)在為 : ", list1)
#列表現(xiàn)在為 :  ['red']

對(duì) python 代碼進(jìn)行講解：

新建一個(gè) list1 列表，我們對(duì)其使用 pop() ，那么 list1 列表中最后一個(gè)元素被移除，這個(gè)元素即為 'blue' ，然后繼續(xù)對(duì) list1 使用 pop 操作，此時(shí) list1 中最后一個(gè)元素為 'green'，將其移除， list1 中最后只有 'red' 一個(gè)元素了。

• 列表中的 remove 方法

remove() 函數(shù)用于移除列表中某個(gè)值的第一個(gè)匹配項(xiàng)。即當(dāng)列表中有一樣的元素的時(shí)候，使用 remove 刪除這個(gè)元素， remove 將會(huì)刪除下標(biāo)較小的。

list1 = ['red', 'green', 'blue']
list1.remove('red')
print ("列表現(xiàn)在為 : ", list1)
# 列表現(xiàn)在為 :  ['green','blue']
list1.remove('green')
print ("列表現(xiàn)在為 : ", list1)
# 列表現(xiàn)在為 :  ['blue']

# 有重復(fù)元素的情況
list2 = ['red','red','green','blue','blue']
list2.remove('red')
print("列表現(xiàn)在為：",list2)
# 列表現(xiàn)在為：['red', 'green', 'blue', 'blue']
list2.remove('green')
print("列表現(xiàn)在為：",list2)
# 列表現(xiàn)在為：['red', 'blue', 'blue']

對(duì) python 代碼進(jìn)行講解：

新建一個(gè) list2 列表，我們對(duì)其使用 remove('red') ，那么 list2 列表中第一個(gè) 'red' 將會(huì)被移除，然后繼續(xù)對(duì) list2 使用 remove 操作，這次我們移除列表中第一個(gè) 'blue' ，打印列表可以發(fā)現(xiàn)，我們?cè)斜碇械?0 號(hào)位的 'red' 和 3 號(hào)位的 'blue' 都被刪掉了，而剩下的 'red' 和 'blue' 沒(méi)有被移除。

時(shí)間復(fù)雜度分析

數(shù)組的插入，我們首先要考慮數(shù)組的長(zhǎng)度和容量，如果容量空余，我們?cè)诓迦肭斑€要為元素騰出位置，因此我們?cè)诖说臅r(shí)間復(fù)雜度 為 ?, 如果元素的容量已滿，我們要擴(kuò)容數(shù)組，那么這個(gè)操作的時(shí)間復(fù)雜度仍為?，綜合考慮，數(shù)組的插入操作時(shí)間復(fù)雜度為? .

數(shù)組的刪除，無(wú)需考慮數(shù)組的長(zhǎng)度和容量問(wèn)題，只需要在刪除元素之后，改變其它元素的位置即可，因此數(shù)組的刪除操作消耗的時(shí)間在此的時(shí)間復(fù)雜度為 ? .

數(shù)組的優(yōu)勢(shì)和劣勢(shì)

數(shù)組的優(yōu)勢(shì)體現(xiàn)在查詢(xún)和修改元素上，我們只需要知道元素的數(shù)組下標(biāo)即可對(duì)其進(jìn)行查詢(xún)和修改，非常的方便。而這種特性也被二分查找法充分的利用了。

數(shù)組的劣勢(shì)體現(xiàn)在它的插入操作和刪除操作上，當(dāng)插入一個(gè)元素或者刪除一個(gè)元素時(shí)，其他的元素都需要改變，這極大地影響了程序的運(yùn)行效率。

總之?dāng)?shù)組適用于，查找，修改較多，插入，刪除較少的場(chǎng)景下。我們下周要講的鏈表則和它的情況相反。

流沙團(tuán)隊(duì)聯(lián)合AI悅創(chuàng)|久遠(yuǎn)·推出輔導(dǎo)班啦，包括「Python 語(yǔ)言輔導(dǎo)班、C++ 輔導(dǎo)班、java 輔導(dǎo)班、算法/數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)班、少兒編程、pygame 游戲開(kāi)發(fā)」，全部都是一對(duì)一教學(xué)：一對(duì)一輔導(dǎo) + 一對(duì)一答疑 + 布置作業(yè) + 項(xiàng)目實(shí)踐等。QQ、微信在線，隨時(shí)響應(yīng)！