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

再次研究了插入排序的概念：定义一个有序的数据序列a，将待排序的序列b中的数依次插入到a的合适位置，插入后仍然有序

总结其与冒泡、选择的区别在于，内部迭代的次数是逐渐增大的，二后两者随着排序进行迭代次数逐渐减少

尝试基于Go的实现：

插入排序都采用in-place在数组上实现。具体算法描述如下：

  • 从第一个元素开始，该元素可以认为已经被排序 取出下一个元素
  • 在已经排序的元素序列中从后向前扫描
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置
  • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后
  • 将新元素插入到该位置后
  • 重复步骤2~5

两种实现方式：1，新建切片； 2，在原切片中进行元素交换

方式一：新建切片

package main

import "fmt"

func main() {
 arr := []int{1, 0, 5, 7, 8, 5, 3, 6, 9, 2, 54, 33, 66}
 newArr := []int{}
 insertionSort(arr, &newArr)
 fmt.Println(newArr)
}

/**
插入排序法：取原数组old中第一个值作为新数组中的第一个值，然后遍历old，将每个元素按照条件插入到新数组中
时间复杂度：O（n^2）
*/
func insertionSort(old []int, new *[]int) {
 if len(*new) == len(old) {
 return
 }
 current := len(*new)
 *new = append(*new, old[current])
 sort(*new)
 insertionSort(old, new)
}

func sort(arr []int) {
 for i := len(arr) - 1; i > 0; i-- {
 if arr[i] < arr[i-1] {
  arr[i], arr[i-1] = arr[i-1], arr[i]
 }
 }
}

注意：insertionSort()函数中的第二个参数为切片的指针，不然打印出来的的新数组为空

原因：虽然切片是指针传递，这是指切片内的各个元素是指针传递，对于切片本身仍是值传递

证明：

package test

import (
 "fmt"
 "testing"
)

func TestSlice(t *testing.T) {
 slice1 := []string{"zhang", "san"}
 fmt.Printf("%p\n", &slice1)
 fmt.Printf("%p\n", &slice1[1])
 modify(slice1)
 fmt.Println(slice1)
}
func modify(data []string) {
 fmt.Printf("%p\n", &data)
 fmt.Printf("%p\n", &data[1])
 data[1] = "si"
}

打印结果：

0xc0420e4680
0xc0420e46b0
0xc0420e46c0
0xc0420e46b0
[zhang si]

引申：Go 语言里的引用类型有如下几个：切片、映射、通道、接口和函数类型。当声明上述类型的变量时，创建的变量被称作标头（header）值。从技术细节上说，字符串也是一种引用类型。每个引用类型创建的标头值是包含一个指向底层数据结构的指针。因为标头值是为复制而设计的，所以永远不需要共享一个引用类型的值。标头值里包含一个指针，因此通过复制来传递一个引用类型的值的副本，本质上就是在共享底层数据结构

结论：不会对切片进行增加或删除操作时（也就是长度不会改变），切片作为参数在函数间的传递不需使用指针。但是如果切片需要进行增加或删除元素的操作，并且原函数需要调用更新后的切片，那么在原函数调用其它函数时，就需要用切片的指针作为参数。

方式二：在原切片中进行元素交换

func method2(arr []int) {
 if len(arr) < 2 {
 return
 }
 for i := 1; i < len(arr); i++ {
 for j := i; j > 0; j-- {
  if arr[j] < arr[j-1] {
  arr[j], arr[j-1] = arr[j-1], arr[j]
  }
 }
 }
}

由于不用创建新的切片，不用进行插入操作，只需要交换操作，所以要较方法一速度快些

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

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

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

  • Go语言排序算法之插入排序与生成随机数详解

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

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

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

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

  • golang 连接mongoDB的方法示例

    Mogondb 不支持事务.所有有事务要求的需求慎用,比如银行的转账操作慎用,转1个亿美金,因为网络,电力的故障导致交易没有完成,不能回滚,交易无法撤回.所有慎用!! Mogondb 的应用场景: 比如一篇CSDN博客,博客内容,博客作者,发布时间,评论,阅读量等信息可以将这些信息存储到一个类似JSON数据中.如果用mysql需要将不同的信息分别存储于不同的表中,使用的时候,查询多表或者使用JOIN查询数据,导致查询过慢.而使用MongoDB,将数据存储在一起,需要数据时,一次就能查询到数据.更

  • 利用Golang生成整数随机数方法示例

    php随机数 生成一个给定范围的随机数,用 PHP 就太简单不过了,而且可以指定从负数到正整数的范围,如: <?php echo mt_rand(-988, 888); 这样就随机生成 -988 到 888 的随机数. 使用 Go 就要稍微麻烦一点.以下两个函数分别是生成一个最大范围内随机整数,和生成一个区间范围的随机整数: 生成一个最大范围内随机数 一定要给一个时间戳的种子,否则每次生成都是一样的值.这里就是生成 [0,100) 的随机数. func GenerateRandnum() int

  • 汇编实现直接插入排序的方法示例

    汇编实现直接插入排序的方法示例

    上一篇实现了简单插入排序的算法,这一篇主要实现直接插入排序算法: S0 SEGMENT STACK DW 20 DUP(?) TOP LABEL WORD S0 ENDS S1 SEGMENT TIP DB "Input ten number and separate the numbers with space:", 0DH, 0AH, 24H ARY DW 20 DUP(0) CRLF DB 0DH, 0AH, 24H N DW 0 E DW 0 S1 ENDS S2 SEGMEN

  • GoLang 中的随机数的示例代码

    随机数我们都知道,就是计算机通过某种算法,"随机"的生成一个数字.很多编程语言都有内置的方法来生成随机数,那么 GoLang 中是怎样一种情况呢? 伪随机数 我们都知道"随机数"在现实生活中的概念,可能你随手抛一个硬币,就可以说其结果是随机的,但是在计算机中要确定一个"随机数"真的是"随机数",那可是有标准的,不是你随随便便说是就是. 根据密码学原理,要想对一个"随机数"进行随机性检验有以下几个标准: 统计

  • Oracle查看表结构的几种方法示例代码

    1,DESCRIBE 命令 使用方法如下: SQL> describe nchar_tst(nchar_tst为表名) 显示的结果如下: 名称 是否为空? 类型 ----------------------------------------- -------- ---------------------------- NAME NCHAR(6) ADDR NVARCHAR2(16) SAL NUMBER(9,2) 2,DBMS_METADATA.GET_DDL包 使用方法如下: SQL> S

  • Android 在子线程中更新UI的几种方法示例

    本文介绍了Android 在子线程中更新UI的几种方法示例,分享给大家,具体如下: 方式一:Handler和Message ① 实例化一个Handler并重写handlerMessage()方法 private Handler handler = newHandler() { public void handleMessage(Message msg) { // 处理消息 super.handleMessage(msg); switch (msg.what) { case 1: button1.

  • Golang实现对map的并发读写的方法示例

    在Golang多协程的情况下使用全局map时,如果不做线程同步,会出现panic的情况. 为了解决这个问题,通常有两种方式: 第一种是最常见的使用互斥锁或者读写锁的方法: 第二种是比较符合Golang特色的方法,启动单个协程对map进行读写,当其他协程需要读写map时,通过channel向这个协程发送信号即可. 写了一个模拟程序对map中的一项进行读或者写,后台一直运行的协程阻塞的接受读写信号,并对map进行操作,但是读操作的时候没想好怎么返回这个值. 后来想到用传引用的方式,定义结构体,第一个

  • Java 添加Word目录的2种方法示例代码详解

    目录是一种能够快速.有效地帮助读者了解文档或书籍主要内容的方式.在Word中,插入目录首先需要设置相应段落的大纲级别,根据大纲级别来生成目录表.本文中生成目录分2种情况来进行: 1.文档没有设置大纲级别,生成目录前需要手动设置 2.文档已设置大纲级别,通过域代码生成目录 使用工具: •Free Spire.Doc for Java 2.0.0 (免费版) •IntelliJ IDEA 工具获取途径1:通过官网下载jar文件包,解压并导入jar文件到IDEA程序. 工具获取途径2:通过Maven仓

  • Golang通过小程序获取微信openid的方法示例

    为什么要获取小程序的 openid 在开发微信小程序的过程中,小程序可以通过微信官方提供的登录能力方便地获取微信提供的用户身份标识,快速建立小程序内的用户体系.那么这个用户身份标识就是 openid. 小程序获取 openid 的流程 那么小程序获取 openid 的流程具体如下,这里我简化了一下,因为我们只需要获取到 openid 即可,具体可以参考 这里 我们需要在小程序中调用 wx.login() 获取 code 码,然后将这个 code 码发送给后端,后端带着这个 code 码和 app

随机推荐