golang 冒泡排序和查找

内部排序和外部排序

1.内部排序（数据量较少使用）

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

2.外部排序法（数据量较大使用）

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

交换式排序

1.冒泡排序法（Bubble sort）

2.快速排序法（Quick sort）

冒泡排序

package main
import(
	"fmt"
)

func sort(arr []int) []int{
	arrLen := len(arr)
	for i := 0; i < arrLen; i++{
		for k := i+1; k < arrLen; k++{
			if arr[i] > arr[k] {
			   sum := arr[i]
			   arr[i] = arr[k]
			   arr[k] = sum
			}
		}
	}
	return arr
}

func main(){
  arr := []int{2,20,18,23,16,15,11,12,5,8,9,6,3,4,1,50}
  fmt.Println(sort(arr))
  //结果：[1 2 3 4 5 6 8 9 11 12 15 16 18 20 23 50]
}

1.顺序查找

2.二分查找

案例演示：

1.有一个数列：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王、

猜数游戏：从键盘中任意输入一个名称，判断数列中是否包含此名称【顺序查找】

package main

import (
    "fmt"
)

func main() {
	names := [4]string{"白眉鹰王","金毛狮王","紫衫龙王","青翼蝠王"}

	hreonName := ""
	fmt.Println("请输入查询的名称。。。")
	fmt.Scanln(&hreonName)

	//顺序查找 第一种方式
	for i := 0; i < len(names); i++{
		if hreonName == names[i]{
			fmt.Printf("找到%v 下面是%v\n",hreonName,i)
			break
		}else if i == len(names) - 1{
			fmt.Printf("没有找到%v",hreonName)
		}
	}
	
	//顺序查找 第二种方式 （推荐使用 代码清晰）
	index := -1
	for i := 0; i < len(names); i++{
		if hreonName == names[i]{
			index = i
		}
	}
	if( index != -1){
		fmt.Printf("找到%v 下面是%v\n",hreonName,index)
	}else{
		fmt.Printf("没有找到%v",hreonName)
	}

}

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

《必须是有序数组才可以进行二分查找》

package main
import(
	"fmt"
)

func BinaryFind(arr *[6]int,leftIndex,rightIndex,findVal int){
	//如果 leftIndex > rightIndex 的说明都已经找过了但是没有找到
	if leftIndex > rightIndex{
		fmt.Printf("%v 没有找到",findVal)
		return
	}
    
	//首先冲中间的下标开始区分
	middle := (leftIndex + rightIndex) / 2
	//如果 arr[middle] > findVal 就应该从 leftIndex ---- （middle - 1）
	//如果 arr[middle] < findVal 就应该从 (middle + 1) ---- rightIndex
	//如果相等就返回已找到 并且返回下标
	if (*arr)[middle] > findVal {
		BinaryFind(arr,leftIndex,middle - 1,findVal)
	}else if (*arr)[middle] < findVal {
		BinaryFind(arr,middle + 1,rightIndex,findVal)
	}else{
		fmt.Printf("%v已找到，下标是%v",findVal,middle)
	}
}

func main(){
	arr := [6]int{1,8,10,89,1000,1234}

	BinaryFind(&arr,0,len(arr) - 1,1234)
}