Golang 排序和查找

排序

基本介绍

  1. 排序是将一组数据，依指定的顺序进行排序的过程。

  2. 排序的分类：

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

          交换式排序法

  3. 交换式排序属于内部排序法，是运用数据值比较厚，依判断规则对数据位置进行交换，以达到排序的目的。

  4. 交换式排序算法又可分为两种：

    • 冒泡排序(Bubble sort)
    • 快速排序法(Quick sort)

      冒泡排序法

  5. 冒泡排序(Bubble Sorting)的基本思想是：通过对待排序序列从后往前(从下标较大的元素开始)，依次比较相邻元素的排序码，若发现逆序则交换，是排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向较小的单元)，就象水底下的气泡一样逐渐向上冒。

  6. 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换，从而减少不必要的比较。(优化)

    冒泡排序法案例

  7. 我们将一个无序数列 [24, 69, 80, 57, 13] 使用冒泡排序法将其排成一个从小大大的有序数列。

  8. 冒泡排序的规则
    • 一共会经过 arr.length-1 轮数比较，每一轮将会确定一个数的位置。
    • 每一轮的比较次数在逐渐的减少。【4，3，2，1】
    • 当发现前面的一个数比后面的一个数大的时候，就进行了交换。
  9. 快速入门案例 ```go package main

import “fmt”

//冒泡排序 func BubbleSort(arr [5]int) { fmt.Println(“排序前 arr = “, arr) temp := 0 //临时变量用于做交换

  1. //冒泡排序: 一步一步推导出来
  2. for i := 0; i < len(*arr) - 1; i++ {
  3.     //第一轮的排序(外层第一次)
  4.     for j := 0; j < len(*arr) - 1 - i; j++ {
  5.         if (*arr)[j] > (*arr)[j+1] {
  6.             //交换
  7.             temp = (*arr)[j]
  8.             (*arr)[j] = (*arr)[j+1]
  9.             (*arr)[j+1] = temp
  10.         }
  11.     }
  12.     fmt.Printf("第%v次排序后 arr = %v \n", i+1, *arr)
  13. }
  14. fmt.Println("arr = ", *arr)

}

func main() { var arr = […]int{24, 69, 80, 57, 13} //将数组传递给一个函数，完成排序 BubbleSort(&arr)

  1. fmt.Println("main arr = ", arr) //有序

}

  1. <a name="dc5d07a1"></a>
  2. ## 查找
  4. 1. 在 Golang 中，我们常用的查找有两种： 
  5.    - 顺序查找 
  6.    - 二分查找(该数组是有序的) 
  7. <a name="e11d9bba"></a>
  8. ### 快速入门
  10. 1. 案例一
  11. ```go
  12. package main
  14. import "fmt"
  16. func main() {
  17.     /*
  18.         有一个数列：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王。
  19.         猜数游戏：从键盘中任意输入一个名称，判断数列中是否包含此名称[顺序查找]。
  20.     */
  22.     /*
  23.         思路分析：
  24.             1. 定义一个数组：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王。(字符串数组)
  25.             2. 从控制台接收一个名词，一次比较，如果发现有，提示。
  26.     */
  28.     names := [...]string{"白眉鹰王", "金毛狮王", "紫衫龙王", "青翼蝠王"}
  29.     var heroName string
  30.     fmt.Println("请输入要查找的人名...")
  31.     fmt.Scanln(&heroName)
  33.     //顺序查找：第一种方式
  34.     for i := 0;i < len(names); i++ {
  35.         if heroName == names[i] {
  36.             fmt.Printf("找到%v , 下标是%v\n", heroName, i)
  37.             break
  38.         }else if i == (len(names) - 1) {
  39.             fmt.Printf("没有找到%v\n", heroName)
  40.         }
  41.     }
  44.     //顺序查找：第二种方式(推荐使用)
  45.     index := -1
  46.     for i := 0;i < len(names); i++ {
  47.         if heroName == names[i] {
  48.             index = i //将找到的值对应下标赋给 index
  49.             break
  50.         }
  51.     }
  52.     if index != -1 {
  53.         fmt.Printf("找到%v , 下标是%v\n", heroName, index)
  54.     } else {
  55.         fmt.Printf("没有找到%v\n", heroName)
  56.     }
  57. }

  1. 二分查找的思路：比如我们要找的数是 findVal 。

    • arr是一个有序数组，并且是从小到大排序
    • 先找到中间的下标 middle = (leftIndex + rightIndex) / 2，然后让中间下标的值和 findVal 进行比较。
    • 如果 arr[middle] > findVal，就应该向 leftIndex —- (middle - 1)
    • 如果 arr[middle] < findVal，就应该向 middle + 1 —- rightIndex
    • 如果 arr[middle] == findVal，就找到
    • 上面的逻辑会递归执行。
    • 递归结束的条件 
      1. if leftIndex > rightIndex {
      2. //找不到
      3. return ...
      4. }

  2. 案例二：请对一个有序数组进行二分查找 {1, 8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下表，如果没有就提示没有这个数。 ```go package main

import “fmt”

/ 二分查找的思路：比如我们要查找的数是 findVal 。 (1) arr 是一个有序数组，并且是从小到大排序 (2) 先找到中间的下标 middle = (leftIndex + rightIndex) / 2，然后让中间下标的值和 findVal 进行比较。 (3) 如果 arr[middle] > findVal，就应该向 leftIndex —- (middle - 1) (4) 如果 arr[middle] < findVal，就应该向 middle + 1 —- rightIndex (5) 如果 arr[middle] == findVal，就找到 (6) 上面的逻辑会递归执行。 (7) 递归结束的条件 if leftIndex > rightIndex { //找不到 return … } /

//二分查找的函数 func BinaryFind(arr *[6]int, leftIndex int, rightIndex int, findVal int) {

  1. //判断leftIndex 是否大于 rightIndex
  2. if leftIndex > rightIndex {
  3.     fmt.Println("找不到")
  4.     return
  5. }
  7. //先找到中间的下标
  8. middle := (leftIndex + rightIndex) / 2
  9. if (*arr)[middle] > findVal {
  10.     //说明我们要查找的数，应该在 leftIndex --- (middle - 1)
  11.     BinaryFind(arr, leftIndex, middle - 1, findVal)
  12. } else if (*arr)[middle] < findVal {
  13.     //说明我们要查找的数，应该在 middle + 1 --- rightIndex
  14.     BinaryFind(arr, middle + 1, rightIndex, findVal)
  15. } else {
  16.     //找到了
  17.     fmt.Printf("找到了，下标为%v \n", middle)
  18. }

}

func main() { arr := […]int{1, 8, 10, 89, 1000, 1234} findVal := 89 leftIndex := 0 rightIndex := len(arr) - 1 BinaryFind(&arr, leftIndex, rightIndex, findVal) }

  1. <a name="05aa9447"></a>
  2. ## 多维数组-二维数组
  3. <a name="10a35cde"></a>
  4. ### 二维数组应用场景
  6. 1. 比如我们开发一个五子棋游戏，棋盘就是需要二维数组来表示。
  7. <a name="4c18491c"></a>
  8. ### 二维数组快速入门
  10. 1. 请用二维数组输出如下图形：

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

  2. 2. 案例一
  3. ```go
  4. package main
  6. import "fmt"
  8. func main() {
  9.     //二维数组的演示案例
  10.     /*
  11.         0 0 0 0 0 0
  12.         0 0 1 0 0 0
  13.         0 2 0 3 0 0
  14.         0 0 0 0 0 0
  15.     */
  17.     //定义/声明二维数组
  18.     var arr [4][6]int
  20.     //fmt.Println("arr =", arr)
  22.     //赋初值
  23.     arr[1][2] = 1
  24.     arr[2][1] = 2
  25.     arr[2][3] = 3
  27.     //fmt.Println("arr =", arr)
  30.     //遍历二维数组，按照要求输出图形。
  31.     for i := 0; i < len(arr); i++ {
  32.         for j := 0; j < len(arr[i]); j++ {
  33.             fmt.Print(arr[i][j], " ")
  34.         }
  35.         fmt.Println()
  36.     }
  37. }

二维数组使用方式

  1. 使用方式一：先声明/定义、再赋值

    • 语法 

      1. var 数组名 [大小][大小]类型

    • 使用演示

    • 二维数组在内存的存在形式(重点)
  2. 案例一 ```go package main

import “fmt”

func main() {

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

}

  2. 3. 使用方式二：直接初始化 
  3.    - 语法 
  4. ```go
  5. var 数组名 [大小][大小]类型 = [大小][大小]类型{{初值..},{初值...}}
  • 赋值(有默认值，比如int 类型的就是 0)
  • 使用演示
  • 说明：二维数组在声明/定义时也对应有四种写法[和一维数组类似] 
    1. var 数组名 [大小][大小]类型 = [大小][大小]类型{{初值..},{初值...}}
    2. var 数组名 [大小][大小]类型 = [...][大小]类型{{初值..},{初值...}}
    3. var 数组名 = [大小][大小]类型{{初值..},{初值...}}
    4. var 数组名 = [...][大小]类型{{初值..},{初值...}}
  1. 案例二 ```go package main

import “fmt”

func main() { //使用方式2：直接初始化 var arr3 [2][3]int = [2][3]int{{1,2,3},{4,5,6}} fmt.Println(“arr3 =”, arr3)

}

  1. <a name="01dc47a1"></a>
  2. ### 二维数组遍历
  4. 1. 双层 for 循环完成遍历
  5. 1. for-range 方式完成遍历
  6. 1. 案例一
  7. ```go
  8. package main
  10. import "fmt"
  12. func main() {
  13.     //演示二维数组的遍历
  15.     //双层 for 循环完成遍历
  17.     var arr [2][3]int = [2][3]int{{1,2,3},{4,5,6}}
  19.     for i := 0; i < len(arr); i++ {
  20.         for j:= 0; j < len(arr[i]); j++ {
  21.             fmt.Printf("%v\t", arr[i][j])
  22.         }
  23.         fmt.Println()
  24.     }
  26.     // for-range 方式完成遍历
  27.     for i, v := range arr {
  28.         for j, v2 :=range v {
  29.             fmt.Printf("arr[%v][%v] = %v\t", i, j, v2)
  30.         }
  31.         fmt.Println()
  32.     }
  33. }

二维数组应用案例

  1. 案例一：定义二维数组，用于保存三个班，每个班五名同学成绩，并求出每个班级平均分、以及所有班级平均分。 ```go package main

import “fmt”

func main() { / 定义二维数组，用于保存三个班，每个班五名同学成绩，并求出每个班级平均分、以及所有班级平均分。 /

  1. //1. 定义一个二维数组
  2. var scores [3][5]float64
  4. //2. 循环的输入成绩
  5. for i := 0; i < len(scores); i++ {
  6.     for j := 0; j < len(scores[i]); j++ {
  7.         fmt.Printf("请输入第 %d 班的第 %d 个学生的成绩：\n", i+1, j+1)
  8.         fmt.Scanln(&scores[i][j])
  9.     }
  10. }
  12. //fmt.Println(scores)
  15. //3.遍历输入成绩后的二维数组，统计平均分。
  16. totalSum := 0.0 //定义一个变量，用于累计所有班级的总分。
  17. for i := 0; i < len(scores); i++ {
  18.     sum := 0.0 // 定义一个变量累计各个班级的总分
  19.     for j := 0; j < len(scores[i]); j++ {
  20.         sum += scores[i][j]
  22.     }
  23.     totalSum += sum
  24.     fmt.Printf("第%d班级的总分为 %v, 平均分 %v\n", i + 1, sum, sum / float64(len(scores[i])))
  25. }
  26. fmt.Printf("所有班级的总分为 %v, 所有班级的平均分 %v\n", totalSum, totalSum / 15)

} ```

课程来源