排序

排序的基本介绍

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

  1. 内部排序

指将需要处理的所有数据都加载到内部存储器中进行排序。包括（交换式排序法、选择式排序法和插入式排序法）

  1. 外部排序

数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。包括（合并排序法和直接合并排序法）
冒泡排序的思路分析

冒泡排序思路分析

arr = 【24,69,80,57,13】 ， 让前面的数和后面的数进行比较，如果前面的数大，则交换。
第一轮的排序【外层】
第1次比较：【24,69,80,57,13】
第2次比较: 【24,69,80,57,13】
第3次比较： 【24,69,57,80,13】
第4次比较： 【24,69,57,13,80】
第二轮的排序【外层】
第1次比较：【24,69,57,13,80】
第2次比较：【24,57,69,13,80】
第3次比较： 【24,57,13,69,80】
第三轮的排序【外层】
第1次比较： 【24,57,13,69,80】
第2次比较： 【24,13,57,69,80】
第四轮的排序【外层】
第1次比较：【13,24,57,69,80】
冒泡排序的规则：

  1. 一共会经过 arr.length-1次的轮数比较，每一轮将会确定一个数的位置。
  2. 每一轮的比较次数再逐渐的减少。【4,3,2,1】

  3. 当发现前面的一个数比后面的一个数大的时候，就进行了交换。

    冒泡排序实现

    1. //冒泡排序
    2. func BubbleSort(arr *[5]int) {
    3. temp := 0 //临时变量(用于做交换)
    4. //冒泡排序..一步一步推导出来的
    5. for i := 0; i < len(*arr)-1; i++ {
    6.     for j := 0; j < len(*arr)-1-i; j++ {
    7.         if (*arr)[j] > (*arr)[j+1] {
    8.             //交换
    9.             temp = (*arr)[j]
    10.             (*arr)[j] = (*arr)[j+1]
    11.             (*arr)[j+1] = temp
    12.         }
    13.     }
    14. }
    15. }
    16. //简写
    17. func BbSort(arr *[5]int) {
    18. var temp int
    19. len := len(*arr)-1
    20. for i := 0; i < len; i++ {
    21.     for j := 0; j < len-i; j++ {
    22.         if arr[j+1] > arr[j] {
    23.             temp = arr[j]
    24.             arr[j] = arr[j+1]
    25.             arr[j+1] = temp
    26.         }
    27.     }
    28. }
    29. }
    30. func main() {
    31. //定义数组
    32. arr := [5]int{24, 69, 80, 57, 13}
    33. //将数组传递给一个函数，完成排序
    35. BubbleSort(&arr)
    36. //BbSort(&arr)
    38. fmt.Println("main arr=", arr) //有序? 是有序的
    39. }

    查找

    在 Golang 中，我们常用的查找有两种: 顺序查找 、二分查找(该数组是有序)

    顺序查找

    1. func main() {
    2. //有一个数列：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王
    3. //猜数游戏：从键盘中任意输入一个名称，判断数列中是否包含此名称【顺序查找】
    4. //思路
    5. //1 定义一个数组, 白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王 字符串数组
    6. //2.从控制台接收一个名字，依次比较，如果发现有，提示
    8. //代码
    9. names := [4]string{"白眉鹰王", "金毛狮王", "紫衫龙王", "青翼蝠王"}
    10. var heroName = ""
    11. fmt.Println("请输入要查找的人名...")
    12. fmt.Scanln(&heroName)
    14. //顺序查找:第一种方式
    15. // for i := 0; i < len(names); i++ {
    16. //     if heroName == names[i] {
    17. //         fmt.Printf("找到%v , 下标%v \n", heroName, i)
    18. //         break
    19. //     } else if i == (len(names) - 1) {
    20. //         fmt.Printf("没有找到%v \n", heroName)
    21. //     }
    22. // }
    24. //顺序查找:第2种方式(推荐)
    25. index := -1
    27. for i := 0; i < len(names); i++ {
    28.     if heroName == names[i] {
    29.         index = i //将找到的值对应的下标赋给 index
    30.         break
    31.     } 
    32. }
    33. if index != -1 {
    34.     fmt.Printf("找到%v , 下标%v \n", heroName, index)
    35. } else {
    36.     fmt.Println("没有找到", heroName)
    37. }
    38. }

    二分查找

    请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示”没有这个数”。
    arr = [ 1,8, 10, 89, 1000, 1234]
    二分查找的思路: 比如我们要查找的数是 findVal

  4. arr是一个有序数组，并且是从小到大排序

  5. 先找到 中间的下标 middle = (leftIndex + rightIndex) / 2, 然后让 中间下标的值和findVal进行比较
    1. 如果 arr[middle] > findVal , 就应该向 leftIndex —— (middle - 1)
    2. 如果 arr[middle] < findVal , 就应该向 middel+1—— rightIndex
    3. 如果 arr[middle] == findVal ， 就找到

  6. 上面的逻辑会递归执行，当leftIndex > rightIndex 没找到，退出递归 ```go //二分查找的函数 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, 8)

} ```