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

目录
  • 选择排序
  • 动画演示
  • 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 代码实现

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 数据结构选择排序的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Go语言数据结构之插入排序示例详解

    Go语言数据结构之插入排序示例详解

    目录 插入排序 动画演示 Go 代码实现 总结 插入排序 插入排序,英文名(insertion sort)是一种简单且有效的比较排序算法. 思想: 在每次迭代过程中算法随机地从输入序列中移除一个元素,并将改元素插入待排序序列的正确位置.重复该过程,直到所有输入元素都被选择一次,排序结束. 插入排序有点像小时候我们抓扑克牌的方式,如果抓起一张牌,我们放在手里:抓起第二张的时候,会跟手里的第一张牌进行比较,比手里的第一张牌小放在左边,否则,放在右边. 因此,对所有的牌重复这样的操作,所以每一次都是插

  • Go语言的数据结构转JSON

    目录 结构体转为 JSON 格式 接口转为 JSON 格式 Marshal() 函数的原型 总结 在日常工作中,除了需要从 JSON 转化为 Go 的数据结构.但往往相反的情况是:我们需要将数据以 JSON 字符串的形式发送到 Web 服务器.今天我们将学会如何从一个结构化数据编码为 JSON . Json(Javascript Object Nanotation)是一种数据交换格式,常用于前后端数据传输.任意一端将数据转换成json 字符串,另一端再将该字符串解析成相应的数据结构,如strin

  • Go 数据结构之堆排序示例详解

    Go 数据结构之堆排序示例详解

    目录 堆排序 堆排序过程 动画显示 开始堆排序 代码实现 总结 堆排序 堆排序是一种树形选择排序算法. 简单选择排序算法每次选择一个关键字最小的记录需要 O(n) 的时间,而堆排序选择一个关键字最小的记录需要 O(nlogn)的时间. 堆可以看作一棵完全二叉树的顺序存储结构. 在这棵完全二叉树中,如果每个节点的值都大于等于左边孩子的值,称为大根堆(最大堆.又叫大顶堆).如果每个节点的值都小于等于左边孩子的值,称为小根堆(最小堆,小顶堆). 可以,用数学符号表示如下: 堆排序过程 构建初始堆 在输

  • Go语言数据结构之希尔排序示例详解

    Go语言数据结构之希尔排序示例详解

    目录 希尔排序 算法思想 图解算法 Go 代码实现: 总结 希尔排序 在插入排序中,在待排序序列的记录个数比较少,而且基本有序,则排序的效率较高. 1959 年,Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进,提出了希尔排序算法. 希尔排序又称为“缩小增量排序”.即将待排序记录按下标的一定增量分组(减少记录个数),对每组记录使用直接插入排序算法排序(达到基本有序): 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1,整个序列基本有序,再对

  • 使用go实现常见的数据结构

    1 golang常见数据结构实现 1.1 链表 举单链表的例子,双向链表同理只是多了pre指针. 定义单链表结构: type LinkNode struct { Data int64 NextNode *LinkNode } 构造链表及打印链表: func main() { node := new(LinkNode) node.Data = 1 node1 := new(LinkNode) node1.Data = 2 node.NextNode = node1 // node1 链接到 nod

  • go语言数据结构之前缀树Trie

    go语言数据结构之前缀树Trie

    目录 介绍 流程 代码 初始化 插入 查找 统计以XXX开头的单词个数 删除数据 介绍 Trie树:又称为单词查找树,是一种树形结构,可以应用于统计字符串,会在搜索引擎系统中用于对文本的词频统计,下图是一个Trie树的结构,同时它也是在插入数时的一个顺序图. 流程 首先应该先创建一个结构体,里面保存的是每一个节点的信息 初始化根节点,根节点应该初始化啥?啥也不用初始化,给个空就好看上图 插入:串转字符数组:遍历数组,如果下一个节点为空,创建,则继续遍历 查找:串转字符数组,遍历如何所有字符都在树

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

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

    目录 选择排序 动画演示 Go 代码实现 总结 选择排序 选择排序(selection sort)是一种原地(in-place)排序算法,适用于数据量较少的情况.由于选择操作是基于键值的且交换操作只在需要时才执行,所以选择排序长用于数值较大和键值较小的文件. 思想: 对一个数组进行排序,从未排序的部分反复找到最小的元素,并将其放在开头. 给定长度为 nnn 的序列和位置索引i=0 的数组,选择排序将: 遍历一遍序列,寻找序列中的最小值.在 [i...n−1] 范围内找出最小值 minValue

  • C语言数据结构线性表教程示例详解

    C语言数据结构线性表教程示例详解

    目录 线性表 顺序表 线性表 数据结构里我们时常看到什么什么表,线性表是最基本.最简单.也是最常用的一种数据结构,其他各种表的万恶之源就是这个线性表,他是个啥其实顾名思义: 一个线性表是n个具有相同特性的数据元素的有限序列.数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部.比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点). 说的这么复杂其实就是

  • C语言直接选择排序算法详解

    C语言直接选择排序算法详解

    目录 1. 直接选择排序介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度 1.4 空间复杂度 1.5 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 直接选择排序介绍 1.1 定义 直接选择排序是指每次都从剩余数据中选出最大或者最小的,将其排在已经排好的有序表后面. 1.2 基本原理 每次从无序表中选择最小(或最大)元素,将其作为首元素,知道所有元素排完为止.将一个有n个元素的数组从小到大排序,第一次从R[0] ~ R[n-1]中选取最小值,与R[0]交换,第二次从R[

  • C语言实现冒泡排序算法的示例详解

    C语言实现冒泡排序算法的示例详解

    目录 1. 问题描述 2. 问题分析 3. 算法设计 动图演示 4. 程序设计 设计一 设计二 结论 5. 流程框架 6. 代码实现 7. 问题拓展 1. 问题描述 对N个整数(数据由键盘输入)进行升序排列. 2. 问题分析 对于N个数因其类型相同,我们可利用 数组 进行存储. 冒泡排序是在 两个相邻元素之间进行比较交换的过程将一个无序表变成有序表. 冒泡排序的思想:首先,从表头开始往后扫描数组,在扫描过程中逐对比较相邻两个元素的大小. 若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

  • R语言时间序列TAR阈值自回归模型示例详解

    R语言时间序列TAR阈值自回归模型示例详解

    为了方便起见,这些模型通常简称为TAR模型.这些模型捕获了线性时间序列模型无法捕获的行为,例如周期,幅度相关的频率和跳跃现象.Tong和Lim(1980)使用阈值模型表明,该模型能够发现黑子数据出现的不对称周期性行为. 一阶TAR模型的示例: σ是噪声标准偏差,Yt-1是阈值变量,r是阈值参数, {et}是具有零均值和单位方差的iid随机变量序列. 每个线性子模型都称为一个机制.上面是两个机制的模型. 考虑以下简单的一阶TAR模型: #低机制参数 i1 = 0.3 p1 = 0.5 s1 = 1

  • R语言编程重读微积分泰勒级数示例详解

    R语言编程重读微积分泰勒级数示例详解

    一 理解极限 二 微分学 泰勒级数 如果我是泰勒,我会把思考的起点建立在这样的一个等式上 那么接下来我们直观地感受一下Taylor级数时如何逐渐逼近某个函数的.简单起见,在此选择  sinx作为被拟合的函数. library(ggplot2) library(gganimate) library(av) library(tibble) x = seq(-pi,pi,0.1) n = length(x) xs = rep(x,11) ys = rep(sin(0),n) ts = rep(0,n)

  • golang编程开发使用sort排序示例详解

    golang sort package: https://studygolang.com/articles/3360 sort 操作的对象通常是一个 slice,需要满足三个基本的接口,并且能够使用整数来索引 // A type, typically a collection, that satisfies sort.Interface can be // sorted by the routines in this package. The methods require that the /

  • go语言题解LeetCode506相对名次示例详解

    目录 一 描述 二 分析 三 答案 一 描述 506. 相对名次 给你一个长度为 n 的整数数组 score ,其中 score[i] 是第 i 位运动员在比赛中的得分.所有得分都 互不相同 . 运动员将根据得分 决定名次 ,其中名次第 1 的运动员得分最高,名次第 2 的运动员得分第 2 高,依此类推.运动员的名次决定了他们的获奖情况: 名次第 1 的运动员获金牌 "Gold Medal" . 名次第 2 的运动员获银牌 "Silver Medal" . 名次第

随机推荐