Go語言數(shù)據(jù)結(jié)構(gòu)之選擇排序示例詳解
選擇排序
選擇排序（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)文章！
- go?sync?Waitgroup數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)基本操作詳解
- Golang迭代如何在Go中循環(huán)數(shù)據(jù)結(jié)構(gòu)使用詳解
- Go 語言數(shù)據(jù)結(jié)構(gòu)之雙鏈表學(xué)習(xí)教程
- Go語言數(shù)據(jù)結(jié)構(gòu)之希爾排序示例詳解
- Go 數(shù)據(jù)結(jié)構(gòu)之堆排序示例詳解
- Go語言數(shù)據(jù)結(jié)構(gòu)之插入排序示例詳解
- go數(shù)據(jù)結(jié)構(gòu)和算法BitMap原理及實(shí)現(xiàn)示例
- Go?語言數(shù)據(jù)結(jié)構(gòu)如何實(shí)現(xiàn)抄一個(gè)list示例詳解
相關(guān)文章
使用systemd部署和守護(hù)golang應(yīng)用程序的操作方法
systemd是一個(gè)流行的守護(hù)進(jìn)程管理器,可以輕松管理服務(wù)的啟動(dòng)、停止、重啟等操作,讓我們的應(yīng)用程序始終保持在線,本文介紹了如何使用systemd部署和守護(hù)golang應(yīng)用程序,感興趣的朋友一起看看吧2023-10-10
這篇文章主要介紹了Golang切片功能操作詳情，切片是一個(gè)擁有相同類型元素的可變長度的序列。它是基于數(shù)組類型做的一層封，切片是一個(gè)引用類型，它的內(nèi)部結(jié)構(gòu)包含地址、長度和容量2022-09-09
對(duì)Golang import 導(dǎo)入包語法詳解
今天小編就為大家分享一篇對(duì)Golang import 導(dǎo)入包語法詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-06-06
go語言VScode?see?'go?help?modules'?(exit?statu
最近上手學(xué)習(xí)go語言,準(zhǔn)備在VSCode上寫程序的時(shí)候卻發(fā)現(xiàn)出了一點(diǎn)問題,下面這篇文章主要給大家介紹了關(guān)于go語言VScode?see?'go?help?modules'(exit?status?1)問題的解決過程,需要的朋友可以參考下2022-07-07
Golang實(shí)現(xiàn)簡(jiǎn)易的命令行功能
這篇文章主要為大家詳細(xì)介紹了如何通過Golang實(shí)現(xiàn)一個(gè)簡(jiǎn)易的命令行功能，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價(jià)值，感興趣的可以了解一下2023-02-02
如何使用Golang創(chuàng)建與讀取Excel文件
我最近工作忙于作圖,圖表,需要自己準(zhǔn)備數(shù)據(jù)源,所以經(jīng)常和Excel打交道,下面這篇文章主要給大家介紹了關(guān)于如何使用Golang創(chuàng)建與讀取Excel文件的相關(guān)資料,需要的朋友可以參考下2022-07-07
這篇文章主要為大家介紹了golang?字符串拼接方法對(duì)比分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-09-09
Golang?Compare?And?Swap算法詳細(xì)介紹
CAS算法是一種有名的無鎖算法。無鎖編程，即不使用鎖的情況下實(shí)現(xiàn)多線程之間的變量同步，也就是在沒有線程被阻塞的情況下實(shí)現(xiàn)變量的同步，所以也叫非阻塞同步Non-blocking?Synchronization2022-10-10
k8s容器互聯(lián)-flannel?host-gw原理篇
這篇文章主要為大家介紹了k8s容器互聯(lián)-flannel?host-gw原理篇，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-04-04
今天我們來聊聊golang是如何進(jìn)行垃圾回收的，我們知道，目前各語言進(jìn)行垃圾回收的方法有很多，如引用計(jì)數(shù)、標(biāo)記清除、分代回收、三色標(biāo)記等，各種方式都有其特點(diǎn)，文中介紹的非常詳細(xì)，感興趣的小伙伴跟著小編一起學(xué)習(xí)吧2023-07-07