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