【Go笔记】第 8 章 排序和查找

• 【尚硅谷】Golang入门到实战教程丨一套精通GO语言 (opens new window)笔记，可在Bilibili同步观看
• 尚硅谷-视频观看地址 (opens new window)

8.1 排序的基本介绍

排序是将一组数据，依指定的顺序进行排列的过程。 排序的分类：

1. 内部排序： 指将需要处理的所有数据都加载到内部存储器中进行排序。 包括（交换式排序法、选择式排序法和插入式排序法）；
2. 外部排序法： 数据量过大，无法全部加载到内存中，需要借助外部存储进行 排序。包括（合并排序法和直接合并排序法）

冒泡排序(Bubble Sorting.)的基本思想是： 通过对待排序序列从后向前（从下标较大的元素开始），依次比较相 邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元)，就象水底下的气泡一样逐渐向上冒。因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较（优化）。

8.2 冒泡排序的思路分析

8.3 冒泡排序实现

package main
import (
"fmt”
)
//冒泡排序
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{24,69,80,57,13}
	//将数组传递给一个函数，完成排序
	Bubblesort(&arr)
	fmt.Println("main arr=",arr) //有序？是有序的
}

8.4 课后练习

略

8.5 查找

🏷 介绍： 在 Golang 中，我们常用的查找有两种:

1. 顺序查找
2. 二分查找(该数组是有序)

🏷 案例演示：

1. 有一个数列：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王 猜数游戏：从键盘中任意输入一个名称，判断数列中是否包含此名称【顺序查找】 代码：

package main
import(
"fmt"
)

func main(){
	//有一个数列：白眉鹰王、金毛狮王、紫衫龙王、青翼幅王
	//猜数游戏：从键盘中任意输入一个名称，判断数列中是否包含此名称【顺序查找】
	//思路
	//1定义一个数组，白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王字符串数组
	//2.从控制台接收一个名字，依次比较，如果发现有，提示
	//1代码
	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("没有找到%w\n”,heroName)
		}
	}

	//顺序查找：第2种方式（推荐.·）
	index := -1
	for i:=0;i<len(names);i++{
		if heroName ==names[i] {
			index=i//将找到的值对应的下标赋给 index
			break
		}
	}
	
	if index !=-1{
		fmt.Printf("找到%v,下标%vn”,heroName,index)
	}else{}
		fmt.Println("没有找到"，heroName)
	}
}

2. 请对一个 有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。【会使用到递归】 二分查找的思路分析：

二分查找的代码实现：

package main  
  
import (  
   "fmt"  
)  
  
//二分查找的函数  
/*  
二分查找的思路: 比如我们要查找的数是 findVal1. arr 是一个有序数组，并且是从小到大排序  
2. 先找到 中间的下标 middle = (leftIndex + rightIndex) / 2, 然后让 中间下标的值和 findVal 进行  
比较  
2.1 如果 arr[middle] > findVal , 就应该向 leftIndex ---- (middle - 1)2.2 如果 arr[middle] < findVal , 就应该向 middel+1---- rightIndex2.3 如果 arr[middle] == findVal ， 就找到  
2.4 上面的 2.1 2.2 2.3 的逻辑会递归执行  
3. 想一下，怎么样的情况下，就说明找不到[分析出退出递归的条件!!]  
if leftIndex > rightIndex {  
// 找不到..  
return ..  
}  
*/  
func BinaryFind(arr *[6]int, leftIndex int, rightIndex int, findVal int) {  
   //判断 leftIndex 是否大于 rightIndex   if leftIndex > rightIndex {  
      fmt.Println("找不到")  
      return  
   }  
   //先找到 中间的下标  
   middle := (leftIndex + rightIndex) / 2  
   if (*arr)[middle] > findVal {  
      //说明我们要查找的数，应该在 leftIndex --- middel-1      BinaryFind(arr, leftIndex, middle-1, findVal)  
   } else if (*arr)[middle] < findVal {  
      //说明我们要查找的数，应该在 middel+1 --- rightIndex      BinaryFind(arr, middle+1, rightIndex, findVal)  
   } else {  
      //找到了  
      fmt.Printf("找到了，下标为%v \n", middle)  
   }  
}  
  
  
func main() {  
   arr := [6]int{1, 8, 10, 89, 1000, 1234}  
   //测试一把  
   BinaryFind(&arr, 0, len(arr)-1, -6)  
}

8.6 二维数组的介绍

多维数组我们只介绍二维数组

8.7 二维数组的应用场景

比如我们开发一个五子棋游戏，棋盘就是需要二维数组来表示。如图

8.8 二维数组快速入门

快速入门案例： 🏷 请用二维数组输出如下图形

0 0 0 0 0 0
0 0 1 0 0 0
0 2 0 3 0 0
0 0 0 0 0 0

🏷 代码演示

package main  
  
import "fmt"  
  
func main() {  
   //1二维数组的演示案例  
   /**  
      000g00      001000      020300      000000      **/   //定义/声明二维数组  
   var arr [4][6]int  
   //1赋初值  
   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.Print(arr[i][j], "")  
      }  
      fmt.Println()  
   }  
}

8.9 使用方式 1: 先声明/定义,再赋值

🏷 语法: var 数组名 [大小][大小]类型 🏷 比如: var arr [2][3]int ， 再赋值。 🏷 使用演示 🏷 二维数组在内存的存在形式(重点)

var arr2[2][3]int //以这个为例来分析arr2在内存的布局1I
arr2[1][1]=10
fmt.Println(arr2)
fmt.Printf("arr2[o]的地址%pn",&arr2[o])
fmt.Printf("arr2[1]的地址%p\n",&arr2[1])

fmt.Printf("arr2[o][o]的地址%p\n",&arr2[o][o])
fmt.Printf("arr2[1][o]的地址%pn”,&arr2[1][o])

8.10 使用方式 2: 直接初始化

🏷 声明：

var 数组名 [大小][大小]类型 = [大小][大小]类型{{初值..},{初值..}}

🏷 赋值(有默认值，比如 int 类型的就是 0) 🏷 使用演示

fmt.Println()
var arr3[2][3]int=[2][3]int{[1,2,3},{4,5,6}}
fmt.Println("arr3=",arr3)

	说明：二维数组在声明/定义时也对应有四种写法[和一维数组类似]
	var 数组名 [大小][大小]类型 = [大小][大小]类型{{初值..},{初值..}}
	var 数组名 [大小][大小]类型 = [...][大小]类型{{初值..},{初值..}}
	var 数组名 = [大小][大小]类型{{初值..},{初值..}}
	var 数组名 = [...][大小]类型{{初值..},{初值..}}

8.11 二维数组的遍历

🏷 双层 for 循环完成遍历 🏷 for-range 方式完成遍历 案例演示：

package main  
  
import "fmt"  
  
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("%v\t", arr3[i][j])  
      }  
      fmt.Println()  
   }  
  
   //for-range来遍历二维数组  
   for i, v := range arr3 {  
      for j, v2 := range v {  
         fmt.Printf("arr3[%v][%v]=%v \t", i, j, v2)  
      }  
      fmt.Println()  
   }  
  
}

8.12 二维数组的应用案例

🏷 要求如下： 定义二维数组，用于保存三个班，每个班五名同学成绩， 并求出每个班级平均分、以及所有班级平均分 🏷 代码

package main  
  
import "fmt"  
  
func main() {  
   /**  
   定义二维数组，用于保存三个班，每个班五名同学成绩，  
   并求出每个班级平均分、以及所有班级平均分  
   */   //1.定义一个二维数组  
   var scores [3][5]float64  
   //2,循环的输入成绩  
   for i := 0; i < len(scores); i++ {  
      for j := 0; j < len(scores[i]); j++ {  
         fmt.Printf("请输入第%d班的第%d个学生的成绩\n", i+1, j+1)  
         fmt.Scanln(&scores[i][j])  
      }  
   }   //fmt.Println(scores)  
   //3.遍历输出成绩后的二维数组，统计平均分  
   totalsum := 0.0 // 定义一个变量，用于累计所有班级的总分  
   for i := 0; i < len(scores); i++ {  
      sum := 8.0 //定义一个变量，用于累计各个班级的总分  
      for j := 0; j < len(scores[i]); j++ {  
         sum += scores[i][j]  
      }  
      totalsum += sum  
      fmt.Printf("第%d班级的总分为%v,平均分%v\n", i+1, sum, sum/float64(len(scores[i])))  
   }  
  
   fmt.Printf("所有班级的总分为%v,所有班级平均分%v\n",  
      totalsum, totalsum/15)  
}