程序員時時刻刻需要將數(shù)據(jù)存儲到內(nèi)存時蛤售，你請求計(jì)算機(jī)提供存儲空間烘豹，計(jì)算機(jī)給你一個存儲地址誓焦。需要存 儲多項(xiàng)數(shù)據(jù)時胆敞，有兩種基本方式——數(shù)組和鏈表。但它們并非都適用于所有的情形杂伟，因此知道它 們的差別很重要移层。接下來介紹數(shù)組和鏈表以及它們的優(yōu)缺點(diǎn)。
（2.1） 數(shù)組和鏈表
有時候赫粥，需要在內(nèi)存中存儲一系列元素观话。假設(shè)你要編寫一個管理待辦事
項(xiàng)的應(yīng)用程序，為此需要將這些待辦事項(xiàng)存儲在內(nèi)存中越平。
應(yīng)使用數(shù)組還是鏈表呢?鑒于數(shù)組更容易掌握频蛔，我們先將待辦事項(xiàng)存 儲在數(shù)組中。使用數(shù)組意味著所有待辦事項(xiàng)在內(nèi)存中都是相連的(緊靠在 一起的)秦叛。
現(xiàn)在假設(shè)你要添加第四個待辦事項(xiàng)晦溪，但后面的那個抽屜放著別人的東西!
這就像你與朋友去看電影，找到地方就坐后又來了一位朋友挣跋，但原來坐的地方?jīng)]有空位置三圆， 只得再找一個可坐下所有人的地方。在這種情況下避咆，你需要請求計(jì)算機(jī)重新分配一塊可容納4個 待辦事項(xiàng)的內(nèi)存舟肉，再將所有待辦事項(xiàng)都移到那里。
如果又來了一位朋友查库，而當(dāng)前坐的地方也沒有空位路媚，你們就得再次轉(zhuǎn)移!真是太麻煩了。同 樣樊销，在數(shù)組中添加新元素也可能很麻煩整慎。如果沒有了空間，就得移到內(nèi)存的其他地方现柠，因此添加 新元素的速度會很慢院领。一種解決之道是“預(yù)留座位”:即便當(dāng)前只有3個待辦事項(xiàng)，也請計(jì)算機(jī)提 供10個位置够吩，以防需要添加待辦事項(xiàng)比然。這樣，只要待辦事項(xiàng)不超過10個周循，就無需轉(zhuǎn)移强法。這是一個 不錯的權(quán)變措施万俗，但你應(yīng)該明白，它存在如下兩個缺點(diǎn)饮怯。
- 你額外請求的位置可能根本用不上闰歪，這將浪費(fèi)內(nèi)存。你沒有使用蓖墅，別人也用不了库倘。
- 待辦事項(xiàng)超過10個后，你還得轉(zhuǎn)移论矾。
因此教翩，這種權(quán)宜措施雖然不錯，但絕非完美的解決方案贪壳。對于這種問題饱亿，可使用鏈表來解決
（2.2）鏈表
鏈表中的元素可存儲在內(nèi)存的任何地方。
鏈表的每個元素都存儲了下一個元素的地址闰靴，從而使一系列隨機(jī)的內(nèi)存地址串在一起彪笼。
這猶如尋寶游戲。你前往第一個地址蚂且，那里有一張紙條寫著“下一個元素的地址為123”配猫。因 此，你前往地址123膘掰，那里又有一張紙條章姓，寫著“下一個元素的地址為847”，以此類推识埋。在鏈表 中添加元素很容易:只需將其放入內(nèi)存凡伊，并將其地址存儲到前一個元素中。
使用鏈表時窒舟，根本就不需要移動元素系忙。這還可避免另一個問題。假設(shè)你與五位朋友去看一部 很火的電影惠豺。你們六人想坐在一起银还，但看電影的人較多，沒有六個在一起的座位洁墙。使用數(shù)組時有 時就會遇到這樣的情況蛹疯。假設(shè)你要為數(shù)組分配10 000個位置，內(nèi)存中有10 000個位置热监，但不都靠 在一起捺弦。在這種情況下，你將無法為該數(shù)組分配內(nèi)存!鏈表相當(dāng)于說“我們分開來坐”，因此列吼， 只要有足夠的內(nèi)存空間幽崩，就能為鏈表分配內(nèi)存。
鏈表的優(yōu)勢在插入元素方面寞钥，那數(shù)組的優(yōu)勢又是什么呢?
（2.3）數(shù)組
排行榜網(wǎng)站使用卑鄙的手段來增加頁面瀏覽量慌申。它們不在一個頁面中 顯示整個排行榜，而將排行榜的每項(xiàng)內(nèi)容都放在一個頁面中理郑，并讓你單擊 Next來查看下一項(xiàng)內(nèi)容蹄溉。例如，顯示十大電視反派時香浩，不在一個頁面中顯 示整個排行榜类缤，而是先顯示第十大反派(Newman)。你必須在每個頁面中 單擊Next邻吭，才能看到第一大反派(Gustavo Fring)。這讓網(wǎng)站能夠在10個頁 面中顯示廣告宴霸，但用戶需要單擊Next 九次才能看到第一個囱晴，真的是很煩。 如果整個排行榜都顯示在一個頁面中瓢谢，將方便得多畸写。這樣，用戶可單擊排行榜中的人名來獲得更 詳細(xì)的信息氓扛。
鏈表存在類似的問題枯芬。在需要讀取鏈表的最后一個元素時，你不能直接讀取采郎，因?yàn)槟悴恢?它所處的地址千所，必須先訪問元素#1，從中獲取元素#2的地址蒜埋，再訪問元素#2并從中獲取元素#3 的地址淫痰，以此類推，直到訪問最后一個元素整份。需要同時讀取所有元素時待错，鏈表的效率很高:你讀 取第一個元素，根據(jù)其中的地址再讀取第二個元素烈评，以此類推火俄。但如果你需要跳躍，鏈表的效率 真的很低讲冠。
數(shù)組與此不同:你知道其中每個元素的地址瓜客。
需要隨機(jī)地讀取元素時，數(shù)組的效率很高，因?yàn)榭裳?速找到數(shù)組的任何元素忆家。在鏈表中犹菇，元素并非靠在一起的，你無法迅速計(jì)算出第五個元素的內(nèi)存 地址芽卿，而必須先訪問第一個元素以獲取第二個元素的地址揭芍，再訪問第二個元素以獲取第三個元素 的地址，以此類推卸例，直到訪問第五個元素称杨。
（2.4）數(shù)組、鏈表運(yùn)行時間
下面列出了常見的數(shù)組和鏈表操作的運(yùn)行時間筷转。
問題:在數(shù)組中插入元素時姑原，為何運(yùn)行時間為O(n)呢?假設(shè)要在數(shù)組開頭插入一個元素，該怎么做呢呜舒？锭汛？？很顯然袭蝗，當(dāng)在第一個元素之前插入元素的時候唤殴，后面的所有元素都要往后移動一位。到腥。
（2.4.1）在中間插入
需要在中間插入元素時朵逝，數(shù)組和鏈表哪個更好呢?使用鏈表時，插入元素很簡單乡范，只需修改 它前面的那個元素指向的地址配名。
而使用數(shù)組時，則必須將后面的元素都向后移晋辆。
如果沒有足夠的空間渠脉，可能還得將整個數(shù)組復(fù)制到其他地方!因此，當(dāng)需要在中間插入元素 時栈拖，鏈表是更好的選擇连舍。
（2.4.2）刪除
如果你要刪除元素呢?鏈表也是更好的選擇，因?yàn)橹恍栊薷那耙粋€元素指向的地址即可涩哟。而使用數(shù)組時索赏，刪除元素后，必須將后面的元素都向前移贴彼。
不同于插入潜腻，刪除元素總能成功。如果內(nèi)存中沒有足夠的空間器仗，插入操作可能失敗融涣，但在任 何情況下都能夠?qū)⒃貏h除童番。
我們來看一下數(shù)組和鏈表的操作運(yùn)行時間：
需要指出的是，僅當(dāng)能夠立即訪問要刪除的元素時威鹿，刪除操作的運(yùn)行時間才為O(1)剃斧。通常我 們都記錄了鏈表的第一個元素和最后一個元素，因此刪除這些元素時運(yùn)行時間為O(1)忽你。
數(shù)組和鏈表哪個用得更多呢?顯然要看情況幼东。但數(shù)組用得很多，因?yàn)樗С蛛S機(jī)訪問科雳。有兩 種訪問方式:隨機(jī)訪問和順序訪問根蟹。順序訪問意味著從第一個元素開始逐個地讀取元素。鏈表只 能順序訪問:要讀取鏈表的第十個元素糟秘，得先讀取前九個元素简逮，并沿鏈接找到第十個元素。隨機(jī) 10 訪問意味著可直接跳到第十個元素尿赚。
（2.5）選擇排序
假設(shè)你的計(jì)算機(jī)存儲了很多樂曲散庶。對于每個樂隊(duì)，你都記錄了其作
品被播放的次數(shù)吼畏。
你要將這個列表按播放次數(shù)從多到少的順序排列督赤，從而將你喜歡的樂隊(duì)排序。該如何做呢?
一種辦法是遍歷這個列表泻蚊，找出作品播放次數(shù)最多的樂隊(duì)，并將該樂隊(duì)添加到一個新列表中
需要的總時間為 O(n × n)丑婿，即O(n2)性雄。
按照這種邏輯，需要檢查的元素?cái)?shù)越來越少羹奉，每次都少檢查一個元素秒旋，最后一次需要檢查的元素都只有一 個。運(yùn)行時間怎么還是O(n2)诀拭？
并非每次都需要檢查n個元素迁筛。第一次需要檢查n個元素，但隨后檢查的元素 數(shù)依次為n , n-1, n – 2, ..., 2和1耕挨。平均每次檢查的元素?cái)?shù)為1/2 × n细卧，因此運(yùn)行時間為O(n × 1/2 × n)。 但大O表示法省略諸如1/2這樣的常數(shù),因此簡單地寫 作O(n × n)或O(n2)筒占。
選擇排序是一種靈巧的算法贪庙，但其速度不是很快
示例代碼
# 前面沒有列出對樂隊(duì)進(jìn)行排序的代碼，但下述代碼提供了類似的功能:將數(shù)組元素按從小到 大的順序排列翰苫。先編寫一個用于找出數(shù)組中最小元素的函數(shù)止邮。
def findSmalest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1,len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
# 現(xiàn)在可以使用這個函數(shù)來編寫選擇排序算法了这橙。
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmalest(arr)
newArr.append(arr.pop(smallest))
return newArr
print(selectionSort([5, 3, 2, 44, 33]))
結(jié)果如下：
/usr/local/bin/python3.6 /Users/tsoumac2016/Desktop/算法Python/findSmallest.py
[2, 3, 5, 33, 44]
Process finished with exit code 0
小結(jié)：
- 計(jì)算機(jī)內(nèi)存猶如一大堆抽屜。
- 需要存儲多個元素時导披，可使用數(shù)組或鏈表屈扎。
- 數(shù)組的元素都在一起。
- 鏈表的元素是分開的撩匕，其中每個元素都存儲了下一個元素的地址鹰晨。
- 數(shù)組的讀取速度很快。
- 鏈表的插入和刪除速度很快滑沧。
- 在同一個數(shù)組中并村，所有元素的類型都必須相同(都為int、double等)滓技。
