1浩峡、內(nèi)存工作原理
今天你要去丹尼斯購(gòu)物，但你帶了雨傘和包曼振，丹尼斯要求這些東西不能帶進(jìn)商場(chǎng)几迄，所以你只能到存儲(chǔ)柜存放這些物品...
存儲(chǔ)柜有很多柜子，每個(gè)柜子都有地址冰评，假設(shè)一個(gè)箱子只能存放一個(gè)物品映胁，你就需要兩個(gè)箱子存放傘和包
你將傘和包分別放進(jìn)相鄰的兩個(gè)柜子中，這時(shí)存儲(chǔ)柜吐出紙條上面寫(xiě)著甲雅，你放物品的柜子地址
以防你找不到物品

其實(shí)計(jì)算機(jī)的內(nèi)存就像是個(gè)大型存儲(chǔ)柜解孙，里面有很多小柜子，每個(gè)柜子都有自己的地址

需要將數(shù)據(jù)存儲(chǔ)到內(nèi)存時(shí)抛人，你請(qǐng)求計(jì)算機(jī)弛姜，它將給你一個(gè)存儲(chǔ)地址，你將數(shù)據(jù)存進(jìn)對(duì)應(yīng)的位置

在存儲(chǔ)多項(xiàng)數(shù)據(jù)時(shí)妖枚，有兩種基本存儲(chǔ)方式 數(shù)組和鏈表

2廷臼，數(shù)組和鏈表
數(shù)組是線性相連的，比如你想將4個(gè)數(shù)據(jù)以數(shù)組的形式绝页，放入內(nèi)存中荠商，計(jì)算機(jī)會(huì)返回給你4個(gè)相連的存儲(chǔ)地址，用來(lái)把4個(gè)數(shù)據(jù)線性的放在對(duì)應(yīng)的位置中

看起來(lái)很完美续誉？
但這里有一個(gè)問(wèn)題莱没，假如 內(nèi)存中 1 -2- 3 號(hào)地址，都沒(méi)有存放數(shù)據(jù)酷鸦，但4號(hào)存放了數(shù)據(jù)饰躲，很尷尬牙咏，你的數(shù)組數(shù)據(jù)無(wú)法存放1 2 3 號(hào)對(duì)應(yīng)的位置，因?yàn)槟阋?個(gè)數(shù)據(jù)嘹裂，并且數(shù)組要求數(shù)據(jù)必須相連妄壶，如果放了1 -2- 3的位置，4被其他數(shù)據(jù)占用焦蘑，數(shù)組中最后的數(shù)據(jù)只能放5號(hào)盯拱，這是做不到的盒发，數(shù)組要求例嘱，數(shù)據(jù)要連續(xù)相連存儲(chǔ)...所以你只能放在4后面，也就是 5-6-7-8的位置宁舰，1-2-3還空著...資源被浪費(fèi)了
另一個(gè)問(wèn)題拼卵，數(shù)組存儲(chǔ)是相連的，如果長(zhǎng)度為4的數(shù)組存儲(chǔ)在內(nèi)存中蛮艰，而末位相鄰的內(nèi)存中存儲(chǔ)了其他數(shù)據(jù)腋腮，此時(shí)添加一個(gè)數(shù)據(jù)會(huì)怎樣?
很抱歉，數(shù)組就像是4個(gè)相連的抽屜壤蚜，第五個(gè)位置被其他數(shù)據(jù)占用即寡，第五個(gè)放不進(jìn)去，那怎么辦袜刷，只能重新創(chuàng)建一個(gè)5個(gè)相連的抽屜聪富，然后放進(jìn)5個(gè)數(shù)據(jù)（把原來(lái)的4個(gè)取出來(lái)，放到新的里面）...這意味著著蟹，要么你很清楚有多少數(shù)據(jù)墩蔓，精確的設(shè)置數(shù)組長(zhǎng)度，要么你多加長(zhǎng)度（多加幾個(gè)抽屜）萧豆，以應(yīng)不便奸披，這就像我邀請(qǐng)10個(gè)朋友吃飯，有朋友說(shuō)他也會(huì)帶2-4個(gè)朋友來(lái)涮雷，具體幾個(gè)他也不知道...所以阵面，在長(zhǎng)桌上，你準(zhǔn)備幾把椅子呢洪鸭？至少14把...結(jié)果當(dāng)天朋友只帶來(lái)了一個(gè)...所以多出來(lái)的3把椅子就浪費(fèi)了
申請(qǐng)更多數(shù)據(jù)存儲(chǔ)空間样刷，有可能造成浪費(fèi)...
這就是數(shù)組的缺點(diǎn)...數(shù)據(jù)是依次相連，次序是固定的卿嘲，所以颂斜，想要調(diào)整數(shù)據(jù)位置或者插入數(shù)據(jù)并不容易

鏈表
鏈表中的元素可以存儲(chǔ)在內(nèi)存中的任何位置
鏈表中的每個(gè)元素都存儲(chǔ)了下一個(gè)元素的地址，從而使一系列隨機(jī)的內(nèi)存地址串在一起
因此鏈表擴(kuò)容很簡(jiǎn)單拾枣，只需將數(shù)據(jù)放入內(nèi)存沃疮，并將其地址存儲(chǔ)到上個(gè)元素中
鏈表的優(yōu)勢(shì)就在于插入元素方便簡(jiǎn)單盒让，內(nèi)存利用度極高
看起來(lái)很完美？
如果一個(gè)鏈表存儲(chǔ)了5個(gè)數(shù)據(jù)司蔬，我取出最后一個(gè)數(shù)據(jù)邑茄，我必須要從第一個(gè)鏈表元素，找到第二個(gè)鏈表元素的地址俊啼，找到第2個(gè)元素肺缕，查找第三個(gè)鏈表的地址，直到找到第四個(gè)元素授帕，我才知道第五個(gè)元素的地址同木，才能取出數(shù)據(jù)....
鏈表的數(shù)據(jù)存儲(chǔ)在內(nèi)存中地址不是相連的（存放在內(nèi)存中的任意位置），所以我們只能從頭開(kāi)始查找下個(gè)位置的元素跛十，直到找到我們想要的彤路。
鏈表：查找效率很低，插入元素方便

數(shù)組存儲(chǔ)在內(nèi)存中的地址是依次相連芥映，我們知道起始位洲尊，其他的位置也就知道了，這樣我們就可以很方便的取出我們想要位置的數(shù)據(jù)
數(shù)組：查詢(xún)效率高奈偏，但擴(kuò)容插入艱難

術(shù)語(yǔ)
數(shù)組中的元素是帶編號(hào)的 從0開(kāi)始坞嘀，依據(jù)位置依次加1 （這里是編號(hào)，不是內(nèi)存地址）
比如 數(shù)組 ——10—— 20 —— 30 —— 40
編號(hào) —— 0 —— 1 —— 2 —— 3
從0開(kāi)始惊来，而不是1丽涩，這是因?yàn)閺拈_(kāi)始可以讓數(shù)組代碼編寫(xiě)起來(lái)更加容易，所有就從0開(kāi)始

編號(hào)的官方稱(chēng)呼為 索引唁盏，請(qǐng)記住 索引 即為位置内狸，例如 元素20的索引是1

在中間插入

數(shù)組 [0 ,1, 2 ,3 ,4 ]
索引 [0 ,1, 2 ,3 ,4 ]
我們想在 索引 1 處插入元素 0.5

插入后
數(shù)組 [0 , 0.5，1, 2 ,3 ,4 ]
索引 [0 , 1厘擂， 2, 3 ,4 ,5 ]

插入0.5后昆淡，索引1后面的所有元素，都必須向后挪動(dòng)1個(gè)位置...
極端情況下刽严，數(shù)組（長(zhǎng)度是5）所在內(nèi)存區(qū)域第6個(gè)位置被其他數(shù)據(jù)占有昂灵，沒(méi)有足夠的空間進(jìn)行插入，
那就需要將整個(gè)數(shù)據(jù)復(fù)制到能夠存放連續(xù)6個(gè)元素的內(nèi)存區(qū)域中去

鏈表 0——>1——>2——>3——>4
我們想在0-1間插入 0.5
那只需要將 0的箭頭（下個(gè)元素的存儲(chǔ)地址）指向0.5 0——>0.5
同時(shí)將0.5的箭頭指向1（0.5中存儲(chǔ)1的地址） 0.5——>1

so
對(duì)于插入 數(shù)組的時(shí)間復(fù)雜度為 O(n) 鏈表的 為O（1）

刪除

數(shù)組 [0 ,1, 2 ,3 ,4 ]
索引 [0 ,1, 2 ,3 ,4 ]
我們想刪除索引0處的元素

刪除后
數(shù)組 [1, 2 ,3 ,4 ]
索引 [0 ,1, 2 ,3 ]

0索引后面的元素依次向前移動(dòng)1

鏈表 0——>1——>2——>3——>4
我想刪除 元素0
請(qǐng)直接刪除... 記錄1 為起始元素即可

so 對(duì)于刪除 數(shù)組的時(shí)間復(fù)雜度為 O(n) 鏈表的 為O（1）

鏈表擅長(zhǎng)插入和刪除
數(shù)組擅長(zhǎng)查看訪問(wèn)

選擇排序
方法：每次挑出元素中最大（或最形杼选）的元素眨补，然后排序
例如 數(shù)組 4-9-5-6-7 由大到小排列
第一次 選出9 [9] 剩余4-5-6-7
第二次 選出7 [9,7] 剩余4-5-6
第三次 選出6 [9,7,6] 剩余4-5
第四次 選出5 [9,7,6,5] 剩余4
第五次 選出4 [9,7,6,5,4]

# 選擇排序===============================================
# 1. 使用交換方法，將原有數(shù)組進(jìn)行從大到小的排列
def selection_sort(array):
    length = len(array)
    for i in range(length):
        max_ = array[i]
        max_index = i
        for k in range(i + 1, length):
            if max_ < array[k]:
                max_ = array[k]
                max_index = k
        # 交換位置
        if max_index != i:
            small = array[i]
            array[i] = max_
            array[max_index] = small

    print(array)


# 選擇排序===============================================
# 2.使用數(shù)據(jù)
def selection_sort_n(array):
    new_array = []
    for i in range(len(array)):
        index = findMaxIndex(array)
        new_array.append(array.pop(index))
    print(new_array)


def findMaxIndex(array):
    max_index = 0
    max_value = array[0]
    for i in range(1, len(array)):
        if max_value < array[i]:
            max_index = i
            max_value = array[i]
    return max_index


if __name__ == '__main__':
    selectionSort = [10, 8, 33, 26, 11, 5, 55]
    print(selectionSort)
    selection_sort(selectionSort)
    selectionSort = [10, 8, 33, 26, 11, 5, 55]
    selection_sort_n(selectionSort)

總結(jié)
1.數(shù)據(jù)可以數(shù)組和鏈表的形式存儲(chǔ)在內(nèi)存中
2.數(shù)組的元素是有序相鄰的
3.鏈表的元素是分開(kāi)的倒脓，其每個(gè)元素存儲(chǔ)著下個(gè)元素的地址
4.數(shù)組的讀取速度很快
5.鏈表的插入刪除速度很快
6.在同一個(gè)數(shù)組中撑螺，所以元素都必須是同一類(lèi)型（都是int 或 double）