Demo

文章头部frot-matter编写参考

所有样式来源于:https://volantis.js.org/v5/tag-plugins/

text

下划线 的文本;带 着重号 的文本;带 波浪线 的文本;带 删除线 的文本

键盘样式的文本: + D

密码样式的文本:这里没有验证码

demo

(LeetCode系列)刷题记

饶大文章汇总

饶大文章汇总

Go语言

深度解密系列

Go语言其他

汇总

彻底解决解决两个链表相交的问题

前言

两个链表相交涉及到关于链表的一系列问题:其中包含了如下子问题,并且涉及到了大量的算法思想,比如快慢指针

  1. 判断链表是否有环
  2. 链表有环的情况下找到环的入口节点
  3. 判断两个链表是否相交
  4. 相交的情况下找到相交时候的第一个节点

对应的7种情况

6aSs8P

解决代码

执行测试命令:go test -v intersection_test.go intersection.go -test.run TestIntersection

解决代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package InterviewCoding

/**
* @Author: yirufeng
* @Date: 2021/11/25 8:21 上午
* @Email: yirufeng@foxmail.com
* @GitHub: https://www.github.com/sivanWu0222
* @Desc:
**/

type LinkedListNode struct {
Val int
Next *LinkedListNode
}

/*
题目:返回两个链表相交的节点
步骤:
1. 明确题目中的意思,两个链表有无环,是否一定相交(如果不一定的话,我们需要判断是否相交,只有在相交的情况下我们才可以返回相交的第一个节点)
2. 分情况进行讨论:
2.1 有环
2.1.1 一定相交:
直接找到相交的节点即可
2.1.2 不一定相交:
首先判断是否相交
相交的时候,找到相交的第一个节点并返回
2.2 无环
2.2.1 一定相交:
2.2.2 不一定相交:
首先判断是否相交
相交的时候,找到相交的第一个节点并返回
2.3 1个有环1个无环,说明一定不会相交,直接返回Nil就可以了
*/

//返回两个链表的相交节点,如果不相交返回Nil,否则返回相交的第一个节点
func Intersection(l1, l2 *LinkedListNode) *LinkedListNode {
//如果有一个为空,直接说明不相交
if l1 == nil || l2 == nil {
return nil
}

//判断两个链表是否有环,如果有环就返回环的起始节点
startOfl1Ring, startOfl2Ring := startNodeOfRing(l1), startNodeOfRing(l2)
//如果1个有1个没有,说明白不相交,直接返回nil
if ((startOfl1Ring == nil) && (startOfl2Ring != nil)) || ((startOfl1Ring != nil) && (startOfl2Ring == nil)) {
return nil
}

var ret *LinkedListNode
if startOfl1Ring != nil { //如果有环
ret = findIntersectionNodeWhenBothHaveCycle(l1, l2, startOfl1Ring, startOfl2Ring)
} else { //如果没有环:此时就转换为我们正常的题解了
ret = findIntersectionNodeWhenBothNoCycle(l1, l2)
}

return ret
}

//当两个链表都没有环的时候,找到两个链表的相交节点(可能相交,可能不相交)
//三种解法去找出第一个相交的节点
func findIntersectionNodeWhenBothNoCycle(l1, l2 *LinkedListNode) *LinkedListNode {
//1. 获得第1个链表第2个链表的长度以及各自链表的最后一个节点
l1Length, l2Length := 1, 1
l1LastNode, l2LastNode := l1, l2
for l1LastNode.Next != nil {
l1Length, l1LastNode = l1Length+1, l1LastNode.Next
}
for l2LastNode.Next != nil {
l2Length, l2LastNode = l2Length+1, l2LastNode.Next
}

//判断各自最后一个节点是否相等,如果不相等,说明不相交,直接返回nil
if l1LastNode != l2LastNode {
return nil
}

//先走长度差
l1LastNode, l2LastNode = l1, l2
if l1Length > l2Length {
for i := 0; i < l1Length-l2Length; i++ {
l1LastNode = l1LastNode.Next
}
} else {
for i := 0; i < l2Length-l1Length; i++ {
l2LastNode = l2LastNode.Next
}
}

//然后一起走,如果中途相等直接返回
for l1LastNode != l2LastNode {
l1LastNode, l2LastNode = l1LastNode.Next, l2LastNode.Next
}

return l1LastNode
}

//当两个链表都有环的时候,找到两个链表的相交节点(可能相交,可能不相交(各自有一个自己的环))
func findIntersectionNodeWhenBothHaveCycle(l1, l2, startOfl1Ring, startOfl2Ring *LinkedListNode) *LinkedListNode {
//判断两个链表是否有环的时候我们可以找到链表有环时候环的第一个节点
//如果两个环的起始节点都相同,此时问题转变为l1的起始节点到自己拥有环的开始节点和l2的起始节点到自己拥有环的开始节点的第一个相交节点
if startOfl1Ring == startOfl2Ring {
l1Temp, l2Temp := l1, l2
//转变为求两个无环单链表的相交节点
var l1TempLength, l2TempLength int

for l1Temp != startOfl1Ring {
l1Temp, l1TempLength = l1Temp.Next, l1TempLength+1
}

for l2Temp != startOfl2Ring {
l2Temp, l2TempLength = l2Temp.Next, l2TempLength+1
}

//长的先走
if l1TempLength > l2TempLength {
for i := 0; i < l1TempLength-l2TempLength; i++ {
l1Temp = l1Temp.Next
}
} else {
for i := 0; i < l2TempLength-l1TempLength; i++ {
l2Temp = l2Temp.Next
}
}

//此时一起走
for l1Temp != l2Temp {
l1Temp, l2Temp = l1Temp.Next, l2Temp.Next
}
return l1Temp

} else { //如果两个环的起始节点不同,让其中一个环开始走,走到起始节点为止,如果中途会出现和另外一个环起始节点相同,说明相交,否则各自成环
l1Temp := startOfl1Ring.Next
for l1Temp != startOfl1Ring {
if l1Temp == startOfl2Ring {
return startOfl2Ring
}
l1Temp = l1Temp.Next
}
}

return nil
}

//返回链表是否有环,如果有的话直接返回true,否则返回false
func startNodeOfRing(head *LinkedListNode) *LinkedListNode {
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast, slow = fast.Next.Next, slow.Next
//说明此时相遇,表明有环
if fast == slow {
break
}
}

//这里是第二个注意点,这里不仅仅要判断fast是否为空,还要判断fast.Next是否为空,
//因为让链表停止上面for循环的有两个条件:1. fast为空 2. fast.Next为空
//判断一下是因为fast为空或者fast.Next为空还是fast==slow退出的
if fast == nil || fast.Next == nil {
return nil
}

//走到这里说明有环,此时让fast指向head,然后fast与slow每次都走一步,一起相遇的时候返回即可
fast = head
for fast != slow {
fast, slow = fast.Next, slow.Next
}
return fast
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package InterviewCoding

import (
"testing"
)

/**
* @Author: yirufeng
* @Date: 2021/11/25 11:05 上午
* @Email: yirufeng@foxmail.com
* @GitHub: https://www.github.com/sivanWu0222
* @Desc:
**/

//测试两个链表
func TestIntersection(t *testing.T) {
//模拟场景
//1.1 两个不带环且不相交的链表
l1, l2 := constructTwoLinkedListWithoutCycleAndNotIntersection()
if Intersection(l1, l2) != nil {
t.Fatalf("expect no intersection node.")
}

//1.2 两个不带环但是相交的链表:LeetCode原题
//已修复,由于&&写成了||
l1, l2 = constructTwoLinkedListWithoutCycleButIntersection()
if Intersection(l1, l2) == nil {
t.Log(Intersection(l1, l2))
t.Fatalf("expect to have intersection node.")
}

//2. 1个链表有环,1个无环
l1, l2 = constructTwoLinkedListButOneHasCycle()
if Intersection(l1, l2) != nil {
t.Fatalf("expect no intersection node.")
}
//3. 两个链表都有环
//3.1 两个链表都有环,但是两个链表的环都是各自的
l1, l2 = constructTwoLinkedBothHasOwnCycle()
if Intersection(l1, l2) != nil {
t.Fatalf("expect no intersection node.")
}

//3.2.1 两个链表都有环,并且两个链表是相交的,且交点在进入环之前
//todo: 有问题
l1, l2 = constructTwoLinkedListBothHasCycleAndIntersection()
if Intersection(l1, l2) == nil {
t.Fatalf("expect to have intersection node.")
}
//3.2.2 两个链表都有环,并且两个链表是相交的,且交点在环上
l1, l2 = constructTwoLinkedListBothHasCycleAndIntersectionII()
if Intersection(l1, l2) == nil {
t.Fatalf("expect to have intersection node.")
}
}

//两个不带环但是相交的链表
func constructTwoLinkedListWithoutCycleButIntersection() (l1, l2 *LinkedListNode) {
node := &LinkedListNode{Val: 5}
l1, l2 = &LinkedListNode{Val: 3}, &LinkedListNode{Val: 4, Next: &LinkedListNode{Val: 6, Next: node}}
l1.Next, l2.Next = node, node
return l1, l2
}

//两个不带环且不相交的链表
func constructTwoLinkedListWithoutCycleAndNotIntersection() (l1, l2 *LinkedListNode) {
l1, l2 = &LinkedListNode{Val: 3, Next: &LinkedListNode{Val: 4}}, &LinkedListNode{Val: 5, Next: &LinkedListNode{Val: 6}}
return l1, l2
}

//构造两个链表1个有环1个无环
func constructTwoLinkedListButOneHasCycle() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 2}, &LinkedListNode{Val: 3}
node.Next, node2.Next = node2, node
l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3}
return l1, l2
}

//构造两个都有环的链表,但是两个链表的环都是各自的
func constructTwoLinkedBothHasOwnCycle() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 2}, &LinkedListNode{Val: 3}
node.Next, node2.Next = node2, node
node3, node4 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
node3.Next, node4.Next = node4, node3
l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3, Next: node3}
return l1, l2
}

//构造两个都有环的链表,但是两个链表都是相交的且相交的起点位于环的入口之前
func constructTwoLinkedListBothHasCycleAndIntersection() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
node.Next, node2.Next = node2, node
node3 := &LinkedListNode{Val: 6, Next: node}
l1, l2 = &LinkedListNode{Val: 1, Next: node3}, &LinkedListNode{Val: 3, Next: node3}
return l1, l2
}

//构造两个都有环的链表,但是两个链表都是相交的且相交的起点位于环上
func constructTwoLinkedListBothHasCycleAndIntersectionII() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
node.Next, node2.Next = node2, node
l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3, Next: &LinkedListNode{Val: 6, Next: node2}}
return l1, l2
}

Go语言中的执行顺序

最近梳理项目结构的时候,对于Go中项目执行流程有点模糊,因此有了本文的诞生方便巩固复习

我们知道整个Go项目只能有一个全局的main()函数,但是Go项目可以有多个不同的package,每一个package下都可以有很多go文件,每一个go文件可以导入其他package,并且每一个go文件可以包含自己的常量定义,全局变量,init()以及其他函数。总结下来,一个Go程序中通常由导入的包,常量,变量,init(),其他函数,main()构成,那么具体的执行流程是怎样的呢?

注意不可以因为导入包造成循环依赖

正常的执行流程:

  1. 首先进入main函数所在的go文件,假设为main.go
    1. 执行 main.go 中的 import 语句,然后进入到其他的pkg中,
      1. 重复我们进入main.go中的类似流程:首先执行import导包,然后定义常量和全局变量并执行init
    2. 执行const定义的常量
    3. 执行var定义的变量
    4. 执行init()对应的初始化函数
    5. 执行main()启动程序

注意点:

  1. 同一个包下面的多个go文件,如果每一个go文件中都有一个init函数,那么执行顺序就是go文件的导入顺序,并且同包下的不同 go 文件,按照文件名“从小到大”排序顺序执行
  2. 其他的包只有被 main 包 import 才会执行,按照 import 的先后顺序执行,也就是按照 main 包中 import 的顺序调用其包中的 init() 函数
  3. 一个包被其它多个包 import,但只能被初始化一次
  4. 对同一个 go 文件的 init( ) 调用顺序是从上到下的
  5. 在同一个 package 中,可以多个文件中定义 init 方法
  6. 在同一个 go 文件中,可以重复定义 init 方法
  7. 在同一个 package 中,不同文件中的 init 方法的执行按照文件名先后执行各个文件中的 init 方法
  8. 所有 init 函数都在同⼀个 goroutine 内执⾏。 所有 init 函数结束后才会执⾏ main.main 函数。

参考文章

  1. Go语言的执行顺序(转)
Golang

实习以及秋招总结

前言

实习结束总结一下实习的所见所闻,顺带分享一下之前实习以及秋招的面经

从3月份找实习到现在找工作以来,一直……

工作

Go语言之go build命令

LVS84L

Golang

gin+docker部署Golang应用

使用gin编写Go的后端程序,然后使用docker打包成镜像并在我们的阿里云ECS上进行部署

编写Go后端程序

项目目录如下:

1
2
3
4
go-web
├── go.mod
├── main.go
├── Dockerfile

main.go文件内容如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package main

import (
"github.com/gin-gonic/gin"
"net/http"
"time"
)

/**
* @Author: yirufeng
* @Date: 2021/7/10 9:04 下午
* @Desc:
**/

type User struct {
Username string `json:"username"`
}

func main() {
engine := gin.Default()

engine.GET("/", func(c *gin.Context) {
startTime := time.Now()

c.JSON(http.StatusOK, gin.H{
"method": http.MethodGet,
"elapsedTime/ms": time.Since(startTime).Milliseconds(),
})
})

engine.POST("/", func(c *gin.Context) {
startTime := time.Now()

var u User
err := c.BindJSON(&u)
if err != nil {
c.JSON(http.StatusOK, gin.H{
"error": err.Error(),
})
return
}

c.JSON(http.StatusOK, gin.H{
"method": http.MethodPost,
"elapsedTime/ms": time.Since(startTime).Milliseconds(),
"username": u.Username,
})
})

engine.Run(":8081")
}
go

docker命令总结

docker

consul集群搭建

consul环境搭建

方法一:docker安装consul集群

自己动手采用docker搭建一个consul集群

1
2
3
4
5
6
7
8
9
10
11
12
# 下载最新的consul镜像
docker pull consul
# 启动我们的第一个consul节点
docker run --name consul1 -d -p 8500:8500 -p 8300:8300 -p 8301:8301 -p 8302:8302 -p 8600:8600 consul agent -server -bootstrap-expect 2 -ui -bind=0.0.0.0 -client=0.0.0.0
# 获取我们第一个启动节点的ip地址:会输出一个ip地址
docker inspect --format '{{ .NetworkSettings.IPAddress }}' consul1
# 启动第二个consul节点
docker run --name consul2 -d -p 8501:8500 consul agent -server -ui -bind=0.0.0.0 -client=0.0.0.0 -join 这里是第一个节点的ip地址
# 启动第三个consul节点
docker run --name consul3 -d -p 8502:8500 consul agent -server -ui -bind=0.0.0.0 -client=0.0.0.0 -join 这里是第一个节点的ip地址
# 查看运行的容器
docker ps

之后访问localhost:8050就可以进入到我们的consul可视化界面

方法二:本机(mac)安装consul:

  1. 直接进入consul官网,下载可执行文件,然后解压到$HOME/Library/consul/
  2. 同时将路径加入到我们的系统环境变量~/.bash_profile
    1
    2
    # add consul
    export PATH=$PATH:$GOPATH/bin:$HOME/Library/consul
  3. 然后刷新我们的配置,此时使用consul执行命令consul members来查看我们docker搭建的consul集群

consul相关命令补充:

  1. vtxNib
  2. zT7xfI

consul参考资料:

  1. 参考1
  2. 参考2
  3. docker安装consul集群

排序算法总结

基础排序算法

点击查看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package basic_sort

/**
* @Author: yirufeng
* @Date: 2021/4/13 8:28 下午
* @Desc: 选择排序

时间复杂度:假设数组中有n个数字
大循环需要遍历n-2趟,然后每一个大循环中,
我们都需要从开始的数字一直到最后选出最小的数字(时间复杂度:O(n)),然后填充到当期那还没有排好序的起始位置

最后总的时间复杂度:O(n^2),
空间复杂度:O(1)。
稳定的排序算法(因为两个相等的数字前面那个一定是排序的时候第一个会被放置到前面的)
**/

func SelectedSort(nums []int) {
selectedSort(nums)
}

func selectedSort(nums []int) {
var min int
for i := 0; i < len(nums)-1; i++ {
//每次从nums[i]开始起
min = i
//依次与后面比对来选择最小的
for j := i + 1; j < len(nums); j++ {
if nums[min] > nums[j] {
min = j
}
}
//交换nums[min]与nums[i]
nums[i], nums[min] = nums[min], nums[i]
}
}

选择排序

选择排序总结:

  1. 时间复杂度:O(n^2)
  2. 空间复杂度:O(1)。
  3. 不稳定的排序算法(比如A 80 B 80 C 70 这三个卷子从小到大排序,最后将会变成CBA,但是稳定的应该是CAB)

三个版本的冒泡排序:

  1. 最基本的
  2. 如果某次冒泡的时候没有交换元素,那么说明这一趟以及后面的元素都是有序的,之后后面我们就不再需要进行冒泡,可以直接退出
  3. 在第二种改进的基础上再使用一个变量,表示我们最后交换的位置,下次遍历到这个位置就可以了

点击查看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package basic_sort

/**
* @Author: yirufeng
* @Date: 2021/4/13 8:28 下午
* @Desc:

有好几个版本:
1. 最基本的
2. 如果某次冒泡的时候没有交换元素,那么说明这一趟以及后面的元素都是有序的,之后后面我们就不再需要进行冒泡,可以直接退出
3. 在第二种改进的基础上再使用一个变量,表示我们最后交换的位置,下次遍历到这个位置就可以了
**/

func BubbleSort(nums []int) {
bubbleSortV2(nums)
}

//最基本的
func bubbleSortV1(nums []int) {
for i := 1; i < len(nums); i++ { //冒泡的次数
for j := 0; j < len(nums)-i; j++ {
//如果前面比后面大就交换
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
}
}
}
}

//如果某次冒泡的时候没有交换元素,那么说明这一趟以及后面的元素都是有序的,之后后面我们就不再需要进行冒泡,可以直接退出
func bubbleSortV2(nums []int) {
//表示某一趟是否有元素交换
flag := true
for i := 1; i < len(nums); i++ { //冒泡的次数
flag = true
for j := 0; j < len(nums)-i; j++ {

//如果前面比后面大就交换
if nums[j] > nums[j+1] {
flag, nums[j], nums[j+1] = false, nums[j+1], nums[j]
}
}
//如果没有元素交换,说明已经有序,直接退出即可
if flag {
break
}
}
}

//在第二种改进的基础上再使用一个变量,表示我们最后交换的位置,下次遍历到这个位置就可以了
//使用一个变量记录最后发生交换的位置,说明该位置之后都是有序的
func bubbleSortV3(nums []int) {
//表示某一趟是否有元素交换
flag := true
//表示最后发生交换的位置
//注意点1:这里必须再额外使用临时变量,因为如果只是用一个变量lastSwapPos的话,
//lastSwapPos的值会一直改变,因此如果一旦变小,我们的for循环就会推出
lastSwapPos := len(nums) - 1 //注意点2:初始值赋值是len(nums) - 1
for i := 1; i < len(nums); i++ { //冒泡的次数
lastSwapPosTemp := len(nums) - i //注意点3:初始值赋值是len(nums) - i
flag = true
//下次遍历的时候遍历到我们上次最后发生交换的位置就可以了
for j := 0; j < lastSwapPos; j++ {
//如果前面比后面大就交换
if nums[j] > nums[j+1] {
flag, nums[j], nums[j+1], lastSwapPosTemp = false, nums[j+1], nums[j], j //注意点4:这里lastSwapPosTemp应该赋值j,因为j与j+1比较过了,所以就认为j之后是已经有序的了
}
}
//如果没有元素交换,说明已经有序,直接退出即可
if flag {
break
}

lastSwapPos = lastSwapPosTemp
}
}

冒泡排序

冒泡排序总结:

  1. 时间复杂度:O(n^2),最好是O(n)
  2. 空间复杂度:O(1)。
  3. 稳定

点击查看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package basic_sort

/**
* @Author: yirufeng
* @Date: 2021/4/13 8:28 下午
* @Desc:

时间复杂度:O(n^2)
空间复杂度:O(1)
稳定的:因为是到前面找到一个小于等于自己的后面那个位置
**/

func InsertSort(nums []int) {
insertSort(nums)
}

func insertSort(nums []int) {
var j int
//第一个元素已经有序,只需要插入后面的元素即可
for i := 1; i < len(nums); i++ {
//当前要插入的元素目前位于i位置
cur := nums[i]
//从后往前找,直到前面元素小于当前元素就停,并且遍历的过程中不断将前面的元素移动到后面
for j = i - 1; j >= 0 && nums[j] > cur; j-- {
nums[j+1] = nums[j]
}
//此时j指向的元素就是前面那个小于或者等于当前元素的位置
//但是我们应该在j+1位置插入
nums[j+1] = cur
}
}

直接插入排序总结

直接插入排序总结:

  1. 时间复杂度:O(n^2),
  2. 空间复杂度:O(1)。
  3. 稳定的:因为是到前面找到一个小于等于自己的后面那个位置

进阶排序算法

点击查看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package advanced_sort

import (
"algos/模板/排序/util"
"fmt"
"sort"
)

/**
* @Author: yirufeng
* @Date: 2021/4/14 3:31 下午
* @Desc: 归并排序
**/

func MergeSort(nums []int) {
mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, l, r int) {
if l == r {
return
}

//找到中间点,一分为二
mid := l + (r-l)>>1
//划分成左右两个有序的空间
mergeSort(nums, l, mid)
mergeSort(nums, mid+1, r)
//将左右两部分以mid为划分轴进行合并
merge(nums, l, mid, r)

}

//合并nums[l:mid+1] 与 nums[mid+1:r+1]两部分内容
func merge(nums []int, l, mid, r int) {
i, j := l, mid+1
cur := 0
//注意点1:这里必须借助一个数组,否则我们前面可能还没有被排序的结果会被我们后半部分的内容覆盖掉,导致前面就没有内容
help := make([]int, r-l+1)
for i <= mid && j <= r {
if nums[i] < nums[j] {
help[cur], cur, i = nums[i], cur+1, i+1
} else {
help[cur], cur, j = nums[j], cur+1, j+1
}
}

for i <= mid {
help[cur], cur, i = nums[i], cur+1, i+1
}
for j <= r {
help[cur], cur, j = nums[j], cur+1, j+1
}

//最后记得我们的help数组中的内容要放回到我们的原来的数组中
for i := 0; i < len(help); i++ {
nums[l+i] = help[i]
}
}

func main() {
nums := util.GenerateRandomNums(0, 100, 30)
fmt.Println(nums)
temp := make([]int, 30)
copy(temp, nums)
sort.Ints(temp)
MergeSort(nums)
fmt.Println(temp)
fmt.Println(nums)
}

归并排序

  1. 时间复杂度:O(nlogN) 最好最坏都是O(NlogN)
  2. 空间复杂度:O(n)。需要一个辅助空间
  3. 是否稳定:稳定的(因为一旦两个数相等我们就不比较,并且每次都是前半部分与后半部分进行比较,所以前面同样的内容与后面同样的内容的相对位置不会改变)

点击查看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package main

import (
"algos/模板/排序/util"
"fmt"
"log"
"sort"
)

/**
* @Author: yirufeng
* @Date: 2021/4/14 3:29 下午
* @Desc: 从小到大的堆排序(需要建立一个大顶堆)

从小到大排序需要建立一个大顶堆,因为我们建立好大顶堆之后,每次从堆头开始排除元素,然后都会将堆头放到目前数组的最后位置,最后位置会不断缩小,
因此我们最后的位置就是一个不断往前移动的过程,从而就是说我们得到的整个数组是从小到大的
**/

func HeapSort(nums []int) {
heapSort(nums)
}

func heapSort(nums []int) {
if nums == nil || len(nums) < 2 {
return
}

for i := 0; i < len(nums); i++ {
heapPush(nums, i)
}

log.Println("建堆完成--------------->", nums)
heapSize := len(nums)

//之后不断吐出元素
for heapSize > 0 {
nums[0], nums[heapSize-1] = nums[heapSize-1], nums[0]
heapSize--
heapify(nums, heapSize)
}
}

//表示当前要加入的是nums中的索引为index的元素
func heapPush(nums []int, index int) {
for (index-1)>>1 >= 0 && nums[index] > nums[(index-1)>>1] {
nums[index], nums[(index-1)>>1], index = nums[(index-1)>>1], nums[index], (index-1)>>1
}
}

//length 表示堆的元素个数
func heapify(nums []int, length int) {
index := 0
// (index << 1 + 1) < length 说明是有左子树的
for (index<<1 + 1) < length { //思路:每次找到左右孩子中更大的与父进行交换
left := index<<1 + 1
//如果有右子树并且右子树比左子树大
if left+1 < length && nums[left+1] > nums[left] {
left++
}
//如果当前节点比左右孩子中大的大,就不交换
if nums[left] <= nums[index] {
break
}
//如果当前节点比左右孩子中大的小,交换当前节点与左右孩子中较大的
//同时让index变为left
nums[left], nums[index], index = nums[index], nums[left], left
}
}

func main() {
nums := util.GenerateRandomNums(0, 100, 50)
temp := make([]int, 50)
copy(temp, nums)
sort.Ints(temp)
fmt.Println(temp)
HeapSort(nums)
fmt.Println(nums)
}

点击查看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package main

import (
"algos/模板/排序/util"
"fmt"
"sort"
)

/**
* @Author: yirufeng
* @Date: 2021/4/15 2:20 下午
* @Desc: 从大到小的排序,需要建立一个小顶堆
**/

func HeapSort(nums []int) {
heapSort(nums)
}

func heapSort(nums []int) {

//如果nums为空或者元素个数小于两个,可以直接退出
if nums == nil || len(nums) < 2 {
return
}

//此时我们需要不断将元素加入我们的堆中
for i := 1; i < len(nums); i++ {
heapInsert(nums, i)
}

//获取堆的大小
heapSize := len(nums)

//此时我们不断将堆里面的元素弹出放到应该放置的位置
for heapSize > 0 {
//将堆的最后一个元素与堆顶交换
nums[0], nums[heapSize-1] = nums[heapSize-1], nums[0]
//堆的元素个数减去1
heapSize--
//开始从堆顶从上往下开始调整堆
heapAdjustFromTopToBottom(nums, heapSize-1) // 从下到上的堆调整
}
}

//第二个参数表示插入的元素位于nums的位置
func heapInsert(nums []int, index int) {
//不断比较当前插入的位置的元素与父节点的大小,如果比父节点小就交换
for (index-1)>>1 >= 0 && nums[(index-1)>>1] > nums[index] {
nums[index], nums[(index-1)>>1], index = nums[(index-1)>>1], nums[index], (index-1)>>1
}
}

//第二个参数表示当前堆的元素个数
func heapAdjustFromTopToBottom(nums []int, length int) {
index := 0
for index<<1+1 < length {
left := index<<1 + 1

//如果有右孩子并且右比左小
if left+1 < length && nums[left+1] < nums[left] {
left++
}

//当前节点小于等于两个孩子较小的
if nums[index] <= nums[left] {
break
}
nums[index], nums[left], index = nums[left], nums[index], left
}
}

func main() {
nums := util.GenerateRandomNums(0, 100, 50)
temp := make([]int, 50)
copy(temp, nums)
sort.Ints(temp)
fmt.Println(temp)
HeapSort(nums)
fmt.Println(nums)
}

点击查看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package main

import (
"algos/模板/排序/util"
"fmt"
"math/rand"
"sort"
)

/**
* @Author: yirufeng
* @Date: 2021/4/14 3:31 下午
* @Desc: 从小到大的快速排序
**/

func QuickSort(nums []int) {
quickSort(nums, 0, len(nums)-1)
}

//表示对[l,r]的元素进行快排
func quickSort(nums []int, l, r int) {
if l < r {
//在[l,r]区间内生成一个随机数作为划分
index := rand.Intn(r-l+1) + l
//每次都把我们随机选择的元素交换到最后
nums[index], nums[r] = nums[r], nums[index]
//进行划分,得到两个相等的区间
less, more := partition(nums, l, r)
//继续对小于和大于的两个区间进行快速排序
quickSort(nums, l, less-1)
quickSort(nums, more+1, r)
}
}

//返回两个结果是等于我们随机数的区间的左端点和右端点
func partition(nums []int, l, r int) (int, int) { //使用nums[r]作为一个划分
less, more := l-1, r
num := nums[r]
cur := l
for cur < more {
if nums[cur] < num {
nums[less+1], nums[cur], less, cur = nums[cur], nums[less+1], less+1, cur+1
} else if nums[cur] > num {
nums[more-1], nums[cur], more = nums[less+1], nums[more-1], more-1
} else if nums[cur] == num {
more++
}
}
nums[more], nums[r] = nums[r], nums[more]
//每次随机择一个划分点
return less + 1, more - 1
}

func main() {
nums := util.GenerateRandomNums(0, 100, 10)
fmt.Println(nums)
temp := make([]int, 10)
copy(temp, nums)
sort.Ints(temp)
fmt.Println(temp)
QuickSort(nums)
fmt.Println(nums)
}

快速排序

思路:采用荷兰国旗的问题进行划分,每次可以划分为3个区间,分别是小于,等于以及大于的区间。

  1. 时间复杂度:O(nlogN) 最好是O(nlogN) 最坏是O(n^2)
  2. 空间复杂度:O(n)。
  3. 是否稳定:不稳定

!!!


1 / 10