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

Hello，大家好我叫是Dream呀，一個有趣的Python博主，小白一枚，多多關照 ?

入門須知：這片樂園從不缺乏天才，努力才是你的最終入場券！

最后，愿我們都能在看不到的地方閃閃發光，一起加油進步

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

第二章：選擇排序

• ??2.1內存的工作原理??
• ??2.2數組和鏈表??

• ??2.2.1鏈表??
• ??2.2.2數組??
• ??2.2.3術語??
• ??2.2.4在中間插入??
• ??2.2.5刪除??

• ??2.3選擇排序??
• ??2.4小結??
• ??最后的福利??

2.1內存的工作原理

計算機就像是很多抽屜的集合體，每個抽屜都有地址。

需要將數據存儲到內存時，有兩種基本的存儲方式：數組和鏈表。但他們之間也各自有缺點和優點。

2.2數組和鏈表

2.2.1鏈表

鏈表的元素可存儲在內存的任何地方。

鏈表的每個元素都存儲了下一個元素的地址，從而使一系列隨機的內存地址串在一起。

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

2.2.2數組

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

數組與此不同：你知道每個元素的地址。

需要隨機讀取元素時，數組的效率很高，因為可以迅速找到數組的任何元素。在鏈表中，元素并非靠在一起，你必須依次訪問。

2.2.3術語

數組元素帶有編號，編號不是從1開始，而是從0開始。

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

2.2.4在中間插入

需要中間插入元素時，使用鏈表會更簡單，只需要修改它前面的那個元素的地址指向。而是用數組時，則必須將后面的元素都向后移。

如果沒有足夠的空間，可能還得將整個數組復制到其他地方！因此，當需要在中間插入元素時，鏈表是最好的選擇。

2.2.5刪除

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

2.3選擇排序

需要的總時間：O（n**2）

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

示例代碼：

#先編寫一個找出數組中最小元素的函數
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
#用這個函數來編寫選擇排序算法：
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小結

1.計算機內存猶如一大堆抽屜

2.需要存儲多個元素時，可以使用數組或者鏈表

3.數組的元素都在一起

4.鏈表的元素是分開的，其中每個元素都存儲了下一個元素的地址

5.數組的讀取速度很快

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

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

最后的福利

??????最后一點小福利帶給大家：如果想快速上手python的小伙伴們，這個詳細整理PPT可以迅速幫助大家打牢python基礎，需要的小伙伴們可以下載一下 Python入門基礎教程全套+小白速成+學不會來找我！

還有自制表白神器，需要自?。?/p>

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

好啦，這就是今天要給大家分享的全部內容了

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