資訊專欄INFORMATION COLUMN
摘要：選擇排序是下一章將介紹的快速排序的基石。需要存儲多項數(shù)據(jù)時有兩種基本方式數(shù)組和鏈表。但它們并非都適用于所有的情形因此知道它們的差別很重要。選擇排序是一種靈巧的算法但其速度不是很快。
選擇排序是下一章將介紹的快速排序的基石。
內(nèi)存的工作原理計算機就像是很多抽屜的集合體,每個抽屜都有地址。
fe0ffeeb是一個內(nèi)存單元的地址。
【細(xì)摳起來，這個圖形有問題：實際上，計算機的內(nèi)存是一維的，而圖形是二維的。】
需要將數(shù)據(jù)存儲到內(nèi)存時,你請求計算機提供存儲空間,計算機給你一個存儲地址。需要存儲多項數(shù)據(jù)時,有兩種基本方式——數(shù)組和鏈表。但它們并非都適用于所有的情形,因此知道它們的差別很重要。
數(shù)組和鏈表 數(shù)組數(shù)組中所有元素占用連續(xù)的內(nèi)存，所以通過數(shù)組首元素地址，可以計算每個元素的地址。元素的位置稱為索引，數(shù)組的索引從0開始，幾乎所有的編程語言都從0開始對數(shù)組元素進(jìn)行編號。在同一個數(shù)組中,所有元素的類型都必須相同(都為int、double等)。
數(shù)組具有以下特點：
知道每個元素的地址，支持隨機訪問方式；時間復(fù)雜度O(1)
插入元素時，可能導(dǎo)致元素的移動，最壞情況下，會移動所有元素；由于數(shù)組需要連續(xù)的內(nèi)存，當(dāng)前內(nèi)存可能無法滿足元素的存儲，需要重新分配內(nèi)存空間和進(jìn)行元素的拷貝；插時間復(fù)雜度O(n)
刪除元素后,必須將后面的元素都向前移；時間復(fù)雜度O(n)
鏈表鏈表的每個元素都存儲了下一個元素的地址,從而使一系列隨機的內(nèi)存地址串在一起。鏈表中的元素可存儲在內(nèi)存的任何地方。只要有足夠的內(nèi)存空間,就能為鏈表分配內(nèi)存。
鏈表具有以下特點：
支持順序訪問方式，只能從第一個元素開始逐個地讀取元素；時間復(fù)雜度O(n)
在鏈表中添加元素很容易:只需將其放入內(nèi)存,并將其地址存儲到前一個元素中；時間復(fù)雜度O(1)
刪除元素只需修改前一個元素指向的地址即可；時間復(fù)雜度O(1)
數(shù)組和鏈表還被用來實現(xiàn)其他數(shù)據(jù)結(jié)構(gòu)，比如散列表等。
算法思想：遍歷待排序列表,找出最大或最小的元素，并添加到到新列表的第一個位置；然后找第二大或第二小的元素，依次類推，直到待排序列表里沒有元素為止，此時新列表的元素已按降序或升序排列。
選擇排序是一種靈巧的算法,但其速度不是很快。需要的總時間為 O(n × n),即O(n2)。
Python版本：
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)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
Haskell版本：
import Data.List (delete)
selectionSort :: Ord a => [a] -> [a]
selectionSort [] = []
selectionSort arr =
let smallest = minimum arr
in smallest : selectionSort (delete smallest arr)
請關(guān)注我的公眾號哦
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/43430.html
摘要：在本書中你將學(xué)習(xí)比較不同算法的優(yōu)缺點該使用合并排序算法還是快速排序算法或者該使用數(shù)組還是鏈表。這樣的算法包括快速排序一種速度較快的排序算法。 在讀《算法圖解》這本書，這本書有兩個優(yōu)點： 手繪風(fēng)格的圖，看著很讓人入戲； 算法采用Python語言描述，能更好的表達(dá)算法思想。 關(guān)于算法的學(xué)習(xí)有兩點心得： 算法思想最重要，理解了思想，算法是很容易寫出來的，所以盡量不要把過多精力放在細(xì)節(jié)上...
摘要：再談大表示法快速排序的獨特之處在于其速度取決于選擇的基準(zhǔn)值。在平均情況下快速排序的運行時間為在最糟情況下退化為?？焖倥判蚝秃喜⑴判虻乃惴ㄋ俣确謩e表示為和，是算法所需的固定時間量被稱為常量。 分而治之 分而治之(divide and conquer,D&C)是一種著名的遞歸式問題解決方法。只能解決一種問題的算法畢竟用處有限,而D&C提供了解決問題的思路,是另一個可供你使用的工具。 D&C...
遞歸是個有意思的概念，正如在前面所說，遞歸能讓算法的可讀性大大提高，而且通常要比使用循環(huán)結(jié)構(gòu)更能寫出準(zhǔn)確的算法。這本書形象引入了遞歸，并沒有太深入，所以我進(jìn)行了一點添油加醋。 遞歸 概念 遞歸其實就是自己調(diào)用自己?？梢詮亩喾N維度對遞歸分類，我見過的最常見的分類： 直接遞歸 自己直接調(diào)用自己。如： --haskell length :: [a] -> Int length [] = 0 length...
摘要：將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。 之前介紹的排序算法： 【算法】插入排序——希爾排序+直接插入排序_Rinne’s blog-C...
閱讀 1478·2021-09-02 09:53
閱讀 2729·2021-07-29 13:50
閱讀 1774·2019-08-30 11:07
閱讀 1626·2019-08-30 11:00
閱讀 1510·2019-08-29 14:00
閱讀 1911·2019-08-29 12:52
閱讀 2627·2019-08-29 11:11
閱讀 3483·2019-08-26 12:23
