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

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

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

選擇排序

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

思想：

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

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

遍歷一遍序列，尋找序列中的最小值。在 [i...n−1] 范圍內(nèi)找出最小值 minValue 的位置 minIndex，
用當前位置的值交換最小值。第 i 項的值與交換 minIndex 的值交換，swap(nums[i],nums[minIndex])
對所有元素重復上述過程，直到整個序列排序完成。將下限 iii 增加1，并重復步驟 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)
  }
}

動畫演示

Go 代碼實現(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)的第一個元素為最小值保存
    var minValue = nums[minIdx]
    for j := i; j < length-1; j++ {
      if minValue > nums[j+1] {
        minValue = nums[j+1]
        minIdx = j + 1
      }
    }
    // 如果最小值的位置改變，將當前的最小值位置保存
    if i != minIdx {
      var temp = nums[i]
      nums[i] = nums[minIdx]
      nums[minIdx] = temp
    }
  }
}

運行結(jié)果為：