Go语言数据结构之选择排序示例详解_Golang

Go语言数据结构之选择排序示例详解

2022-08-26 18:38宇宙之一粟 Golang

这篇文章主要为大家介绍了Go语言数据结构之选择排序示例详解，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪

选择排序

选择排序（selection sort）是一种原地（in-place)排序算法，适用于数据量较少的情况。由于选择操作是基于键值的且交换操作只在需要时才执行，所以选择排序长用于数值较大和键值较小的文件。

思想：

对一个数组进行排序，从未排序的部分反复找到最小的元素，并将其放在开头。

给定长度为 nnn 的序列和位置索引i=0 的数组，选择排序将：

遍历一遍序列，寻找序列中的最小值。在 [i...n−1] 范围内找出最小值 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语言数据结构之选择排序示例详解

Go 代码实现

				?

									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

									    // 每次循环的第一个元素为最小值保存

									    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

									    }

									  }

									}