Go語言數(shù)據(jù)結(jié)構(gòu)之選擇排序示例詳解
選擇排序
選擇排序(selection sort)是一種原地(in-place)排序算法,適用于數(shù)據(jù)量較少的情況。由于選擇操作是基于鍵值的且交換操作只在需要時(shí)才執(zhí)行,所以選擇排序長(zhǎng)用于數(shù)值較大和鍵值較小的文件。
思想:
對(duì)一個(gè)數(shù)組進(jìn)行排序,從未排序的部分反復(fù)找到最小的元素,并將其放在開頭。
給定長(zhǎng)度為 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對(duì)Golang import 導(dǎo)入包語法詳解
今天小編就為大家分享一篇對(duì)Golang import 導(dǎo)入包語法詳解,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-06-06go語言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-07Golang實(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-07Golang?Compare?And?Swap算法詳細(xì)介紹
CAS算法是一種有名的無鎖算法。無鎖編程,即不使用鎖的情況下實(shí)現(xiàn)多線程之間的變量同步,也就是在沒有線程被阻塞的情況下實(shí)現(xiàn)變量的同步,所以也叫非阻塞同步Non-blocking?Synchronization2022-10-10k8s容器互聯(lián)-flannel?host-gw原理篇
這篇文章主要為大家介紹了k8s容器互聯(lián)-flannel?host-gw原理篇,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-04-04