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

选择排序

选择排序（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 代码实现

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 } } } 

运行结果为：

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\选择排序\main.go"\
8 10 12 13 20 27 40

总结

选择排序的优点：

• 易于实现，容易理解
• 原地排序（不需要额外的存储空间）,即 空间复杂度为 O(1)O(1)O(1)

缺点：

• 扩展性较差
• 时间复杂度为 O(n2)O(n^2)O(n2)

稳定性：

• 选择排序是不稳定的排序算法。

以上就是Go语言数据结构之选择排序示例详解的详细内容，更多关于Go 数据结构选择排序的资料请关注其它相关文章！

提示： 本文由神整理自网络，如有侵权请联系本站删除！
本站声明：
1、本站所有资源均来源于互联网，不保证100%完整、不提供任何技术支持；
2、本站所发布的文章以及附件仅限用于学习和研究目的;不得将用于商业或者非法用途；否则由此产生的法律后果，本站概不负责！