學(xué)習(xí)筆記
學(xué)習(xí)書目：《算法圖解》- Aditya Bhargava

---

文章目錄

• • • 選擇排序
    • • 內(nèi)存工作原理
      • 數(shù)組
      • 鏈表
      • 讀取
      • 索引
      • 插入
      • 刪除
      • 是常見的數(shù)組和鏈表操作的運(yùn)行時(shí)間
      • 選擇排序
      • python實(shí)現(xiàn)

---

選擇排序

內(nèi)存工作原理

假如我去博物館參觀，帶了玩具熊和花盆，我想把這兩樣?xùn)|西寄存一下，那么我就在服務(wù)臺(tái)要了兩個(gè)柜子寄存它們，寄存過我就可以去參觀博物館啦！(先別管我為啥不把兩樣?xùn)|西寄存在一個(gè)柜子)

這大致就是計(jì)算機(jī)內(nèi)存的工作原理。計(jì)算機(jī)就像是很多柜子的集合體，每個(gè)柜子都有地址。

比如，當(dāng)我們需要將數(shù)據(jù)存儲(chǔ)到內(nèi)存時(shí)，我就請(qǐng)求計(jì)算機(jī)提供存儲(chǔ)空間，計(jì)算機(jī)就會(huì)給我一個(gè)存儲(chǔ)地址fe0ffeeb。

當(dāng)我們需要存儲(chǔ)多項(xiàng)數(shù)據(jù)時(shí)，有兩種基本方式：數(shù)組和鏈表。下面，我們就簡(jiǎn)要介紹一下這兩種方式。

數(shù)組

假如我想將我明天的計(jì)劃(比如：吃早飯、學(xué)《概率論與數(shù)理統(tǒng)計(jì)》、睡午覺)寫入內(nèi)存中，那么我們應(yīng)該使用數(shù)組還是鏈表呢？

如果我們將計(jì)劃存儲(chǔ)在數(shù)組中，那么使用數(shù)組則意味著所有計(jì)劃在內(nèi)存中都是相連的(緊靠在一起的)：

假設(shè)此時(shí)，我們要添加第4個(gè)計(jì)劃(吃水果)，但是我們看到后面的格子中被別人占用了，那該咋整呢？此時(shí)，我們就要請(qǐng)求計(jì)算機(jī)重新分配給我們一塊可以容納4個(gè)計(jì)劃的內(nèi)存空間，再將所有計(jì)劃都移動(dòng)到那里去。

但是，如果我又要添加1個(gè)計(jì)劃可咋整呢？難道我們要再移動(dòng)一次？

此時(shí)，一種解決之道是“預(yù)留空間”：即便當(dāng)前只有3個(gè)計(jì)劃，也請(qǐng)計(jì)算機(jī)提供10個(gè)位置，以防需要添加計(jì)劃。這樣，只要待辦事項(xiàng)不超過10個(gè)，就無需轉(zhuǎn)移。

雖然這種方法不錯(cuò)，但還是存在以下兩種缺陷：

• 我額外請(qǐng)求的位置可能根本用不上，這將浪費(fèi)內(nèi)存。
• 我沒有使用，別人也用不了。 待辦事項(xiàng)超過10個(gè)后，你還得轉(zhuǎn)移。

鏈表

相比于數(shù)組，鏈表中的元素可存儲(chǔ)在內(nèi)存的任何地方。鏈表的每個(gè)元素都存儲(chǔ)了下一個(gè)元素的地址，從而使一系列隨機(jī)的內(nèi)存地址串在一起。

在鏈表中添加元素很容易：只需將其放入內(nèi)存，并將其地址存儲(chǔ)到前一個(gè)元素中。

使用鏈表時(shí)，根本就不需要移動(dòng)元素。這還避免了使用數(shù)組時(shí)，因?yàn)閮?nèi)存中沒有足夠的連續(xù)空間(只有足夠的不連續(xù)空間)而無法分配內(nèi)存的情況。

鏈表的優(yōu)勢(shì)在插入元素方面，那數(shù)組的優(yōu)勢(shì)又是什么呢？

讀取

如果我們使用鏈表來存儲(chǔ)數(shù)據(jù)，在需要讀取鏈表的最后一個(gè)元素時(shí)，你不能直接讀取，因?yàn)槟悴恢浪幍牡刂?#xff0c;必須先訪問元素#1，從中獲取元素#2的地址，再訪問元素#2并從中獲取元素#3的地址，以此類推，直到訪問最后一個(gè)元素。需要同時(shí)讀取所有元素時(shí)，鏈表的效率很高：你讀取第一個(gè)元素，根據(jù)其中的地址再讀取第二個(gè)元素，以此類推。但如果你需要跳躍，鏈表的效率真的很低。

而數(shù)組則與此不同，因?yàn)閿?shù)組是相連的，所以如果我們知道數(shù)元素#1的地址為00，那么元素#5的地址就是04。需要隨機(jī)地讀取元素時(shí)，數(shù)組的效率很高，因?yàn)榭裳杆僬业綌?shù)組的任何元素。

索引

數(shù)組的元素帶編號(hào)，編號(hào)從0而不是從1開始：

In [14]: (1, 2, 3, 4)[0] Out[14]: 1

從0開始讓基于數(shù)組的代碼編寫起來更容易，因此程序員始終堅(jiān)持這樣做。幾乎所有的編程語言都從0開始對(duì)數(shù)組元素進(jìn)行編號(hào)。元素的位置稱為索引，因此，不說元素1的位置為0，而說元素1位于索引0處。

插入

假如，我突然想起來，明天吃完早飯后要先跑步，那么我們將跑步這個(gè)計(jì)劃插入總計(jì)劃中的時(shí)候，數(shù)組和鏈表哪一個(gè)表現(xiàn)更好呢？

使用鏈表時(shí)，插入元素很簡(jiǎn)單，只需要修改它前面的那個(gè)元素指向的地址即可：

使用數(shù)組時(shí)，則需要將后面的元素都向后移動(dòng)。但是，如果后面沒有空間了，那么還得將整個(gè)數(shù)組復(fù)制到其他地方。

刪除

如果你要?jiǎng)h除元素呢？

鏈表也是更好的選擇，因?yàn)橹恍栊薷那耙粋€(gè)元素指向的地址即可。而使用數(shù)組時(shí)，刪除元素后，必須將后面的元素都向前移。不同于插入，刪除元素總能成功。如果內(nèi)存中沒有足夠的空間，插入操作可能失敗，但在任何情況下都能夠?qū)⒃貏h除。

是常見的數(shù)組和鏈表操作的運(yùn)行時(shí)間

數(shù)組鏈表

讀取	O(1)	O(n)
插入	O(n)	O(1)
刪除	O(n)	O(1)

數(shù)組和鏈表哪個(gè)用得更多呢？顯然要看情況。但數(shù)組用得很多，因?yàn)樗С蛛S機(jī)訪問。
順序訪問意味著從第一個(gè)元素開始逐個(gè)地讀取元素。鏈表只能順序訪問：要讀取鏈表的第十個(gè)元素，得先讀取前九個(gè)元素，并沿鏈接找到第十個(gè)元素。隨機(jī)訪問意味著可直接跳到第十個(gè)元素。

選擇排序

假設(shè)A班有5位同學(xué)，對(duì)于這些同學(xué)，我的計(jì)算機(jī)里都記錄了它們的期末考試總分。現(xiàn)在我將這些同學(xué)和他們的成績(jī)裝在列表1中：

成績(jī)

A	259
B	199
C	287
D	250
E	266

我想按照成績(jī)的高低對(duì)它們進(jìn)行降序排列，那么我們?cè)撛趺醋瞿?#xff1f;

一種辦法是遍歷這個(gè)列表1，找出成績(jī)最好的同學(xué)，并將該同學(xué)添加到一個(gè)新列表(列表2)中；再次這樣做，找出成績(jī)第2好的同學(xué)，再將該同學(xué)添加到列表2，以此類推，最終我們將得到一個(gè)有序的列表2。

下面從計(jì)算機(jī)科學(xué)的角度出發(fā)，我們看看這需要多長(zhǎng)時(shí)間。別忘了，O(n)時(shí)間意味著查看列表中的每個(gè)元素一次，如果我們想要找出成績(jī)最好的同學(xué)，就要檢查列表中的每一個(gè)元素。需要的總時(shí)間為 O(n × n)，即O($n^2$).

• 需要檢查的元素越來越少

但是此時(shí)，我們可能會(huì)提出一個(gè)疑問。

隨著排序的進(jìn)行，每次需要檢查的元素?cái)?shù)在逐漸減少，最后一次需要檢查的元素都只有一個(gè)。既然如此，運(yùn)行時(shí)間怎么還是O($n^2$)呢？

你說得沒錯(cuò)，并非每次都需要檢查n個(gè)元素。第一次需要檢查n個(gè)元素，但隨后檢查的元素?cái)?shù)依次為n - 1, n – 2, …, 2和1。平均每次檢查的元素?cái)?shù)為$\frac{1}{2}n$，因此運(yùn)行時(shí)間為O($\frac{1}{2}{n}^2$)。但大O表示法省略諸如1/2這樣的常數(shù)，因此簡(jiǎn)單地寫作O(n × n)或O($n^2$).

python實(shí)現(xiàn)

# -*- coding: utf-8 -*-def findMaximum(arr):maximum = arr[0]maximum_index = 0for item in range(1, len(arr)):if arr[item] > maximum :maximum = arr[item]maximum_index = itemreturn maximum_indexdef selectionSort(arr):newArr = []for item in range(len(arr)):maximum = findMaximum(arr)newArr.append(arr.pop(maximum))return newArrprint(selectionSort([259,199,287,250,266]))

輸出結(jié)果：

[287, 266, 259, 250, 199]

總結(jié)

以上是生活随笔為你收集整理的小白的算法初识课堂(part2)--选择排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。