跟着动画学 Go 数据结构之选择排序

作者：宇宙之一粟

2021 年 12 月 20 日
本文字数：923 字
阅读完需：约 3 分钟

选择排序

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

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

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

遍历一遍序列，寻找序列中的最小值。在 $[i . . . n - 1]$ 范围内找出最小值 minValue 的位置 minIndex，
用当前位置的值交换最小值。第 i 项的值与交换 minIndex 的值交换，swap(nums[i],nums[minIndex])
对所有元素重复上述过程，直到整个序列排序完成。将下限 $i$ 增加 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 mainimport "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 (n^{2})$

稳定性：

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

发布于: 2 小时前阅读数: 5

原文链接:【http://xie.infoq.cn/article/735775c4a511afe0af2235ba7】。文章转载请联系作者。

宇宙之一粟

关注

宇宙古今无有穷期，一生不过须臾，当思奋争 2020.05.07 加入

混迹于江湖，江湖却没有我的影子热爱技术，专注于后端全栈，轻易不换岗拒绝内卷，工作于软件工程师，弹性不加班热衷分享，执着于阅读写作，佛系不水文各大平台同名 CSDN、51CTO、掘金、知乎、公众号、简书。。。

发布

暂无评论

创作场景

跟着动画学 Go 数据结构之选择排序

选择排序

动画演示

Go 代码实现

总结

宇宙之一粟

评论