排序是将一组数据，依指定的顺序进行排序的过程。
一、排序的分类
内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。包括交换排序、选择排序和插入排序。
外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。包括合并排序和直接合并排序。
二、排序
1、冒泡排序
通过对待排序序列从后向前(从下标较大的元素开始)，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元)。
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排查过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较(优化)。
package main
import "fmt"
func BubbleSort(arr *[5]int) {
fmt.Println("排序前arr= ", (*arr))
for i := 0; i < len(*arr)-1; i++ {
for j := 0; j < len(*arr)-1-i; j++ {
if (*arr)[j] > (*arr)[j+1] {
(*arr)[j+1] = (*arr)[j+1] + (*arr)[j]
(*arr)[j] = (*arr)[j+1] - (*arr)[j]
(*arr)[j+1] = (*arr)[j+1] - (*arr)[j]
}
}
}
fmt.Println("排序后arr= ", (*arr))
}
func main() {
arr := [5]int{2, 4, 1, 9, 8}
BubbleSort(&arr)
fmt.Println("main arr= ", arr)
}
2、选择排序
选择排序(select sorting)也是一种简单的排序方法。它的基本思想是:第一次从R[0]~R[n-1]中选 取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，第三次从R[2]~R[n-1]中选取最小值，与 R[2]交换，...，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，..., 第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
package main
import "fmt"
func SelectSort(arr *[9]int) {
//(*arr)[1]=600 等价于 arr[1]=600
for i := 0; i < len(arr)-1; i++ {
min := arr[i]
minIndex := i
for j := i + 1; j < len(arr); j++ {
if min > arr[j] {
min = arr[j]
minIndex = j
}
}
if minIndex != i {
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
fmt.Printf("第%d次 %v
", i+1, *arr)
}
}
func main() {
var arr [9]int = [9]int{8, 0, 2, 4, 1, 6, 3, 5, 7}
SelectSort(&arr)
}
3、插入排序
插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个 元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
package main
import "fmt"
func InsertSort(arr *[9]int) {
for i := 1; i < len(arr); i++ {
insertVal := arr[i]
j := i - 1
for j >= 0 && arr[j] < insertVal {
arr[j+1] = arr[j]
j--
}
if j+1 != i {
arr[j+1] = insertVal
}
fmt.Printf("第%d次插入后%v
", i, *arr)
}
}
func main() {
var arr [9]int = [9]int{8, 0, 2, 4, 1, 6, 3, 5, 7}
InsertSort(&arr)
}
4、快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
package main
import "fmt"
//left表示数组左边的下标，right表示数组右边的下标，pivot表示中轴、支点
func QuickSort(left int, right int, array *[9]int) {
l := left
r := right
pivot := array[(left+right)/2]
tmp := 0
//将比pivot小的数放到左边,比pivot大的数放到右边
for ; l < r; {
//从pivot的左边找到大于等于pivot的值
for ; array[l] < pivot; {
l++
}
//从pivot的右边边找到小于等于pivot的值
for ; array[r] > pivot; {
r--
}
//1>=r表明本次分解任务完成
if l >= r {
break
}
tmp = array[l]
array[l] = array[r]
array[r] = tmp
if array[l] == pivot {
r--
}
if array[r] == pivot {
l++
}
}
if l == r {
l++
r--
}
//向左递归
if left < r {
QuickSort(left, r, array)
}
//向右递归
if right > l {
QuickSort(l, right, array)
}
}
func main() {
var arr [9]int = [9]int{8, 0, 2, 4, 1, 6, 3, 5, 7}
fmt.Println("初始", arr)
//调用快速排序
QuickSort(0, len(arr)-1, &arr)
fmt.Println("排序后", arr)
三、查找
在golang中常用的查找有两种：顺序查找和二分查找(数组是有序的)。
1、顺序查找
package main
import "fmt"
func main() {
//有一个数列:白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王.从键盘中任意输入一个名称，判断数列中是否包含此名称【顺序查找】
//实现方式一
names := [4]string{"白眉鹰王", "金毛狮王", "紫衫龙王", "青翼蝠王"}
var heroName = ""
fmt.Println("请输入要查找的人名")
fmt.Scanln(&heroName)
for i := 0; i < len(names); i++ {
if heroName == names[i] {
fmt.Printf("找到%v,下标%v
", heroName, i)
break
} else if i == (len(names) - 1) {
fmt.Printf("没有找到%v
", heroName)
}
}
//实现方式二
index := -1
for i := 0; i < len(names); i++ {
if heroName == names[i] {
index = i
break
}
}
if index != -1 {
fmt.Printf("找到%v,下标%v
", heroName, index)
} else {
fmt.Println("没有找到", heroName)
}
}
2、二分查找
package main
import "fmt"
func BinaryFind(arr *[6]int, leftIndex int, rightIndex int, findVal int) {
if leftIndex > rightIndex {
fmt.Println("找不到", findVal)
return
}
middle := (leftIndex + rightIndex) / 2
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, -6)
BinaryFind(&arr, 0, len(arr)-1, 89)
}
四、二维数组
二维数组在声明/定义时的四种写法[
var 数组名 [大小][大小]类型 = [大小][大小]类型{{初值..},{初值..}}
var 数组名 [大小][大小]类型 = [...][大小]类型{{初值..},{初值..}}
var 数组名 = [大小][大小]类型{{初值..},{初值..}}
var 数组名 = [...][大小]类型{{初值..},{初值..}}
二维数组的遍历
package main
import "fmt"
func main() {
var arr = [2][3]int{{1, 2, 3}, {4, 5, 6}}
//for循环遍历
for i := 0; i < len(arr); i++ {
for j := 0; j < len(arr[i]); j++ {
fmt.Printf("%v ", arr[i][j])
}
fmt.Println()
}
//for - range遍历二维数组
for i, v := range arr {
for j, v2 := range v {
fmt.Printf("arr[%v][%v]=%v ", i, j, v2)
}
fmt.Println()
}
}
定义二维数组，用于保存三个班，每个班五名同学成绩，并求出每个班级平均分、以及所有班级平均分
package main
import (
"fmt"
)
func main() {
/*
定义二维数组，用于保存三个班，每个班五名同学成绩
并求出每个班级平均分、以及所有班级平均分
*/
var scores [3][5]float64
for i := 0; i < len(scores); i++ {
for j := 0; j < len(scores[i]); j++ {
fmt.Printf("请输入第%d班的第%d个学生的成绩
", i+1, j+1)
fmt.Scanln(&scores[i][j])
}
}
totalSum := 0.0
for i := 0; i < len(scores); i++ {
sum := 0.0
for j := 0; j < len(scores[i]); j++ {
sum += scores[i][j]
}
totalSum += sum
fmt.Printf("第%d班的总分为%v,平均分为%v
", i+1, sum, sum/float64(len(scores[i])))
}
fmt.Printf("所有班级的总分是%v,所有班级的平均分是%v
", totalSum, totalSum/15)
}