快捷導(dǎo)航

Go語言數(shù)據(jù)結(jié)構(gòu)之選擇排序示例詳解

更新時(shí)間：2022年08月26日 15:24:54 作者：宇宙之一粟

這篇文章主要為大家介紹了Go語言數(shù)據(jù)結(jié)構(gòu)之選擇排序示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

選擇排序

選擇排序（selection sort）是一種原地（in-place)排序算法，適用于數(shù)據(jù)量較少的情況。由于選擇操作是基于鍵值的且交換操作只在需要時(shí)才執(zhí)行，所以選擇排序長用于數(shù)值較大和鍵值較小的文件。

思想：

對(duì)一個(gè)數(shù)組進(jìn)行排序，從未排序的部分反復(fù)找到最小的元素，并將其放在開頭。

給定長度為 nnn 的序列和位置索引i=0 的數(shù)組，選擇排序?qū)ⅲ?/p>

遍歷一遍序列，尋找序列中的最小值。在 [i...n−1] 范圍內(nèi)找出最小值 minValue 的位置 minIndex，
用當(dāng)前位置的值交換最小值。第 i 項(xiàng)的值與交換 minIndex 的值交換，swap(nums[i],nums[minIndex])
對(duì)所有元素重復(fù)上述過程，直到整個(gè)序列排序完成。將下限 iii 增加1，并重復(fù)步驟 1 直到 i=n−2。

偽代碼：

func selectionSort(nums []int, length int) {
  for i := 0; i < length-1; i++ { // O(N)
    minValue = nums[minIdx] // O(N)
    swap(nums[i], nums[minIndex]); // O(1), X may be equal to L (no actual swap)
  }
}

動(dòng)畫演示

Go 代碼實(shí)現(xiàn)

package main
import "fmt"
func main() {
  unsorted := []int{40, 13, 20, 8, 12, 10, 27}
  length := len(unsorted)
  selectionSort(unsorted, length)
  for i := 0; i < length; i++ {
    fmt.Printf("%d\t", unsorted[i])
  }
}
func selectionSort(nums []int, length int) {
  var minIdx int // 被選擇的最小的值的位置
  for i := 0; i < length-1; i++ {
    minIdx = i
    // 每次循環(huán)的第一個(gè)元素為最小值保存
    var minValue = nums[minIdx]
    for j := i; j < length-1; j++ {
      if minValue > nums[j+1] {
        minValue = nums[j+1]
        minIdx = j + 1
      }
    }
    // 如果最小值的位置改變，將當(dāng)前的最小值位置保存
    if i != minIdx {
      var temp = nums[i]
      nums[i] = nums[minIdx]
      nums[minIdx] = temp
    }
  }
}

運(yùn)行結(jié)果為：

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 數(shù)據(jù)結(jié)構(gòu)\選擇排序\main.go"\
8 10 12 13 20 27 40

總結(jié)

選擇排序的優(yōu)點(diǎn)：

易于實(shí)現(xiàn)，容易理解
原地排序（不需要額外的存儲(chǔ)空間）,即空間復(fù)雜度為 O(1)O(1)O(1)

缺點(diǎn)：

擴(kuò)展性較差
時(shí)間復(fù)雜度為 O(n2)O(n^2)O(n2)

穩(wěn)定性：

選擇排序是不穩(wěn)定的排序算法。

以上就是Go語言數(shù)據(jù)結(jié)構(gòu)之選擇排序示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go 數(shù)據(jù)結(jié)構(gòu)選擇排序的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

相關(guān)文章

GO?集合?map?使用示例小結(jié)
Go語言的集合稱為映射(map)，它是一種無序的鍵值對(duì)(key-value)的集合，集合是通過鍵(key)來快速檢索值(value)的，鍵(key)類似于索引，它指向值(value)的數(shù)據(jù)，這篇文章主要介紹了GO集合map使用總結(jié),本文通過示例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下
2023-06-06
go benchmark 基準(zhǔn)測(cè)試詳解
這篇文章主要介紹了go benchmark 基準(zhǔn)測(cè)試詳解,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2023-03-03
深入了解Golang官方container/heap用法
在?Golang?的標(biāo)準(zhǔn)庫?container?中，包含了幾種常見的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，其實(shí)是非常好的學(xué)習(xí)材料。今天我們就來看看?container/heap?的源碼，了解一下官方的同學(xué)是怎么設(shè)計(jì)，我們作為開發(fā)者又該如何使用
2022-10-10
go語言學(xué)習(xí)之包和變量詳解
這篇文章主要給大家愛介紹了關(guān)于go語言學(xué)習(xí)之包和變量的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用go語言具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2018-06-06
利用Go語言開發(fā)文件操作工具輕松處理所有文件
在后端開發(fā)中,文件操作是一個(gè)非常常見但又容易出錯(cuò)的場(chǎng)景,本文小編要向大家介紹一個(gè)強(qiáng)大的 Go 語言文件操作工具庫,它能幫你輕松處理各種文件操作場(chǎng)景
2025-03-03
Golang中類型轉(zhuǎn)換利器cast庫的用法詳解
cast庫是一個(gè)簡潔而強(qiáng)大的第三方庫,它的主要功能是實(shí)現(xiàn)類型之間的安全轉(zhuǎn)換,而在Golang開發(fā)中,類型轉(zhuǎn)換是一個(gè)常見且不可避免的過程,下面我們就來看看cast庫在Golang中的具體應(yīng)用吧
2024-11-11
golang?http請(qǐng)求未釋放造成的錯(cuò)誤問題
這篇文章主要介紹了golang?http請(qǐng)求未釋放造成的錯(cuò)誤問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2024-01-01
go語言 swagger 查詢 json 字段注釋的示例代碼
在Go語言中,使用Swagger通過swag工具和gin-gonic框架生成API文檔,涉及引入依賴、定義模型、添加注釋等步驟,示例中展示了如何為接受查詢參數(shù)的API端點(diǎn)添加注釋,感興趣的朋友跟隨小編一起看看吧
2024-09-09
golang 生成定單號(hào)的操作
這篇文章主要介紹了golang 生成定單號(hào)的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2020-12-12
Go語言封裝一個(gè)Cron定時(shí)任務(wù)管理器
在現(xiàn)代應(yīng)用中,定時(shí)任務(wù)是非常常見的需求,無論是用于定時(shí)清理數(shù)據(jù),還是定時(shí)執(zhí)行系統(tǒng)維護(hù)任務(wù),下面我們就來使用Go語言封裝一個(gè)Cron定時(shí)任務(wù)管理器吧
2024-12-12