20、排序和查找
排序是将一组数据按指定的顺序进行排列的过程，排序分为：内部排序、外部排序，内部排序是将所有数据都加载都内存中，外部排序是借助外部存储进行排序。
- 交换式排序法：
- 冒泡排序法：从前向后，依次比较相邻的2个数字，大/小的数据放到后面；有n个元素，需要进行n-1轮对比，每一轮确定一个数的位置，每一轮的比较次数在逐渐减少 代码： 1）先完成将最大的数字放最后； 2）再将第二大的放到倒数第二；
3）总结规律，合并循环 - 顺序查找：按顺序遍历整个数组查找 二分查找：数组是有序的，先找到中间的下标(start+end)/2，对应的值和X比较，如果大于，则X在左边区间，反之在右边区间，循环直到相等，或没有相等的；查找过程递归执行，递归退出条件是：查找区间<0
package main
import "fmt"
//顺序查找，有一个数列，从控制台接收一个值，依次比较，返回结果
var arr [4]string = [4]string{"king", "kong", "sing", "qing"}
var msg = ""
func find1() {
//第一种方法
for i := 0; i < len(arr); i++ {
if msg == arr[i] {
fmt.Printf("you find %v, index is %v", msg, i)
break
} else if i == (len(arr) - 1) {
fmt.Println("you faile,you out.")
}
}
}
func find2() {
//第二种方法，推荐使用，操作状态，循环中尽量减少内容处理
index := -1 //定义标识状态的变量
for i := 0; i < len(arr); i++ {
if msg == arr[i] {
index = i //找到了改变状态
break
} else if i == (len(arr) - 1) {
fmt.Println("you faile,you out.")
}
}
if index != -1 { //最后对状态进行判断
fmt.Printf("you find %v, index is %v", msg, index)
}
}
func main() {
fmt.Println("please input message:")
fmt.Scanln(&msg)
find2()
}
package main
import "fmt"
//二分查找法示例
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.Printf("找到了，下标为%v", middle)
}
}
func main() {
var arr [6]int = [6]int{1, 20, 45, 66, 245, 1234} //数组必须是已排好序的
BinaryFind(&arr, 0, len(arr)-1, 3)
}
package main
import "fmt"
//冒泡排序法
func BubbleSort(arr *[5]int) {
fmt.Println("排序前的数组:", (*arr))
tmp := 0
//外层循环
for j := 0; j < len(*arr)-1; j++ {
//内层比较大小
for i := 0; i < len(*arr)-1-j; i++ {
if (*arr)[i] > (*arr)[i+1] { //从小到大 > ； 从大到小 <
tmp = (*arr)[i]
(*arr)[i] = (*arr)[i+1]
(*arr)[i+1] = tmp
}
}
fmt.Printf("第%v轮排序的数组 %v: \n", j+1, (*arr))
}
}
func main() {
arr := [5]int{13, 21, 65, 32, 7}
BubbleSort(&arr)
}
21、二维数组的介绍
数组里的元素也是数组。二维数组保存的是一维数组的首地址。 声明：var 数组名 [大小][大小]类型 = [大小][大小]类型{{初值},{初值}} 其他用法和一维数组类似。
package main
import "fmt"
func main() {
//定义一个二维数组
var arr [4][6]int
arr[1][2] = 1
arr[2][1] = 2
arr[2][3] = 3
fmt.Println(arr)
//遍历二维数组方法1
for i := 0; i < 4; i++ {
for j := 0; j < 6; j++ {
fmt.Print(arr[i][j], " ") //逐个元素取出
}
fmt.Println() //换行
}
fmt.Println("===============")
//遍历二维数组方法2
for _, v := range arr {
for _, vv := range v {
fmt.Print(vv, " ")
}
fmt.Println()
}
fmt.Printf("%p %p \n", &arr[0], &arr[1]) //每个元素是个6 int,6*8=48,转为16进制是30
fmt.Printf("%p %p \n", &arr[0][0], &arr[1][0]) //二维数组保存的是一维数组的首地址
}