数据结构

稀疏数组（sparsearray）

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是：

  1. 记录数据一共有几行几列，有多少个不同的值
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模 
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
func main(){
	//1. 先创建一个原始数组
	var chessMap [11][11]int
	chessMap[1][2] = 1 //黑子
	chessMap[10][3] = 2 //白子

	//输出原始数组
	fmt.Println("原始数组")
	for _,v := range chessMap{
		for _ , v2 := range v{
			fmt.Printf("%d\t" , v2)
		}
		fmt.Println()
	}

	//2. 转成稀疏数组
	//思路：
		//1. 遍历chessMap，如果发现有一个元素值不为0，创建一个node结构体
	var sparseArr []ValNode

		//2.一个标准的稀疏数组需要记录二位数组的规模
	valNode := ValNode{
		row: 11,
		col: 11,
		val: 0,
	}
	sparseArr = append(sparseArr , valNode)
	for i,v := range chessMap{
		for j , v2 := range v{
			if v2 != 0{
				//创建一个ValNode 值结点
				valNode = ValNode{
					row: i,
					col: j,
					val: v2,
				}
				sparseArr = append(sparseArr , valNode)
			}
		}
	}

	//输出稀疏数组
	fmt.Println("稀疏数组")
	for i , valNode := range sparseArr{
		fmt.Printf("%d : %d %d %d\n" , i ,valNode.row ,valNode.col ,valNode.val)
	}

	//3. 将稀疏数组存盘
	fileName := "chessMap.data"
	f , err := os.Create(fileName)
	if err!=nil{
		fmt.Println("os.Create err : ", err)
	}
	for _ , valNode := range sparseArr{
		_,err = f.WriteString(strconv.Itoa(valNode.row)+" "+strconv.Itoa(valNode.col)+" "+strconv.Itoa(valNode.val)+"\n")
		if err!=nil {
			fmt.Println("文件写入失败 err : ",err)
			return
		}
	}
	f.Close()

	//4. 将稀疏数组恢复
	//先创建一个原始的数组
	var chessMap2 [11][11]int
	r, _ := os.Open(fileName)
	defer r.Close()
	s := bufio.NewScanner(r)
	rowNum := 0
	for s.Scan() {        // 循环直到文件结束
		line := s.Text()  // 这个 line 就是每一行的文本了，string 类型
		if rowNum == 0{
			rowNum++
			continue
		}

		var row,col,val int
		start := 0
		for i:=0 ;i<len(line) ; i++{
			if line[i] == 32 && start ==0{
				row ,_ = strconv.Atoi(line[start:i])
				//fmt.Println(line[start:i])
				start = i+1
			}else if line[i] == 32 && start !=0{
				col ,_ = strconv.Atoi(line[start:i])
				//fmt.Println(line[start:i])
				val ,_ =strconv.Atoi(line[i+1:])
				//fmt.Println(line[i+1:])
			}
		}
		chessMap2[row][col] = val
	}

	fmt.Println("稀疏数组还原")
	for _,v := range chessMap2{
		for _ , v2 := range v{
			fmt.Printf("%d\t" , v2)
		}
		fmt.Println()
	}
}

队列（queue）

  1. 队列是一个有序列表，可以用数组或者链表实现
  2. 遵循先入先出的原则

数组模拟队列

  1. 创建一个数组array作为队列的一个字段
  2. front初始化为-1
  3. rear表示队列尾部，初始化为-1
  4. 要把数组作为一个环形队列
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
type CircleQueue struct {
	maxSize int
	array [5] int
	head int
	tail int
}

//入列
func (cq *CircleQueue) Push(val int)(err error)  {
	if cq.IsFull(){
		return errors.New("queue full")
	}

	//tail在队列尾部，但不包含最后元素
	cq.array[cq.tail] = val //把值给尾部
	cq.tail  = (cq.tail+1) % cq.maxSize
	return
}

//出列
func (cq *CircleQueue) Pop() (val int ,err error) {
	if cq.IsEmpty(){
		return 0,errors.New("queue empty")
	}

	//取出,head指向队首，并含队首元素
	val = cq.array[cq.head]
	cq.head = (cq.head+1) % cq.maxSize
	return
}

//显示队列
func (cq *CircleQueue) ListQueue()  {
	//取出当前队列有多少个元素
	size := cq.Size()
	if size == 0{
		fmt.Println("队列为空")
	}

	//辅助变量,指向head
	tmpHead := cq.head
	for i := 0 ;i < size ; i++{
		fmt.Printf("add[%d] = %d \t\n" , tmpHead ,cq.array[tmpHead])
		tmpHead = (tmpHead + 1) % cq.maxSize
	}
}

//判断队列是否满了
func (cq *CircleQueue) IsFull() bool {
	return (cq.tail+1) % cq.maxSize == cq.head
}

//判断队列是否为空
func (cq *CircleQueue) IsEmpty() bool {
	return  cq.tail == cq.head
}

//取出环形队列有多少个元素
func (cq *CircleQueue) Size() int {
	return (cq.tail + cq.maxSize - cq.head)% cq.maxSize
}

func main() {
	//初始化环形队列
	circleQueue := CircleQueue{
		maxSize: 5,
		head:    0,
		tail:    0,
	}

	var key string
	var val int
	for{
		fmt.Println("输入add表示添加数据到队列")
		fmt.Println("输入get表示获取队列数据")
		fmt.Println("输入show表示显示队列")
		fmt.Println("输入exit表示退出")
		fmt.Scanln(&key)
		switch key {
		case "add":
			fmt.Println("输入你要入队列的数")
			fmt.Scanln(&val)
			err := circleQueue.Push(val)
			if err==nil{
				fmt.Println("加入队列成功")
			}else{
				fmt.Println(err.Error())
			}
		case "get":
			val , err := circleQueue.Pop()
			if err!=nil{
				fmt.Println(err.Error())
			}else{
				fmt.Println("从队列中取出了 : " ,val)
			}
		case "show":
			circleQueue.ListQueue()
		case "exit":
			os.Exit(0)

		}		
	}
}

链表（link）

单向链表

为了比较好的对单链表进行增删改查的操作，一般都会设置一个头节点，头节点的作用主要是用来标识链表头，本身这个节点不存放数据

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
169
170
171
172
173
174
175
176
177
178
//定义节点
type UserNode struct {
	Id int
	Name string
	Age int
	Next *UserNode //指向下一个节点
}

//给链表插入一个节点
//方法一: 在链表最后加入
func InsertUserNode01(head *UserNode , newUserNode *UserNode)  {
	//先找到该链表最后的节点
	//创建一个辅助节点
	tmp := head
	for  {
		if tmp.Next == nil{
			break
		}
		//让tmp不断指向下一个节点
		tmp = tmp.Next
	}
	//将newUserNode加入链表最后
	tmp.Next = newUserNode
}

//方法二
//根据编号从小到大插入
func InsertUserNode(head *UserNode , newUserNode *UserNode)  {
	//找到适合的节点
	//创建一个辅助节点
	tmp := head
	flag := true
	for  {
		if tmp.Next ==nil{//到最后
			break
		}else if tmp.Next.Id > newUserNode.Id{
			break
		}else if tmp.Next.Id == newUserNode.Id{
			flag = false
			break
		}
		tmp = tmp.Next
	}
	if !flag{
		fmt.Println("已经存在此Id")
		return
	}else{
		newUserNode.Next = tmp.Next
		tmp.Next = newUserNode
	}
}

func DeleteUserNode(head *UserNode , id int)  {
	tmp := head
	flag := false
	for  {
		if tmp.Next ==nil{//到最后
			break
		}else if tmp.Next.Id == id{
			flag = true
			break
		}
		tmp = tmp.Next
	}
	if flag{
		tmp.Next = tmp.Next.Next
		ListUserNode(head)
	}else{
		fmt.Println("要删除的Id不存在")
	}
}

func FindUserNode(head *UserNode , id int)  {
	tmp := head
	flag := false
	for  {
		if tmp.Next ==nil{//到最后
			break
		}else if tmp.Next.Id == id{
			flag = true
			break
		}
		tmp = tmp.Next
	}
	if flag{
		fmt.Printf("[%d , %s , %d ]\n" , tmp.Next.Id , tmp.Next.Name,tmp.Next.Age)
	}else{
		fmt.Println("要查找的Id不存在")
	}
}

func UpdateUserNode(head *UserNode , id int)  {
	tmp := head
	flag := false
	for  {
		if tmp.Next ==nil{//到最后
			break
		}else if tmp.Next.Id == id{
			flag = true
			break
		}
		tmp = tmp.Next
	}
	if flag{
		tmp.Name = "夜行书生改"
		ListUserNode(head)
	}else{
		fmt.Println("要修改的Id不存在")
	}
}

//显示链表所有节点信息
func ListUserNode(head *UserNode){
	//创建一个辅助节点
	tmp := head
	//判断链表是否为空链表
	if tmp.Next ==nil{
		fmt.Println("链表是空的")
		return
	}
	//遍历链表
	for {
		fmt.Printf("[%d , %s , %d ]==>" , tmp.Next.Id , tmp.Next.Name,tmp.Next.Age)
		//判断是否到链表最后
		tmp = tmp.Next
		if tmp.Next ==nil{
			fmt.Println("遍历结束")
			break
		}
	}

}

func main() {
	//创建一个头节点,不需要给值
	head := &UserNode{}

	//创建一个新的节点
	user := &UserNode{
		Id: 2,
		Name: "ck",
		Age:  22,
	}

	user2 := &UserNode{
		Id: 1,
		Name: "夜行书生",
		Age:  23,
	}

	user3 := &UserNode{
		Id: 3,
		Name: "chen",
		Age:  24,
	}


	//添加
	fmt.Println("增")
	InsertUserNode(head,user)
	InsertUserNode(head,user2)
	InsertUserNode(head,user3)

	//显示
	ListUserNode(head)

	//删除
	fmt.Println("删")
	DeleteUserNode(head,2)

	//查找
	fmt.Println("查")
	FindUserNode(head , 3)

	//修改
	fmt.Println("改")
	UpdateUserNode(head , 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
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
//定义节点
type UserNode struct {
	Id int
	Name string
	Age int
	Pre *UserNode//指向前一个节点
	Next *UserNode //指向下一个节点
}

//给链表插入一个节点
//方法一: 在链表最后加入
//func InsertUserNode(head *UserNode , newUserNode *UserNode)  {
//	//先找到该链表最后的节点
//	//创建一个辅助节点
//	tmp := head
//	for  {
//		if tmp.Next == nil{
//			break
//		}
//		//让tmp不断指向下一个节点
//		tmp = tmp.Next
//	}
//	//将newUserNode加入链表最后
//	tmp.Next = newUserNode
//	newUserNode.Pre = tmp
//}

//方法二
//根据编号从小到大插入
func InsertUserNode(head *UserNode , newUserNode *UserNode)  {
	//找到适合的节点
	//创建一个辅助节点
	tmp := head
	flag := true
	for  {
		if tmp.Next ==nil{//到最后
			break
		}else if tmp.Next.Id > newUserNode.Id{
			break
		}else if tmp.Next.Id == newUserNode.Id{
			flag = false
			break
		}
		tmp = tmp.Next
	}
	if !flag{
		fmt.Println("已经存在此Id")
		return
	}else{
		newUserNode.Next = tmp.Next
		newUserNode.Pre = tmp
		if tmp.Next != nil{
			tmp.Next.Pre = newUserNode
		}
		tmp.Next = newUserNode
	}
}

func DeleteUserNode(head *UserNode , id int)  {
	tmp := head
	flag := false
	for  {
		if tmp.Next ==nil{//到最后
			break
		}else if tmp.Next.Id == id{
			flag = true
			break
		}
		tmp = tmp.Next
	}
	if flag{
		tmp.Next = tmp.Next.Next
		if tmp.Next != nil{
			tmp.Next.Pre = tmp
		}
		ListUserNode(head)
	}else{
		fmt.Println("要删除的Id不存在")
	}
}

func FindUserNode(head *UserNode , id int)  {
	tmp := head
	flag := false
	for  {
		if tmp.Next ==nil{//到最后
			break
		}else if tmp.Next.Id == id{
			flag = true
			break
		}
		tmp = tmp.Next
	}
	if flag{
		fmt.Printf("[%d , %s , %d ]\n" , tmp.Next.Id , tmp.Next.Name,tmp.Next.Age)
	}else{
		fmt.Println("要查找的Id不存在")
	}
}

func UpdateUserNode(head *UserNode , id int)  {
	tmp := head
	flag := false
	for  {
		if tmp.Next ==nil{//到最后
			break
		}else if tmp.Next.Id == id{
			flag = true
			break
		}
		tmp = tmp.Next
	}
	if flag{
		tmp.Name = "夜行书生改"
		ListUserNode(head)
	}else{
		fmt.Println("要修改的Id不存在")
	}
}

//显示链表所有节点信息
func ListUserNode(head *UserNode){
	//创建一个辅助节点
	tmp := head
	//判断链表是否为空链表
	if tmp.Next ==nil{
		fmt.Println("链表是空的")
		return
	}
	//遍历链表
	for {
		fmt.Printf("[%d , %s , %d ]==>" , tmp.Next.Id , tmp.Next.Name,tmp.Next.Age)
		//判断是否到链表最后
		tmp = tmp.Next
		if tmp.Next ==nil{
			fmt.Println("遍历结束")
			break
		}
	}

}

func main() {
		//创建一个头节点,不需要给值
		head := &UserNode{}

		//创建一个新的节点
		user := &UserNode{
			Id: 2,
			Name: "ck",
			Age:  22,
		}

		user2 := &UserNode{
			Id: 1,
			Name: "夜行书生",
			Age:  23,
		}

		user3 := &UserNode{
			Id: 3,
			Name: "chen",
			Age:  24,
		}


	//添加
	fmt.Println("增")
	InsertUserNode(head,user)
	InsertUserNode(head,user2)
	InsertUserNode(head,user3)

	//显示
	ListUserNode(head)

	//删除
	fmt.Println("删")
	DeleteUserNode(head,2)

	//查找
	fmt.Println("查")
	FindUserNode(head , 3)

	//修改
	fmt.Println("改")
	UpdateUserNode(head , 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
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
type UserNode struct {
	Id int
	Name string
	Next *UserNode
}

func InsertUserNode (head *UserNode , newUserNode *UserNode)  {
	//判断是否添加第一个用户
	if head.Next == nil{
		head.Id = newUserNode.Id
		head.Name = newUserNode.Name
		head.Next = head //形成环状
		return
	}

	//定义临时变量，帮助找到最后的结点
	tmp := head
	for{
		if tmp.Next == head{
			break
		}
		tmp = tmp.Next
	}
	//加入到链表中
	tmp.Next = newUserNode
	newUserNode.Next = head
}

func ListCircleLink(head *UserNode)  {
	tmp := head
	if tmp.Next == nil{
		fmt.Println("empty link")
		return
	}
	for {
		fmt.Printf("User : [id = %d  name = %s]\n",tmp.Id , tmp.Name)
		if tmp.Next == head{
			break
		}
		tmp = tmp.Next
	}
}

//删除一个节点
func DeleteUser(head *UserNode , id int) *UserNode {
	//先让tmp指向head
	tmp := head
	//让helper指向环形链表最后
	helper := head
	//空链表
	if tmp.Next == nil{
		fmt.Println("empty link")
		return head
	}
	//只有一个节点
	if tmp.Next == head{
		tmp.Next = nil
		return head
	}

	//将helper定位到链表最后
	for{
		if helper.Next == head{
			break
		}
		helper = helper.Next
	}

	//两个及以上的节点
	//让tmp和要删除的id进行比较
	flag := false
	for{
		if tmp.Next == head{
			//除了最后一个节点，没有要删除的节点
			break
		}
		if tmp.Id == id{
			if tmp == head{//如果删除的是头节点
				head = head.Next
			}
			helper.Next = tmp.Next
			flag = true
			break
		}
		tmp = tmp.Next //用来比较
		helper = helper.Next //用来删除
	}
	if !flag{
		if tmp.Id == id{
			helper.Next = tmp.Next
		}else{
			fmt.Println("没有找到这个Id")
		}
	}
	return head
}

func main() {

	//初始化一个头节点
	head := &UserNode{}

	//创建一个用户
	user1 := &UserNode{
		Id:   1,
		Name: "ck1",
	}
	user2 := &UserNode{
		Id:   2,
		Name: "ck2",
	}
	user3 := &UserNode{
		Id:   3,
		Name: "ck3",
	}
	InsertUserNode(head , user1)
	InsertUserNode(head , user2)
	InsertUserNode(head , user3)
	ListCircleLink(head)
	fmt.Println("---------------------------")
	ListCircleLink(DeleteUser(head , 1))
}

约瑟夫问题

N个人围成一圈，从第一个开始报数，第M个将出列，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，出列的顺序是：5，4，6，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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
type Boy struct {
	Id int
	Next *Boy
}

//构成单向环形链表
//num:表示小孩的个数
func AddBoy(num int) *Boy {
	first := &Boy{}
	//构成循环链表需要辅助指针
	curBoy := &Boy{}
	if num < 1{
		fmt.Println("num值错误")
		return first
	}
	for i := 1 ; i <= num ;i++{
		boy := &Boy{
			Id:   i,
		}

		//假设只有一个小孩
		if i == 1{
			first = boy
			curBoy = boy
			curBoy.Next = first
		}else{
			curBoy.Next = boy
			curBoy = boy
			curBoy.Next = first //构成环形链表
		}
	}
	return first
}

//显示单向环形链表
func ListBoy(first *Boy) {
	if first .Next == nil{
		fmt.Println("empty link")
		return
	}

	//创建一个辅助指针
	curBoy := first
	for{
		fmt.Printf("[ id:%d ]-> \n" ,curBoy.Id)
		if curBoy.Next == first{
			break
		}
		curBoy = curBoy.Next
	}
}

//1.编写一个函数，PlayGame(first *Boy , startNum int , countNum int)
//2.按照要求在环形链表中留下最后一人

func PlayGame(first *Boy , startNum int , countNum int){
	if first.Next == nil{
		fmt.Println("空链表")
		return
	}
	//if startNum <= 总数
	//构建辅助节点
	tail := first
	//让tail指向环形链表最后一个人
	for{
		if tail.Next == first{
			break
		}
		tail = tail.Next
	}
	//让first移动到startNum
	for i := 0; i<startNum-1 ;i++{
		first = first.Next
		tail = tail.Next
	}
	//移动countNum次
	for{
		for i:= 0 ;i < countNum-1 ; i++{
			first = first.Next
			tail = tail.Next
		}
		//删除first指向的节点
		fmt.Printf("编号小孩为%d的出列 : \n" , first.Id)
		first = first.Next
		tail.Next = first

		//判断圈中只有一人
		if tail == first{
			break
		}
	}
	//判断如果tail == first ，说明圈中只有一人
	fmt.Printf("编号小孩为%d的出列 : \n" , first.Id)
}

func main() {
	first := AddBoy(5)
	ListBoy(first)

	PlayGame(first , 2 ,3)
}

排序

选择排序

选择排序属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，经过和其他元素重整，再依原则交换位置后达到排序的目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func SelectSort(arr *[10]int)  {
	for i:=0 ; i<len(arr) -1 ;i++{
		maxNum := arr[i]
		maxIndex := i
		for  j:=i ; j <len(arr) ; j++{
			if	maxNum < arr[j]{
				maxNum = arr[j]
				maxIndex = j
			}
		}
		arr[i] , arr[maxIndex]  =  arr[maxIndex], arr[i]
		fmt.Printf("第%d次交换 : %v\n" , i+1 , *arr)
	}
}

func main() {
	arr := [10]int {1,3,2,8,6,10,4,9,5,7}
	fmt.Println(arr)
	SelectSort(&arr)
}

插入排序

插入排序输入内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

把N个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含N-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码一次与有序表元素的排序码进行比较，插入适当的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func InsertSort(arr []int){
   for i := 0 ;i <len(arr)-1 ; i++{
      insertVal := arr [i+1]
      insertIndex := i

      for insertIndex >=0 &&arr[insertIndex] < insertVal{
         arr[insertIndex + 1] = arr[insertIndex]//数据后移
         insertIndex--
      }

      //插入
      if insertIndex != i{
         arr[insertIndex+1] = insertVal
      }
      fmt.Printf("第%d次插入 : %v\n" ,i, arr)
   }
}

func main() {
   arr := []int{1,3,2,8,6,10,4,9,5,7}
   fmt.Println(arr)
   InsertSort(arr)
}

快速排序

快速排序是对冒泡排序的一种改进，基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程都可以递归进行，以此达到整个数据变成有序序列。

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
func QuickSort(left ,right int ,arr []int)  {
	l := left
	r := right
	//pivot是中轴，支点
	pivot := arr[(left+right)/2]

	//把比pivot小的数放在左边。大的放在右边
	for ;l < r ;{
		//先从pivot的左边找到大于等于pivot的值
		for ; arr[l] < pivot;{
			l++
		}
		//从pivot的右边找到小于等于pivot的值
		for ; arr[r] > pivot;{
			r--
		}
		//分割任务完成
		if l >= r{
			break
		}
		//交换
		arr[l],arr[r] = arr[r] , arr[l]
		if arr[l] == pivot{
			r--
		}
		if arr[r] == pivot{
			l++
		}
	}
	if l == r{
		l++
		r--
	}
	//向左递归
	if left < r{
		QuickSort(left ,r ,arr)
	}
	//向右递归
	if right > l{
		QuickSort(l,right,arr)
	}
}

func main() {
	arr := []int{1,3,2,8,6,10,4,9,5,7}
	fmt.Println(arr)
	QuickSort(0,len(arr)-1,arr)
	fmt.Println(arr)
}

排序算法的比对

排序方法 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好 空间复杂度 稳定性
冒泡排序 O(n2) O(n2) O(n) O(1) 稳定
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
插入排序 O(n2) O(n2) O(n) O(1) 稳定
希尔排序 O(n1.3) O(n2) O(n) O(1) 不稳定
快速排序 O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定
基数排序 O(n∗k) O(n∗k) O(n∗k) O(n+k) 稳定

栈

栈是一个先入后出的有序列表（队列是先入先出）

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
type Stack struct {
	MaxTop int //表示栈顶的最大值，也就是栈能存多少数据
	Top int //表示栈顶,-1是为空
	//栈底是固定的，所以不用定义
	arr [5]int //切片模拟
}

//入栈
//栈满返回err
func (s *Stack)Push (val int)  {
	//判断栈是否满了
	if s.Top == s.MaxTop - 1{
		fmt.Println("栈满了")
		return
	}
	s.Top ++
	//放入数据
	s.arr[s.Top] = val
	return
}

//出栈
func (s *Stack) Pop() (val int) {
	if s.Top == -1{
		fmt.Println("栈是空的")
		return
	}
	val = s.arr[s.Top]
	s.Top --
	return val
}

//遍历栈
func  (s *Stack)List()  {
	//判断栈是否为空
	if s.Top == -1{
		fmt.Println("栈是空的")
		return
	}

	for i:=s.Top ; i>=0 ; i--{
		fmt.Printf("arr[%d] = %d \n" , i , s.arr[i])
	}
}
func main() {
	stack := &Stack{
		MaxTop: 5,
		Top:    -1,
	}
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)
	stack.List()
	val := stack.Pop()
	fmt.Printf("%d出栈了\n" , val)
	stack.List()
}

递归

迷宫问题

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
func SetWay(maze *[8][7]int ,i ,j int) bool {
	//令maze[6][5]为出口
	if maze[6][5] == 2{
		fmt.Println("找到了出口")
		return true
	}else{
		//该点为路才能探测
		if maze[i][j] == 0{
			maze[i][j] = 2
			if SetWay(maze , i+1 , j){//下
				return true
			}else if SetWay(maze , i , j+1){//右
				return true
			}else if SetWay(maze , i-1 , j){//上
				return true
			}else if SetWay(maze , i , j-1){//左
				return true
			}else {//死路
				maze[i][j] = 3
				return false
			}
		}else{
			return false
		}
	}
}

func main() {
	//先创建一个二位数组模拟迷宫
	maze := [8][7]int{}
	//如果为1则为墙，为0则为路，为2则为走过的通路，为3则为走过的死路
	//初始化迷宫
	for i:=0 ;i <7 ;i++{
		maze[0][i] = 1
		maze[7][i] = 1
	}
	for i:=0 ;i <8 ;i++{
		maze[i][0] = 1
		maze[i][6] = 1
	}

	//输出地图
	fmt.Println("原地图")
	for i:=0;i<8;i++{
		for j:=0;j<7;j++{
			fmt.Print(maze[i][j] , " ")
		}
		fmt.Println()
	}

	way := SetWay(&maze , 1, 1)
	//探测完毕
	if way{
		for i:=0;i<8;i++{
			for j:=0;j<7;j++{
				fmt.Print(maze[i][j] , " ")
			}
			fmt.Println()
		}
	}else {
		fmt.Println("没路")
	}
}

哈希表（散列）

哈希表是根据关键码值直接进行访问的数据结构，通过把关键码映射到表中的一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数，存放记录的数据叫做哈希表（散列表）

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
//使用链表实现哈希表，该链表不带表头

//定义Emp
type Emp struct {
	Id   int
	Name string
	Next *Emp
}

//定义EmpLink,不带表头，第一个节点就存放信息
type EmpLink struct {
	Head *Emp
}

//添加成员方法,添加Id从小到大
func (e *EmpLink) Insert(emp *Emp) {
	//定义辅助指针
	cur := e.Head
	var pre *Emp = nil //pre始终在cur前面

	if cur == nil {
		e.Head = emp
		return
	}
	//如果不是空链表
	for {
		if cur != nil {
			if cur.Id >= emp.Id {
				break
			}
			pre = cur
			cur = cur.Next
		} else {
			break
		}
	}
	pre.Next = emp
	emp.Next = cur
}

//定义hashtable，含有一个链表数组
type HashTable struct {
	LinkArr [9]EmpLink
}

//添加
func (h *HashTable) InsertUser(emp *Emp) {
	//确定成员添加到哪个链表
	linkNo := h.HashFun(emp.Id)
	h.LinkArr[linkNo].Insert(emp)
}

//显示
func (h *HashTable) ShowAll()  {
	for i:=0 ; i<len(h.LinkArr) ;i++{
		h.LinkArr[i].ShowLink(i)
	}
}
//显示当前链表信息
func (e *EmpLink) ShowLink(i int)  {
	if e.Head == nil{
		fmt.Printf("链表%d为空\n" , i)
		return
	}
	cur := e.Head
	for{
		if cur != nil{
			fmt.Printf("链表%d Id : %d 姓名 : %s ->",i,cur.Id,cur.Name)
			cur = cur.Next
		}else{
			break
		}
	}
	fmt.Println()
}

//做散列函数
func (h *HashTable) HashFun(id int) int {
	return id % 9
}

//查找
func (h *HashTable) FindById(id int) *Emp {
	linkNo := h.HashFun(id)
	emp := h.LinkArr[linkNo].FindById(id)
	return emp
}

func (e *EmpLink) FindById(id int) *Emp {
	cur := e.Head
	for{
		if cur != nil && cur .Id == id{
			return cur
		}else if cur == nil {
			break
		}
		cur = cur.Next
	}
	return nil
}

func main() {
	key := ""
	id := 0
	name := ""
	var hashtable HashTable
	for {
		fmt.Println("input 表示添加成员")
		fmt.Println("show 表示显示成员")
		fmt.Println("find 表示查找成员")
		fmt.Println("exit 表示退出")
		fmt.Scan(&key)
		switch key {
		case "input":
			fmt.Println("请输入成员Id")
			fmt.Scanln(&id)
			fmt.Println("请输入成员姓名")
			fmt.Scanln(&name)
			emp := &Emp{
				Id:   id,
				Name: name,
			}
			hashtable.InsertUser(emp)
		case "show":
			hashtable.ShowAll()
		case "find":
			fmt.Println("请输入要查找的Id")
			fmt.Scanln(&id)
			emp := hashtable.FindById(id)
			if emp == nil{
				fmt.Println("id不存在")
			}else {
				fmt.Printf("id : %d ,name : %s\n",emp.Id,emp.Name)
			}
		case "exit":
			os.Exit(1)
		default:
			fmt.Println("输入有误")
		}
	}
}