华山资源网

Golang 实现插入排序的方法示例(2种)
脚本专栏 2024/11/15 佚名
3 1

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

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

尝试基于Go的实现：

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

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

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

两种实现方式：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]
  }
 }
 }
}

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

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

华山资源网 Design By www.eoogi.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
华山资源网 Design By www.eoogi.com
www.eoogi.com 华山资源网
120,135影音资源
344,641技术资源
22,817软件资源
435,032站长资源

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接
华山资源网 Design By www.eoogi.com