6.Go语言数组的排序和查找

main.go

// Go语言数组的排序和查找
package main

//  包的本质是创建不同的文件夹
//  go的每一个文件都是属于一个包的
//  go以包的形式管理项目和文件目录。
//  import "包的路径"
import (
     "day7/model/utils" 
    _"fmt"
)


var content string = `
————————————————Go语言数组的排序和查找————————————————————
一、排序
二、查找

`


func main() {
    utils.Entry()
}

utils.go

// Go语言数组的排序和查找
package utils

import (
    "fmt"
)

var layout string = "2006-01-02"

// 全局变量
var Author string = "Jhou Shuai"

// 全局变量
var Description string = "Go语言数组的排序和查找"

//全局变量：使用反引号来定义多行字符串
var Content string = `
————————————————Go语言数组的排序和查找————————————————————
一、排序
    排序是将一组数据，依指定的顺序进行排列的过程
    排序分类：
        1.内部排序：
            指将需要处理的所有数据都加载到内部存储器中进行排序。
        包括：交换式排序、选择式排序、插入式排序
        一次性把所有数据加载到内存中排序
        交换式排序：
            冒泡排序 Bubble Sorting

        2.外部排序：
            数据量过大，无法全部加载到内存中，需要借助外部存储进
        行排序。包括：合并排序法、直接合并排序法
二、查找
    1.顺序查找
    2.二分查找
        前提：数组是有序的
`

/**
 * [Init 入口]
 * @author Jhou Shuai
 * @datetime 2019-05-18T11:58:33+0800
 */
func Entry() {
    // var intArr [5]int = [...]int{24,69,80,57,13}
    // bubbleSorting(&intArr)
    // findArry()
    var intArr [6]int = [...]int{1,8,10,89,1000,1234}
    binarySearch(&intArr,0,len(intArr),666)
}

/**
 * [bubbleSorting 冒泡排序 Bubble Sorting]
 * 从小到大
 * 思路（思想）-》代码（语法）
 * 经过len(intArr)-1论比较
 * 每一轮：比较的次数是递减[4,3,2,1]=len(intArr)-1-第几轮(从零开始的)
 * 即前面的一个数与后面的一个数比较  如果前面的数大就交换
 * @author Jhou Shuai
 * @datetime 2019-05-30T09:53:33+0800
 * @example:
 * var intArr [5]int = [...]int{24,69,80,57,13}
 * bubbleSorting(&intArr)
 */
func bubbleSorting(intArr *[5]int) {
    // 第一轮：
    // 第1次：24与69  [24,69,80,57,13]
    // 第2次：69与80  [24,69,80,57,13]
    // 第3次：80与57  80>57 [24,69,57,80,13]
    // 第4次：80与13  80>13 [24,69,57,13,80]
    // for j := 0; j< 4; j++ {
    //     if (*intArr)[j] > (*intArr)[j+1] {
    //         (*intArr)[j]   = (*intArr)[j] + (*intArr)[j+1]
    //         (*intArr)[j+1] = (*intArr)[j] - (*intArr)[j+1]
    //         (*intArr)[j]   = (*intArr)[j] - (*intArr)[j+1]
    //     }
    // }


    // 第二轮：
    // 第1次：24与69  [24,69,57,13,80]
    // 第2次：69与57  69>57 [24,57,69,13,80]
    // 第3次：69与13  69>13 [24,57,13,69,80]
    // for j := 0; j< 3; j++ {
    //     if (*intArr)[j] > (*intArr)[j+1] {
    //         (*intArr)[j]   = (*intArr)[j] + (*intArr)[j+1]
    //         (*intArr)[j+1] = (*intArr)[j] - (*intArr)[j+1]
    //         (*intArr)[j]   = (*intArr)[j] - (*intArr)[j+1]
    //     }
    // }

    // 第三轮：
    // 第1次：24与57  [24,57,13,69,80]
    // 第2次：57与13  57>13 [24,13,57,69,80]
    // for j := 0; j< 2; j++ {
    //     if (*intArr)[j] > (*intArr)[j+1] {
    //         (*intArr)[j]   = (*intArr)[j] + (*intArr)[j+1]
    //         (*intArr)[j+1] = (*intArr)[j] - (*intArr)[j+1]
    //         (*intArr)[j]   = (*intArr)[j] - (*intArr)[j+1]
    //     }
    // }

    // 第四轮：
    // 第1次：24与13 24>13 [13,24,57,69,80]
    // for j := 0; j< 1; j++ {
    //     if (*intArr)[j] > (*intArr)[j+1] {
    //         (*intArr)[j]   = (*intArr)[j] + (*intArr)[j+1]
    //         (*intArr)[j+1] = (*intArr)[j] - (*intArr)[j+1]
    //         (*intArr)[j]   = (*intArr)[j] - (*intArr)[j+1]
    //     }
    // }
    intArrLen := len(intArr)
    for i := 0; i < intArrLen-1; i++ {
        for j := 0; j< intArrLen-1-i; j++ {
            if (*intArr)[j] > (*intArr)[j+1] {
                (*intArr)[j]   = (*intArr)[j] + (*intArr)[j+1]
                (*intArr)[j+1] = (*intArr)[j] - (*intArr)[j+1]
                (*intArr)[j]   = (*intArr)[j] - (*intArr)[j+1]
            }
        }
    }
    fmt.Println((*intArr))
}


/**
 * [findArry 顺序查找]
 * @author Jhou Shuai
 * @datetime 2019-05-30T11:39:01+0800
 */
func findArry() {
    var flag = false
    var players [4]string = [...]string{"Uzi","Faker","Mata","TheShy"}
    var name string
    fmt.Print("请输入你喜欢的选手>>>")
    fmt.Scanln(&name)
    for _,val := range players{
        if name == val {
            flag = true
            break;
        }
    }

    if flag {
        fmt.Printf("找到咯。。。恭喜你！%v签名贴 \n",name)
    }else{
         fmt.Printf("没找到%v选手咯... \n",name)
    }
}


/**
 * [binarySearch 二分查找]
 * 2.二分查找
        前提：数组是有序的
 * @author Jhou Shuai
 * @datetime 2019-05-30T11:52:58+0800
 * var intArr [6]int = [...]int{1,8,10,89,1000,1234}
 * binarySearch(&intArr,0,len(intArr),666)
 */
func binarySearch(intArr *[6]int,leftIndex int,rightIndex int,fandVal int) {
    // 思路：
    // 0.我们要查找的数是fandVal
    // 1.intArr必须是一个有序的数组，并且是从小到大排列的
    // 2.定义：
    //      左边的下标为 leftIndex
    //      右边的下标为 rightIndex
    //      leftIndex <= rightIndex
    //      中间的下标为 middle = (leftIndex+rightIndex)/2
    // 3.intArr[middle] 与 findVal进行比较，有三种情况如下：
    //      3.1.intArr[middle]>fandVal 就应该在[leftIndex,rightIndex=(middle-1)]继续查找
    //      3.2.intArr[middle]<fandVal 就应该在[leftIndex=(middle+1),rightIndex]继续查找
    //      3.3.intArr[middle]=fandVal 找到咯。
    //      3.4.上面的过程(3.1,3.2,3.3)会递归执行
    // 4.最终都没有找到，我们想要的数据。退出递归条件：
    //      最后一次查找的时候：
    //          leftIndex == rightIndex
    //      若在继续：
    //          leftIndex > rightIndex 
    //       此时应该退出
    //       If leftIndex > rightIndex {
    //          //未找到我们想要的数据
    //          return ...
    //       }
    if leftIndex > rightIndex {
        fmt.Println("未找到我们想要的数据")       
        return 
    }

    var middle int = (leftIndex+rightIndex)/2

    if (*intArr)[middle] > fandVal {
        // 3.1.intArr[middle]>fandVal 就应该在[leftIndex,rightIndex=(middle-1)]继续查找
        binarySearch(intArr, leftIndex, middle-1, fandVal)
    }else if (*intArr)[middle] < fandVal {
        // 3.2.intArr[middle]<fandVal 就应该在[leftIndex=(middle+1),rightIndex]继续查找
        binarySearch(intArr, middle+1,rightIndex , fandVal)
    }else{
        // 3.3.intArr[middle]=fandVal 找到咯
        fmt.Printf("找到咯，下标为:%v \n",middle)       
    }
}