Go语言 排序与搜索切片

Go语言标准库中提供了sort包对整型，浮点型，字符串型切片进行排序，检查一个切片是否排好序，使用二分法搜索函数在一个有序切片中搜索一个元素等功能。

创新互联公司坚持“要么做到，要么别承诺”的工作理念，服务领域包括：网站设计、成都做网站、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的官渡网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

关于sort包内的函数说明与使用，请查看

在这里简单讲几个sort包中常用的函数

在Go语言中，对字符串的排序都是按照字节排序，也就是说在对字符串排序时是区分大小写的。

二分搜索算法

Go语言中提供了一个使用二分搜索算法的sort.Search(size,fn)方法：每次只需要比较㏒₂n个元素，其中n为切片中元素的总数。

sort.Search(size,fn)函数接受两个参数：所处理的切片的长度和一个将目标元素与有序切片的元素相比较的函数，该函数是一个闭包，如果该有序切片是升序排列，那么在判断时使用 有序切片的元素 = 目标元素。该函数返回一个int值，表示与目标元素相同的切片元素的索引。

在切片中查找出某个与目标字符串相同的元素索引

GoLang中的切片扩容机制

[5]int 是数组，而 []int 是切片。二者看起来相似，实则是根本上不同的数据结构。

切片的数据结构中，包含一个指向数组的指针 array ，当前长度 len ，以及最大容量 cap 。在使用 make([]int, len) 创建切片时，实际上还有第三个可选参数 cap ，也即 make([]int, len, cap) 。在不声明 cap 的情况下，默认 cap=len 。当切片长度没有超过容量时，对切片新增数据，不会改变 array 指针的值。

当对切片进行 append 操作，导致长度超出容量时，就会创建新的数组，这会导致和原有切片的分离。在下例中

由于 a 的长度超出了容量，所以切片 a 指向了一个增长后的新数组，而 b 仍然指向原来的老数组。所以之后对 a 进行的操作，对 b 不会产生影响。

试比较

本例中， a 的容量为6，因此在 append 后并未超出容量，所以 array 指针没有改变。因此，对 a 进行的操作，对 b 同样产生了影响。

下面看看用 a := []int{} 这种方式来创建切片会是什么情况。

可以看到，空切片的容量为0，但后面向切片中添加元素时，并不是每次切片的容量都发生了变化。这是因为，如果增大容量，也即需要创建新数组，这时还需要将原数组中的所有元素复制到新数组中，开销很大，所以GoLang设计了一套扩容机制，以减少需要创建新数组的次数。但这导致无法很直接地判断 append 时是否创建了新数组。

如果一次添加多个元素，容量又会怎样变化呢？试比较下面两个例子：

那么，是不是说，当向一个空切片中插入 2n-1 个元素时，容量就会被设置为 2n 呢？我们来试试其他的数据类型。

可以看到，根据切片对应数据类型的不同，容量增长的方式也有很大的区别。相关的源码包括： src/runtime/msize.go ， src/runtime/mksizeclasses.go 等。

我们再看看切片初始非空的情形。

可以看到，与刚刚向空切片添加5个int的情况一致，向有3个int的切片中添加2个int，容量增长为6。

需要注意的是， append 对切片扩容时，如果容量超过了一定范围，处理策略又会有所不同。可以看看下面这个例子。

具体为什么会是这样的变化过程，还需要从 源码 中寻找答案。下面是 src/runtime/slice.go 中的 growslice 函数中的核心部分。

GoLang中的切片扩容机制，与切片的数据类型、原本切片的容量、所需要的容量都有关系，比较复杂。对于常见数据类型，在元素数量较少时，大致可以认为扩容是按照翻倍进行的。但具体情况需要具体分析。

Go切片数组深度解析

Go 中的分片数组，实际上有点类似于Java中的ArrayList,是一个可以扩展的数组，但是Go中的切片由比较灵活，它和数组很像，也是基于数组，所以在了解Go切片前我们先了解下数组。

数组简单描述就由相同类型元素组成的数据结构, 在创建初期就确定了长度，是不可变的。

但是Go的数组类型又和C与Java的数组类型不一样， NewArray 用于创建一个数组，从源码中可以看出最后返回的是 Array{}的指针，并不是第一个元素的指针，在Go中数组属于值类型，在进行传递时，采取的是值传递，通过拷贝整个数组。Go语言的数组是一种有序的struct。

Go 语言的数组有两种不同的创建方式，一种是显示的初始化，一种是隐式的初始化。

注意一定是使用 [...]T 进行创建，使用三个点的隐式创建，编译器会对数组的大小进行推导，只是Go提供的一种语法糖。

其次，Go中数组的类型，是由数值类型和长度两个一起确定的。[2]int 和 [3]int 不是同一个类型，不能进行传参和比较，把数组理解为类型和长度两个属性的结构体，其实就一目了然了。

Go中的数组属于值类型，通常应该存储于栈中，局部变量依然会根据逃逸分析确定存储栈还是堆中。

编译器对数组函数中做两种不同的优化：

在静态区完成赋值后复制到栈中。

总结起来，在不考虑逃逸分析的情况下，如果数组中元素的个数小于或者等于 4 个，那么所有的变量会直接在栈上初始化，如果数组元素大于 4 个，变量就会在静态存储区初始化然后拷贝到栈上。

由于数组是值类型，那么赋值和函数传参操作都会复制整个数组数据。

不管是赋值或函数传参，地址都不一致，发生了拷贝。如果数组的数据较大，则会消耗掉大量内存。那么为了减少拷贝我们可以主动的传递指针呀。

地址是一样的，不过传指针会有一个弊端，从打印结果可以看到，指针地址都是同一个，万一原数组的指针指向更改了，那么函数里面的指针指向都会跟着更改。

同样的我们将数组转换为切片，通过传递切片，地址是不一样的，数组值相同。

切片是引用传递，所以它们不需要使用额外的内存并且比使用数组更有效率。

所以，切片属于引用类型。

通过这种方式可以将数组转换为切片。

中间不加三个点就是切片,使用这种方式创建切片，实际上是先创建数组，然后再通过第一种方式创建。

使用make创建切片，就不光编译期了，make创建切片会涉及到运行期。1. 切片的大小和容量是否足够小；

切片是否发生了逃逸，最终在堆上初始化。如果切片小的话会先在栈或静态区进行创建。

切片有一个数组的指针，len是指切片的长度, cap指的是切片的容量。

cap是在初始化切片是生成的容量。

发现切片的结构体是数组的地址指针array unsafe.Pointer，而Go中数组的地址代表数组结构体的地址。

slice 中得到一块内存地址，array[0]或者unsafe.Pointer(array[0])。

也可以通过地址构造切片

nil切片：指的unsafe.Pointer 为nil

空切片：

创建的指针不为空，len和cap为空

当一个切片的容量满了，就需要扩容了。怎么扩，策略是什么？

如果原来数组切片的容量已经达到了最大值，再想扩容， Go 默认会先开一片内存区域，把原来的值拷贝过来，然后再执行 append() 操作。这种情况对现数组的地址和原数组地址不相同。

从上面结果我们可以看到，如果用 range 的方式去遍历一个切片，拿到的 Value 其实是切片里面的值拷贝,即浅拷贝。所以每次打印 Value 的地址都不变。

由于 Value 是值拷贝的，并非引用传递，所以直接改 Value 是达不到更改原切片值的目的的，需要通过 slice[index] 获取真实的地址。

Go小知识新解

1、值接收者和指针接收者

所谓指针接收者和值接收者这两个概念，用GO写了一阵子代码的人都了解了，这里只做简要说明一下，也就是对于一个给定结构，咱们对结构进行方法包装的时候，固定必传的参数，用来指向这个对象结构自身的一个参数，在go中也就是形式如下：

我们对结构体testStruct进行了包装，提供了两个方法，sum和modify，其中sum的方法接收者为a testStruct，这个就是值接收者，而modify的接收者为a *testStruct就是指针接收者，也就是说固定对象指针，一个传递的是指针地址，而另外一个直接传递的是结构值拷贝了

对指针有一定了解的，都可以知道，指针传递过去的，可以直接修改结构内部内容，而值传递过去的，无论如何修改这个接收者的数据，不会对原对象结构产生影响。而对于咱们包装结构对象的时候，到底是使用指针还是使用值接收者，这个实际上没有太大的定论，就我个人的观点来说，如果结构体占有的内存空间不大(kb级别)，而又不需要修改内部的，同时结构对象内部没有同步对象比如（sync包中的mutex,rwlock，waitgroup等之类的结构的话，可以直接值传递，实际上值copy也没有咱们想象的那么慢，很多时候，都用指针，最后的gc回收扫描可能都比咱们这个传递copy的消耗大） p="" /kb级别)，而又不需要修改内部的，同时结构对象内部没有同步对象比如（sync包中的mutex,rwlock，waitgroup等之类的结构的话，可以直接值传递，实际上值copy也没有咱们想象的那么慢，很多时候，都用指针，最后的gc回收扫描可能都比咱们这个传递copy的消耗大）

2、实现接口的值接收者和指针接收者有啥区别

也就是比如定义如下

这里面的值接收者和指针接收者有什么区别，这里咱来写一个测试

通过这个测试用例可以发现，指针接收者实现的接口可以同时支持转移到值接收者接口和指针接收者接口，而用值接收者实现的接口，则无法转移到使用指针接收者实现的接口，为啥子呢？目前网上或者各类资料上都是给的一个很官方很官方，而且很书面话难以理解的说明，大致意思如下：

这是目前网络或者各种资料上都是差不多是这样说的，看似讲了，实际上就说了一个结果，根本就没说出来一个为什么。这样的总结出来，一个初学者的角度来看，是很不好理解的，初学者要么就是死记硬背，要么就是生搬硬套，甚至直到写了好多好多代码了，都还没有搞明白一个为啥子，只是会用了而已，从长远来说这是不利于自身提高的。

有这两个本质点，咱们自己来思考一下，如果你来实现这个编译器的时候，用指针接收的时候，指针接收者，默认就能直接获取支持，而值接收者实现接口的咱们可以直接来一个解指针就变成了值，就能匹配上值接收者实现的接口了，反过来说，如果值接收者，此时要匹配指针接收者，如何匹配呢，取一个地址就变成了指针了，此时数据类型确实是匹配了，但是，地址指向的数据区不对了，因为我们刚刚说了值接收者拷贝了一个新值之后是完全的一个新的对象，这个新对象和原始对象一点关系都没有，咱们取地址，取的也是这个新对象地址，对这个地址进行操作，也是这个新对象的内部数据，和原始数据内部没有任何关系，所以由此就能推断出，这个是为啥子值接收者不能匹配上指针接收者，而指针接收者却可以匹配上值接收者了。

1、在某个作用域内部，所有定义的字符串的数据区相同

这个很好验证，代码如下：

2、字符串相加会产生一个新串

这个也很好验证

3、字符串真的是不可变的吗

实际上从字符串的结构

从这个结构，就能大致的推断出来，字符串设计成这样就不具备直接扩容+来增加新数据，而如果咱们直接使用string[index] = 'a'，用这种方式，就不能编译通过，官方也确定说字符串是不可变的。那么真的是不可变的吗？

通过上面的结构，在加上go的slice切片的数据结构

由此可见，咱们可以将字符串通过指针方式强转为一个byte数组指针，然后通过byte切片来修改，试试

编译通过，运行报错

unexpected fault address 0xae2e27

fatal error: fault

这个错误，基本上就是一个内存的保护错误，是写异常，所以说明了，这个肯定做了内存写保护，那么直接修改一下内存区的属性，去掉他的写保护，就能写了

以下代码都是在Win平台，Go1.18，Win上修改内存权限属性，使用VirtualProtect,代码如下

此时运行，就能发现tstr的内容被咱们变了，这种情况实际上在实际开发中不具有实际意义，因为本身在语言层面，已经做了层层限制，咱们这是属于非法强制的操作方式，是流氓行为，那么是否有比较温和一点的操作方式呢？答案是有的，且往下看。

通过上面，我们已经用到了字符串结构，切片结构，要想字符串内容可变，那么咱们自己构造字符串的数据内容区域，且让这个数据区木有内存写保护不就行了，内容区可变，GO原生态的byte数组不就行嘛，所以咱们自己构造一下

此时我们直接修改buffer的内容，就是直接修改了str的数据内容了。而又不会像前面的一样遇到内存写保护

4、字符串转换优化时可能碰到的坑

通过前面讨论的字符串的可变性的方法，咱们可以知道，很多时候，[]byte到字符串的转变，可以直接构造其结构，而共享数据，从而达到减少数据内存copy的方式来进行优化，再使用这些优化的时候，一定需要注意，字符串或者数组的生命周期，是否会存在被改写的情况，从而导致前后不一致的问题。

比如下面这段代码：

大家可以猜想一下，这个最后里面的数据mmp中，"test"的value是多少,"abcd"的value是多少，然后想想为什么，且等端午之后，再来分解

go切片遍历

对于切片的顺序遍历，一般使用 range 就可以了。

这里有一个问题需要注意一下，如果这里的切片nums不是基本数据类型而是结构体。range遍历出来的value值是拷贝值而并非原结构体，修改value中的值不会改变原切片中的值。如果要遍历修改，可以将切片的结构体改为指针，或都索引来取值。

一般情况下逆序遍历思路就是for size-1到0.

二般的也可以使用range来遍历

Go数据结构篇

1、基本数据类型

bool

string

int int8 int16 int32 int64

uint uint8 uint16 uint32 uint64 uintptr

byte // alias for int8

rune // alias for int32,represents a Unicode code point

float32 float64

complex64 complex128

常量定义

2、类型转换

（1）Go语言不允许隐式类型转换（不支持小位数类型向大位数类型转）

（2）别名和原有类型也不能进行隐式类型转换（type MyInt int64 = int64）

3、类型的预定义值

1.math.MaxInt64

2.math.MaxFloat64

3.math.MaxUInt32

4、指针类型

（1）不支持指针运算

（2）string是值类型，其默认的初始化值为空字符串，而不是nil

5、算术运算符

+ - * / % ++ --（不支持前置++ --）

6、比较运算符

#== != = =

（1）比较数组

相同维数且含有形同个数元素的数组才可以比较

每个元素都相同的才相等

7、位运算符

｜ ^

^ (按位置零) a (^b)

1 ^ 0 1

1 ^ 1 0

0 ^ 1 0

0 ^ 0 0

8、条件与循环

（1）循环

Go 语⾔仅⽀持循环关键字 for

（2）条件

9、数组和切片

数组截取，索引下标从0开始计数

a[开始索引(包含), 结束索引(不包含)]

a := [...]int{1, 2, 3, 4, 5}

a[1:2] //2

a[1:3] //2,3

a[1:len(a)] //2,3,4,5

a[1:] //2,3,4,5

a[:3] //1,2,3

切片内部结构

9、Map

9、字符串

Unicode UTF8

常⽤字符串函数

名称栏目：go语言数据结构切片,go 字节切片
当前链接：http://pwwzsj.com/article/heshce.html