排序与查找，简略版

数组的排序

排序的基本介绍

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

1. 内部排序：
   1. 一次性
   2. 适用数据量小的情况
      将需要处理的数据都加载到内部存储器中进行排序。包括交换式排序，选择式排序，插入式排序
2. 外部排序：
   1. 多次
   2. 适用数据量大的情况
      数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。包括合并排序法，直接合并排序法

交换式排序

交换式排序是内部排序的一种，运用数值比较后，依据判定规则对数据位置进行交换，以达到排序目的
交换式排序有两种

1. 冒泡排序
2. 快速排序

冒泡排序法

冒泡排序的思想：
以递增排序为例，冒泡排序有两种思路：一种是从前向后遍历每次循环都将尚未排序的部分中的最大值放到未排序部分的最后一位；一种是从后向前遍历，每次都将位排序部分的最小值放到未排序部分的最前面

冒泡排序是需要双层循环来实现的

1. 外层循环控制要几次将指定数据放到指定位置（最不理想次数也就是len()-1次）
2. 内层循环控制要想将本轮的指定数据放到指定位置所需要逐个比较数据的次数（最不理想次数也就是len()-i，其中i表示第几次外循环）

优化

只需要本次内部循环没有改变任何数据的位置，就可以说明数组已经排序完毕了，也就可以提前结束内外双循环，从而优化代码。（可以通过设置flag来判断是否有改变数据位置）

冒泡代码

package main

import (
“fmt”
)

func BubbleSort(a *[5]int) {
leng := len((*a))
fmt.Printf(“排序前：%v\n”, (*a))
for i := 0; i < leng-1; i++ {
flag := false
for j := 0; j < leng-1-i; j++ {
if (*a)[j] > (*a)[j+1] {
c := (*a)[j]
(*a)[j] = (*a)[j+1]
(*a)[j+1] = c
if !flag {
flag = true
}
}
}
if !flag {
return
}
}
}
func main() {
a := [5]int{4, 12, 532, 1, 23}
BubbleSort(&a)
fmt.Printf(“排序后：%v”, a)
}
输出结果：
排序前：[4 12 532 1 23]
排序后：[1 4 12 23 532]

数组的查找

1. 顺序查找
2. 二分查找

二分查找

二分查找是对一个有序数列进行的。

二分查找的思路

数组a是一个有序数组，假设是递增的
left=0,right=len(a)-1
mid=(left+right)/2

1. mid<find left=mid+1
2. mid>find right=mid-1
3. mid=find return
4. 123是递归进行的
   如果left>right，就说明找不到这个值。

代码实现

func BinaryFind(arr [6]int, left int, right int, find int) int {
if left > right {
return -1
}
midd := (left + right) / 2
mid := arr[midd]
if mid > find {
return BinaryFind(arr, left, midd-1, find)
} else if mid < find {
return BinaryFind(arr, midd+1, right, find)
} else {
return midd
}
}
func main() {
a := [6]int{1, 3, 6, 8, 10, 21}
index := BinaryFind(a, 0, len(a)-1, 8)
fmt.Printf(“%d”, index)
}