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

目录
  • 插入排序
  • 动画演示
  • Go 代码实现
  • 总结

插入排序

插入排序，英文名（insertion sort）是一种简单且有效的比较排序算法。

思想： 在每次迭代过程中算法随机地从输入序列中移除一个元素，并将改元素插入待排序序列的正确位置。重复该过程，直到所有输入元素都被选择一次，排序结束。

插入排序有点像小时候我们抓扑克牌的方式，如果抓起一张牌，我们放在手里；抓起第二张的时候，会跟手里的第一张牌进行比较，比手里的第一张牌小放在左边，否则，放在右边。

因此，对所有的牌重复这样的操作，所以每一次都是插入最正确的排序顺序，直到牌抓完为止。

动画演示

假设我们需要从小到大进行排序，动画演示如下：

Go 代码实现

package main
import "fmt"
func main() {
    arrays := []int{6, 2, 5, 8, 9, 3, 1}
    length := len(arrays)
    insertionSort(arrays, length)
    for i := 0; i < length; i++ {
        fmt.Printf("%d ", arrays[i])
    }
}
func insertionSort(unsorted []int, length int) {
    for i := 0; i < length; i++ {
        var insertElement = unsorted[i]
        var insertPosition = i
        for j := insertPosition - 1; j >= 0; j-- {
            if insertElement < unsorted[j] {
                unsorted[j+1] = unsorted[j]
                insertPosition--
            }
        }
        unsorted[insertPosition] = insertElement
    }
}

运行结果：

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\main.go"
1 2 3 5 6 8 9

总结

插入排序实现简单，理解也较容易，数据量较少时效率高，算法的实际运行效率优于选择排序和冒泡排序。

空间复杂度： 空间复杂度为 O(1)，即不输入借助其他的辅助空间。

稳定性： 插入排序是稳定的排序算法，在键值相同时它能够保持输入数据的原有次序。

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

赞 (0)

相关推荐

  • 使用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语言排序算法之插入排序与生成随机数详解

    前言 排序,对于每种编程语言都是要面对的.这里跟大家一起分享golang实现一些排序算法,并且说明如何生成随机数.下面话不多说了,来一起看看详细的介绍吧. 经典排序算法 算法的学习非常重要,是检验一个程序员水平的重要标准.学习算法不能死记硬背,需要理解其中的思想,这样才能灵活应用到实际的开发中. 七大经典排序算法 插入排序 选择排序 冒泡排序 希尔排序 归并排序 堆排序 快速排序 插入排序 先考虑一个问题:对于长度为n的数组,前n-1位都是递增有序的,如何排序? 1.从第1位至第n-1位遍历数组

  • Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

    本文实例讲述了Go语言实现冒泡排序.选择排序.快速排序及插入排序的方法.分享给大家供大家参考.具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法.排序算法有许多种,这里介绍4中排序算法:冒泡排序,选择排序,快速排序和插入排序,以从小到大为例. 一.冒泡排序 冒泡排序的原理是,对给定的数组进行多次遍历,每次均比较相邻的两个数,如果前一个比后一个大,则交换这两个数.经过第一次遍历之后,最大的数就在最右侧了:第二次遍历之后,第二大的数就在右数第二个位置了:以此类推. 复制代码 代码如下:

  • go数据结构和算法BitMap原理及实现示例

    目录 1. BitMap介绍 如何判断数字在bit数组的位置 设置数据到bit数组 从bit数组中清除数据 数字是否在bit数组中 2. Go语言位运算 左移 右移 使用&^和位移运算来给某一位置0 3. BitMap的Go语言实现 定义 创建BitMap结构 将数据添加到BitMap 从BitMap中删除数据 判断BitMap中是否存在指定的数据 1. BitMap介绍 BitMap可以理解为通过一个bit数组来存储特定数据的一种数据结构.BitMap常用于对大量整形数据做去重和查询.在这类查

  • Golang 实现插入排序的方法示例(2种)

    Golang 实现插入排序的方法示例(2种)

    再次研究了插入排序的概念:定义一个有序的数据序列a,将待排序的序列b中的数依次插入到a的合适位置,插入后仍然有序 总结其与冒泡.选择的区别在于,内部迭代的次数是逐渐增大的,二后两者随着排序进行迭代次数逐渐减少 尝试基于Go的实现: 插入排序都采用in-place在数组上实现.具体算法描述如下: 从第一个元素开始,该元素可以认为已经被排序 取出下一个元素 在已经排序的元素序列中从后向前扫描 如果该元素(已排序)大于新元素,将该元素移到下一位置 重复步骤3,直到找到已排序的元素小于或者等于新元素的位

  • Go语言的数据结构转JSON

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

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

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

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

  • C语言进阶栈帧示例详解教程

    C语言进阶栈帧示例详解教程

    目录 正片开始 栈有什么用? 寄存器 main函数创建 局部变量创建 函数部分 形参与实参 正片开始 今天来讲讲我对栈帧创建与销毁的拙见.理解什么是栈帧首先知道什么是栈: 在数据结构中, 栈是限定仅在表尾进行插入或删除操作的线性表.栈是一种数据结构,它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据. 栈有什么用? 在计算机系统中,栈也可以称之为栈内存是一个具有动态内存区域,存储函数内部(包括main函数)的局部变量和方法调用和函数参数值,

  • C语言实现单元测试的示例详解

    目录 前沿 使用前提 测试框架如下 测试方法编写文件 验证 前沿 单元测试(unit testing),是指对软件中的最小可测试单元进行检查和验证.对于单元测试中单元的含义,一般来说,要根据实际情况去判定其具体含义,如C语言中单元指一个函数,Java里单元指一个类,图形化的软件中可以指一个窗口或一个菜单等.总的来说,单元就是人为规定的最小的被测功能模块.单元测试是在软件开发过程中要进行的最低级别的测试活动,软件的独立单元将在与程序的其他部分相隔离的情况下进行测试. 在网上找了找C语言都没有类似j

  • Go语言基础模板设计模式示例详解

    Go语言基础模板设计模式示例详解

    目录 概述 模板模式生活案例 策略模式涉及到两个角色 UML 总结 示例 概述 模板方法模式定义了一个算法的步骤,并允许子类别为一个或多个步骤提供其实践方式.让子类别在不改变算法架构的情况下,重新定义算法中的某些步骤 确定了步骤的执行顺序,单某些步骤因环境或人等因素具体实现是未知的 模板模式生活案例 请客吃饭[点菜->吃东西->结账],每个人点菜不一样,吃东西不一样,结账也不一样从某地到某地[起点->出行方式->终点]起点和终点不一一样,但是每个人出行方式是不一样的 Go没有封装.

  • C语言数据结构之单向链表详解分析

    链表的概念:链表是一种动态存储分布的数据结构,由若干个同一结构类型的结点依次串连而成. 链表分为单向链表和双向链表. 链表变量一般用指针head表示,用来存放链表首结点的地址. 每个结点由数据部分和下一个结点的地址部分组成,即每个结点都指向下一个结点.最后一个结点称为表尾,其下一个结点的地址部分的值为NULL(表示为空地址). 特别注意:链表中的各个结点在内存中是可以不连续存放的,具体存放位置由系统分配. 例如:int *ptr ; 因此不可以用ptr++的方式来寻找下一个结点. 使用链表的优点

  • C语言数据结构之二分法查找详解

    问题:在有序数组中查找给定元素的下标goal. 在查找一个数组元素的下标,可以用循环来解决,但是如果一个数足够大,比如说手机的价格,用循环来查找,就相当于叫一个人猜,从0开始,需要猜很久.这时候就出现了二分查找,也叫对半查找. 对半查找顾名思义就是猜一次,下次猜的内容就减少一半              这时候定义一个变量left表示最左边元素的下标,在定义一个right表示最右边元素的下标,而mid就表示中间元素的下标. 当中间值小于目标值,left重新定义. if (mid < goal)

  • C语言数据结构哈希表详解

    C语言数据结构哈希表详解

    /* * 程序名:hash.c,此程序演示哈希表的实现,数据元素单链表带头结点. * */ #include <stdio.h> #include <stdlib.h> #include <string.h> // 哈希表中数据元素的结构体. typedef struct Element { unsigned int key; // 关键字. int value; // 数据元素其它数据项,可以是任意数据类型. // char value[1001]; // 数据元素其

  • C语言实现队列的示例详解

    C语言实现队列的示例详解

    目录 前言 一. 什么是队列 二. 使用什么来实现栈 三. 队列的实现 3.1头文件 3.2 函数的实现 四.完整代码 前言 前一段时间,我们试着用C语言实现了数据结构中的顺序表,单链表,双向循环链表,栈.今天我们再用C语言来实现另一种特殊的线性结构:队列 一. 什么是队列 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(head)进行删除操作,而在表的后端(tail)进行插入操作,和栈一样,队列是一种操作受限制的线性表.进行插入操作的端称为队尾,进行删除操作的端称为队头. 这个队列就可

  • C语言实现栈的示例详解

    C语言实现栈的示例详解

    目录 前言 一. 什么是栈 二. 使用什么来实现栈 三. 栈的实现 3.1 头文件 3.2 函数实现 3.3 完整代码 四. 栈的用处 前言 前一段时间,我们试着用C语言实现了数据结构中的顺序表,单链表,双向循环链表.今天我们再用C语言来实现另一种特殊的线性结构:栈 一. 什么是栈 栈(stack)又名堆栈,它是一种运算受限的线性表.限定仅在表尾进行插入和删除操作的线性表.这一端被称为栈顶,相对地,把另一端称为栈底.向一个栈插入新元素又称作进栈.入栈或压栈,它是把新元素放到栈顶元素的上面,使之成

  • C语言实现阶乘的示例详解

    C语言实现阶乘的示例详解

    目录 前言 1.阶乘实现 1.1理论步骤 1.2实践结果 2.连续乘层相加实现 2.1理论步骤 2.2实践结果 前言 在现实中,我们做数学题总会遇到阶乘问题,这在计算机中也不例外. 那我们应该怎么实现呢? 我记得很多老师在电脑上书写阶乘都是用!这个符号表示. 比如5的阶乘,写为5!. 这在C语言中是行不通的,下面我讲解C语言中阶乘的实现. 1.阶乘实现 1.1理论步骤 我们可以利用while.do……while.以及for等循环实现,实现功能如下: 我们先设置好3个变量,i.n(想要的阶层数).

随机推荐