Go语言の排序和查找
- 本文主要讲Go语言的以下知识点
- 冒牌排序
- 顺序查找
- 二分法查找
- 二维数组
排序的基本介绍
排序是将一组数据，依指定的顺序进行排列的过程。
排序的分类：
内部排序：
指将需要处理的所有数据都加载到内部存储器中进行排序。包括（交换式排序法，选择式排序法和插入式排序法）；
外部排序法：
数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。包括（合并排序法和直接合并排序法）。
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就像水底下的气泡一样逐渐向上冒。
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较（优化）。
冒泡排序的思路分析
冒泡排序实现
func BubbleSort(arr *[5]int) {
fmt.Println("排序前arr=",(*arr))
temp := 0//用于交换的临时变量
//冒泡排序--一步一步推导出来的
for i := 0; i < len(*arr)-1; i++ {
for j := 0; j < len(*arr)-1-i; j++ {
//交换
if(*arr)[j] > (*arr)[j+1] {
temp = (*arr)[j]
(*arr)[j] = (*arr)[j+1]
(*arr)[j+1] = temp
}
}
}
fmt.Println("排序后arr=",(*arr))
}
func main() {
//定义数组
arr := [5]int {23,64,224,76,34}
BubbleSort(&arr)
fmt.Println("main arr=", arr) //有序的哦
}课后练习
需要牢记冒泡排序的代码！能默写出来才行
查找
介绍
在Golang中，我们常用的查找有两种：
- 顺序查找
- 二分查找（数组有序）
案例演示：
- 有一个数列：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王
猜数游戏：从键盘中任意输入一个名称，判断数列中是否包含此名称【使用顺序查找】
代码：
package main
import (
"fmt"
)
func main() {
names := [4]string {"白眉鹰王","金毛狮王","紫衫龙王","青翼蝠王"}
var heroName = ""
fmt.Println("请输入要查找的人名...")
fmt.Scanln(&heroName)
//按顺序查找 第一种方式
for i := 0; i < len(names); i++ {
if heroName == names[i] {
fmt.Printf("找到%v，下标为%v \n", heroName, i)
break
} else if i == (len(names) - 1) {
fmt.Printf("没有找到%v \n", heroName)
}
}
//顺序查找 第二种方式 （推荐）
index := -1
for i := 0; i < len(names); i++ {
if heroName == names[i] {
index = i //赋值
break
}
}
if index != -1 {
fmt.Printf("找到%v, 下标为%v\n", heroName, index)
} else {
fmt.Println("没有找到",heroName)
}
} ~/go/src/go_code/chapter08/demo02/main go run ./main.go
请输入要查找的人名...
金毛狮王
找到金毛狮王，下标为1
找到金毛狮王, 下标为1- 请对一个有序数组进行二分查找 {1,8,10,89,1000,1234},输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示“没有这个数”。【使用到递归】
package main
import (
"fmt"
//"time"
//"math/rand"
)
func BinaryFind(arr *[6]int,leftIndex int,rightIndex int,findVal int) {
if leftIndex > rightIndex {
fmt.Println("找不到哦找不到哦")
return
}
middle := (leftIndex + rightIndex) / 2
if (*arr)[middle] > findVal {
BinaryFind(arr, leftIndex, middle - 1, findVal)
} else if (*arr)[middle] < findVal {
BinaryFind(arr, middle + 1, rightIndex, findVal)
} else {
fmt.Println("这个数字的下标位置在",middle)
}
}
func main(){
var arrs [6]int = [6]int {1,8,10,89,1000,1234}
fmt.Println("请输入一个数：")
var num int = 0
fmt.Scanln(&num)
BinaryFind(&arrs, 0, len(arrs), num)
} ~/go/src/go_code/chapter08/demo03/main go run ./main.go
请输入一个数：
1001
找不到哦找不到哦
~/go/src/go_code/chapter08/demo03/main go run ./main.go
请输入一个数：
1000
这个数字的下标位置在 4二维数组的介绍
如你所见 就是二维数组罢了
二维数组应用场景
比如开发了一个五子棋游戏，棋盘就需要二维数组来表示。如图
二维数组快速入门
快速入门案例：
- 请用二维数组输出如下图形
0 0 0 0 0 0
0 0 1 0 0 0
0 2 0 3 0 0
0 0 0 0 0 0- 代码演示
func main(){
var arr [4][6]int
arr[1][2] = 1
arr[2][1] = 2
arr[2][3] = 3
for i := 0; i < 4; i++ {
for j := 0; j < 6; j++ {
fmt.Printf("%v ",arr[i][j])
}
fmt.Println()
}
}使用方式1:先声明/定义，再赋值
- 语法
var 数组名 [大小][大小]类型 - 比如
var arr [2][3]int,再赋值 - 使用演示
- 二维数组在内存的存在形式（重点）
var arr2 [2][3]int // 以这个为例来分析arr2在内存的布局！！
arr2[1][1] = 10
fmt.Println(arr2)
fmt.Printf("arr2[0]的地址%p\n", &arr2[0])
fmt.Printf("arr2[1]的地址%p\n", &arr2[1])
fmt.Printf("arr2[0][0]的地址%p\n", &arr2[0][0])
fmt.Printf("arr2[1][0]的地址%p\n", &arr2[1][0]) ~/go/src/go_code/chapter08/demo04/main go run ./main.go
[[0 0 0] [0 10 0]]
arr2[0]的地址0xc0000ac030
arr2[1]的地址0xc0000ac048
arr2[0][0]的地址0xc0000ac030
arr2[1][0]的地址0xc0000ac048使用方式2:直接初始化
- 声明：
var 数组名 [大小][大小]类型 = [大小][大小]类型{{初值..},{初值..}} - 赋值（有默认值，比如int类型的就是0）
- 使用演示
var arr3 [2][3]int = [2][3]int{{1,2,3},{4,5,6}}
fmt.Println("arr3=",arr3)arr3= [[1 2 3] [4 5 6]]- 说明：二维数组在声明/定义时也对应有四种写法[和一维数组类似]
var 数组名 [大小][大小]类型 = [大小][大小]类型{{},{}}
var 数组名 [大小][大小]类型 = [...][大小]类型{{初值..},{初值..}}
var 数组名 = [大小][大小]类型{{初值..},{初值..}}
var 数组名 = [...][大小]类型{{初值..},{初值..}}二维数组的遍历
- 双层for循环完成遍历
- for-range方式完成遍历
实例演示：
func main(){
var arr3 = [2][3]int{{1,2,3},{4,5,6}}
//for循环遍历
for i := 0; i < len(arr3); i++ {
for j := 0; j < len(arr3[i]); j++ {
fmt.Printf("arr3[%v][%v] = %v\t", i, j, arr3[i][j])
}
fmt.Println()
}
fmt.Println()
//for-range遍历二维数组
for i, v1 := range arr3 {
for j, v2 := range v1 {
fmt.Printf("arr3[%v][%v] = %v \t", i, j, v2)
}
fmt.Println()
}
} ~/go/src/go_code/chapter08/demo05/main go run ./main.go
arr3[0][0] = 1 arr3[0][1] = 2 arr3[0][2] = 3
arr3[1][0] = 4 arr3[1][1] = 5 arr3[1][2] = 6
arr3[0][0] = 1 arr3[0][1] = 2 arr3[0][2] = 3
arr3[1][0] = 4 arr3[1][1] = 5 arr3[1][2] = 6 二维数组的应用案例
要求如下：
定义二维数组，用于保存三个班，每个班五名同学成绩，并求出每个班级平均分，以及所有班级平均分
代码
func main(){
var scores [3][5]float64
fmt.Println("请按照提示输入成绩：")
for i := 0; i < len(scores); i++ {
for j := 0; j < len(scores[i]); j++ {
fmt.Printf("请输入%v班的第%v个成绩：", i+1, j+1)
fmt.Scanln(&scores[i][j])
}
}
//计算各班平均分
totalSum := 0.0
count := 0
for i := 0; i < len(scores); i++ {
sum := 0.0
for j := 0; j < len(scores[i]); j++ {
sum += scores[i][j]
count++
}
totalSum += sum
fmt.Printf("第%d个班的总分为%v,平均分为%v \n", i+1, sum, sum / float64(len(scores[i])))
}
fmt.Printf("所有人总分为%v,平均分为%v\n",totalSum, totalSum / float64(count))
} ~/go/src/go_code/chapter08/demo06/main go run ./main.go
请按照提示输入成绩：
请输入1班的第1个成绩：70
请输入1班的第2个成绩：80
请输入1班的第3个成绩：60.5
请输入1班的第4个成绩：99
请输入1班的第5个成绩：100
请输入2班的第1个成绩：78
请输入2班的第2个成绩：97
请输入2班的第3个成绩：87
请输入2班的第4个成绩：67
请输入2班的第5个成绩：66
请输入3班的第1个成绩：99
请输入3班的第2个成绩：56
请输入3班的第3个成绩：87
请输入3班的第4个成绩：75
请输入3班的第5个成绩：70.4
第1个班的总分为409.5,平均分为81.9
第2个班的总分为395,平均分为79
第3个班的总分为387.4,平均分为77.47999999999999
所有人总分为1191.9,平均分为79.46000000000001