【算法】算法圖解筆記_選擇排序

mylxsw 發布于2019-07-31 10:12 / 2572人閱讀

摘要：選擇排序是下一章將介紹的快速排序的基石。需要存儲多項數據時有兩種基本方式數組和鏈表。但它們并非都適用于所有的情形因此知道它們的差別很重要。選擇排序是一種靈巧的算法但其速度不是很快。

選擇排序是下一章將介紹的快速排序的基石。

內存的工作原理

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

fe0ffeeb是一個內存單元的地址。

【細摳起來，這個圖形有問題：實際上，計算機的內存是一維的，而圖形是二維的。】

需要將數據存儲到內存時,你請求計算機提供存儲空間,計算機給你一個存儲地址。需要存儲多項數據時,有兩種基本方式——數組和鏈表。但它們并非都適用于所有的情形,因此知道它們的差別很重要。

數組和鏈表 數組

數組中所有元素占用連續的內存，所以通過數組首元素地址，可以計算每個元素的地址。元素的位置稱為索引，數組的索引從0開始，幾乎所有的編程語言都從0開始對數組元素進行編號。在同一個數組中,所有元素的類型都必須相同(都為int、double等)。

數組具有以下特點：

知道每個元素的地址，支持隨機訪問方式；時間復雜度O(1)

插入元素時，可能導致元素的移動，最壞情況下，會移動所有元素；由于數組需要連續的內存，當前內存可能無法滿足元素的存儲，需要重新分配內存空間和進行元素的拷貝；插時間復雜度O(n)

刪除元素后,必須將后面的元素都向前移；時間復雜度O(n)

鏈表

鏈表的每個元素都存儲了下一個元素的地址,從而使一系列隨機的內存地址串在一起。鏈表中的元素可存儲在內存的任何地方。只要有足夠的內存空間,就能為鏈表分配內存。

鏈表具有以下特點：

支持順序訪問方式，只能從第一個元素開始逐個地讀取元素；時間復雜度O(n)

在鏈表中添加元素很容易:只需將其放入內存,并將其地址存儲到前一個元素中；時間復雜度O(1)

刪除元素只需修改前一個元素指向的地址即可；時間復雜度O(1)

數組和鏈表還被用來實現其他數據結構，比如散列表等。

選擇排序

算法思想：遍歷待排序列表,找出最大或最小的元素，并添加到到新列表的第一個位置；然后找第二大或第二小的元素，依次類推，直到待排序列表里沒有元素為止，此時新列表的元素已按降序或升序排列。

選擇排序是一種靈巧的算法,但其速度不是很快。需要的總時間為 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)

請關注我的公眾號哦

云服務器 GPU云服務器排序算法圖解選擇排序的算法過程字符串選擇排序算法排序算法總結

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43430.html

【算法】算法圖解筆記_算法簡介

摘要：在本書中你將學習比較不同算法的優缺點該使用合并排序算法還是快速排序算法或者該使用數組還是鏈表。這樣的算法包括快速排序一種速度較快的排序算法。在讀《算法圖解》這本書，這本書有兩個優點：手繪風格的圖，看著很讓人入戲；算法采用Python語言描述，能更好的表達算法思想。關于算法的學習有兩點心得：算法思想最重要，理解了思想，算法是很容易寫出來的，所以盡量不要把過多精力放在細節上...

tomlingtm 2019-07-31 10:10 評論0 收藏0
【算法】算法圖解筆記_快速排序

摘要：再談大表示法快速排序的獨特之處在于其速度取決于選擇的基準值。在平均情況下快速排序的運行時間為在最糟情況下退化為。快速排序和合并排序的算法速度分別表示為和，是算法所需的固定時間量被稱為常量。分而治之分而治之(divide and conquer,D&C)是一種著名的遞歸式問題解決方法。只能解決一種問題的算法畢竟用處有限,而D&C提供了解決問題的思路,是另一個可供你使用的工具。 D&C...

YanceyOfficial 2019-07-31 10:14 評論0 收藏0
【算法】算法圖解筆記_遞歸

遞歸是個有意思的概念，正如在前面所說，遞歸能讓算法的可讀性大大提高，而且通常要比使用循環結構更能寫出準確的算法。這本書形象引入了遞歸，并沒有太深入，所以我進行了一點添油加醋。遞歸概念遞歸其實就是自己調用自己。可以從多種維度對遞歸分類，我見過的最常見的分類：直接遞歸自己直接調用自己。如： --haskell length :: [a] -> Int length [] = 0 length...

tomlingtm 2019-07-31 10:12 評論0 收藏0
【算法】計數排序 + 各個排序算法的穩定性

摘要：將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。之前介紹的排序算法：【算法】插入排序——希爾排序+直接插入排序_Rinne’s blog-C...

不知名網友 2021-11-29 10:50 評論0 收藏0