??深入解析鏈表和數(shù)組的區(qū)別?? 算法圖解：第二章：選擇排序
2022-04-29 14:08:41

Hello，大家好我叫是Dream呀，一個(gè)有趣的Python博主，小白一枚，多多關(guān)照 ?

入門(mén)須知：這片樂(lè)園從不缺乏天才，努力才是你的最終入場(chǎng)券！

最后，愿我們都能在看不到的地方閃閃發(fā)光，一起加油進(jìn)步

“一萬(wàn)次悲傷，依然會(huì)有Dream，我一直在最溫暖的地方等你”，唱的就是我！哈哈哈~

第二章：選擇排序

• ??2.1內(nèi)存的工作原理??
• ??2.2數(shù)組和鏈表??

• ??2.2.1鏈表??
• ??2.2.2數(shù)組??
• ??2.2.3術(shù)語(yǔ)??
• ??2.2.4在中間插入??
• ??2.2.5刪除??

• ??2.3選擇排序??
• ??2.4小結(jié)??
• ??最后的福利??

2.1內(nèi)存的工作原理

計(jì)算機(jī)就像是很多抽屜的集合體，每個(gè)抽屜都有地址。

需要將數(shù)據(jù)存儲(chǔ)到內(nèi)存時(shí)，有兩種基本的存儲(chǔ)方式：數(shù)組和鏈表。但他們之間也各自有缺點(diǎn)和優(yōu)點(diǎn)。

2.2數(shù)組和鏈表

2.2.1鏈表

鏈表的元素可存儲(chǔ)在內(nèi)存的任何地方。

鏈表的每個(gè)元素都存儲(chǔ)了下一個(gè)元素的地址，從而使一系列隨機(jī)的內(nèi)存地址串在一起。

比如你去尋寶時(shí)，你前往地址112，那里有一張紙條，寫(xiě)著：下一個(gè)元素地址是558，以此類推。在鏈表中添加元素也很容易：只需要將其放入內(nèi)存，并將地址存儲(chǔ)到前一個(gè)元素中。

2.2.2數(shù)組

鏈表必須先訪問(wèn)元素#1才可以訪問(wèn)元素#2，以此類推，但如果你需要跳躍，鏈表的效率真的很低。

數(shù)組與此不同：你知道每個(gè)元素的地址。

需要隨機(jī)讀取元素時(shí)，數(shù)組的效率很高，因?yàn)榭梢匝杆僬业綌?shù)組的任何元素。在鏈表中，元素并非靠在一起，你必須依次訪問(wèn)。

2.2.3術(shù)語(yǔ)

數(shù)組元素帶有編號(hào)，編號(hào)不是從1開(kāi)始，而是從0開(kāi)始。

元素的位置稱為索引。因此，不說(shuō)“元素20的位置為1”，而是說(shuō)“元素20位于索引1處”

2.2.4在中間插入

需要中間插入元素時(shí)，使用鏈表會(huì)更簡(jiǎn)單，只需要修改它前面的那個(gè)元素的地址指向。而是用數(shù)組時(shí)，則必須將后面的元素都向后移。

如果沒(méi)有足夠的空間，可能還得將整個(gè)數(shù)組復(fù)制到其他地方！因此，當(dāng)需要在中間插入元素時(shí)，鏈表是最好的選擇。

2.2.5刪除

刪除 鏈表也是最好的選擇，使用數(shù)組時(shí)，刪除元素后，必須將后面的元素都往前移。不同于插入，刪除總能成功。

2.3選擇排序

需要的總時(shí)間：O（n**2）

隨著排序的進(jìn)行，每次需要檢查的元素在逐漸減少，最后一次需要檢查的元素為1個(gè)，運(yùn)行時(shí)間為啥還是O(n**2)呢？其實(shí)用大O表示法省略1/2這樣的常數(shù)，可以簡(jiǎn)單的寫(xiě)作O（n*n）

示例代碼：

#先編寫(xiě)一個(gè)找出數(shù)組中最小元素的函數(shù)
def findSmallest(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
#用這個(gè)函數(shù)來(lái)編寫(xiě)選擇排序算法：
def selectionSort(arr):
    newArr=[]
    for i in range(len(arr)):
        smallest1=findSmallest(arr)
        newArr.append(arr.pop(smallest1))
    return newArr
print(selectionSort([8,9,5,6,4,1,2]))

2.4小結(jié)

1.計(jì)算機(jī)內(nèi)存猶如一大堆抽屜

2.需要存儲(chǔ)多個(gè)元素時(shí)，可以使用數(shù)組或者鏈表

3.數(shù)組的元素都在一起

4.鏈表的元素是分開(kāi)的，其中每個(gè)元素都存儲(chǔ)了下一個(gè)元素的地址

5.數(shù)組的讀取速度很快

6.鏈表的插入和刪除速度很快

7.在同一個(gè)數(shù)組中，所有元素的類型必須相同（都為int或者double等）。

最后的福利

??????最后一點(diǎn)小福利帶給大家：如果想快速上手python的小伙伴們，這個(gè)詳細(xì)整理PPT可以迅速幫助大家打牢python基礎(chǔ)，需要的小伙伴們可以下載一下 Python入門(mén)基礎(chǔ)教程全套+小白速成+學(xué)不會(huì)來(lái)找我！

還有自制表白神器，需要自取：

Python表白神器，源碼+解析+各種完美配置+浪漫新穎?

好啦，這就是今天要給大家分享的全部?jī)?nèi)容了

如果你喜歡的話，就不要吝惜你的一鍵三連了~