go 排序和查找

排序的介绍

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

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

2、外部排序法：

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

交换式排序法

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

1、冒泡排序法（Bubble sort）

image.png

案例（冒泡排序法）:

将5个无序：24,69,80,57,13，使用冒泡排序法将其排成一个从小到大的有序数列。

图例：

• 写多重for循环，先从简单的内循环写起

package main

import (
    "fmt"
)

//冒泡排序
func minToMax(arr [5]int) [5]int {
    for i := len(arr) - 1; i >= 0; i-- {
        var tmp int = 0
        for j := 0; j < len(arr)-1; j++ {
            if arr[j] > arr[j+1] {
                tmp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = tmp
            }
        } //内循环
    } //外循环
    return arr
}

func main() {
    //定义数组
    arr := [5]int{77, 69, 80, 57, 13}
    var a = minToMax(arr)
    fmt.Println(a)
}

2、快速排序法 (Quick sort)

顺序查找

• 介绍
  1、顺序查找
  2、二分查找

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

• 代码实现：

    //定义名称数组
    names := [4]string{"白眉鹰王", "金毛狮王", "紫衫龙王", "青翼蝠王"}
    //定义输入的变量字符串
    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 //如果找不到index就是-1；如果找到就是相应的下标
    for i := 0; i < len(names); i++ {
        if heroname == names[i] { //找到了
            index = i
            break
        }
    }
    if index == -1 {
        fmt.Printf("没有找到%v\n", heroname)
    } else {
        fmt.Printf("找到了%v,下标是%v\n", heroname, index)
    }

推荐使用index方式

二分查找

2、请对一个有序数组进行二分查找{ 1，8，10，89，1000，1234 }，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示“没有这个数” （使用递归）

• 代码实现

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 {
        //如果中间下标的值大于传入的值 ，则应该在left 查找。下标范围是 leftIndex到 middle -1
        BinaryFind(arr, leftIndex, middle-1, findVal)
    } else if (*arr)[middle] < findVal {
        //如果中间下标的值小于传入的值，则应该在right 查找。下标范围是 middle +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)
}