- 选择排序
- 冒泡排序
- 插入排序
- 堆排序
- 快速排序
选择排序
从下标0开始到length-1 , 每次选出一个最大或最小值, 交换 ，和冒泡排序不同，冒泡时交换频率很高
1package main
2import "fmt"
3func selectSort(sortNumArr []int) []int {
4 len := len(sortNumArr)
5 for i := 0; i < len-1; i++ { //只剩一个元素不需要挑选，
6 max := i //标记索引
7 for j := i + 1; j < len; j++ { //每次选出一个极大值
8 if sortNumArr[max] < sortNumArr[j] {
9 max = j // 标记极大值大索引
10 }
11 }
12 sortNumArr[i], sortNumArr[max] = sortNumArr[max], sortNumArr[i]
13 }
14 return sortNumArr
15}
16func main() {
17 var intNumArr = []int{8}
18 res := selectSort(intNumArr)
19 fmt.Println(res)
20}
字符串比较大小
1strings.Compare("string1","string2")
冒泡排序
1package main
2
3import "fmt"
4
5//11,9,2,8,3,7,4,6,5,10
6//9 11 2 8 3 7 4 6 5 10
7//9 2 11 8 3 7 4 6 5 10
8//9 2 8 11 3 7 4 6 5 10
9//9 2 8 3 11 7 4 6 5 10
10//9 2 8 3 7 11 4 6 5 10
11//9 2 8 3 7 4 11 6 5 10
12//9 2 8 3 7 4 6 11 5 10
13//9 2 8 3 7 4 6 5 11 10
14//9 2 8 3 7 4 6 5 10 11
15//9 2 8 3 7 4 6 5 10
16
17func BubbleFindMax(arr []int) int {
18 length := len(arr) //求数组长度
19 if length <= 1 {
20 return arr[0]
21 } else {
22 for i := 0; i < length-1; i++ {
23 if arr[i] > arr[i+1] { //两两比较
24 arr[i], arr[i+1] = arr[i+1], arr[i]
25 }
26 }
27 return arr[length-1]
28 }
29}
30
31func Bubblesort(arr []int) []int {
32 length := len(arr) //求数组长度
33 if length <= 1 {
34 return arr
35 } else {
36 for i := 0; i < length-1; i++ { //只剩一个，不需要冒泡了
37 isneedexchange := false //优化， 如果出现不用交换的场景，表示已经有序
38 for j := 0; j < length-1-i; j++ {
39 if arr[j] > arr[j+1] { //两两比较
40 arr[j], arr[j+1] = arr[j+1], arr[j]
41 isneedexchange = true
42 }
43 }
44 if !isneedexchange {
45 break
46 }
47 fmt.Println(arr)
48
49 }
50
51 return arr
52 }
53}
54
55func main05() {
56 arr := []int{11, 9, 2, 8, 3, 7, 4, 6, 5, 10}
57 //fmt.Println(BubbleFindMax(arr))
58 fmt.Println(Bubblesort(arr))
59
60}
插入排序
找到位置比自己小（大）的插入进去。
1package main
2
3import "fmt"
4
5func InsertTest(arr []int) []int {
6 //假定处理下标3的， 从下标2开始找，找到比 下标3的值小的位置插入进去，
7 num := arr[3]
8 j := 3 - 1
9 for ; j >= 0 && arr[j] > num; j-- {
10 arr[j+1] = arr[j]
11 }
12 arr[j+1] = num
13 return arr
14}
15
16func InsertSort(arr []int) []int {
17 for i := 1; i < len(arr); i++ {
18 num := arr[i]
19 j := i - 1
20 for ; j >= 0 && arr[j] > num; j-- {
21 arr[j+1] = arr[j]
22 }
23 arr[j+1] = num
24 }
25 return arr
26
27}
28
29func main() {
30 var arr = []int{1, 2, 9, 8, 0, 3, 7, 4, 5, 6}
31 fmt.Println(InsertTest(arr)) //[1 2 8 9 0 3 7 4 5 6]
32 fmt.Println(InsertSort(arr))
33}
堆排序
n代表数组长度
树的数量 <= n/2
1package main
2
3import "fmt"
4
5func HeapSort(arr[] int) []int{
6 length:=len(arr)
7 for i:=0;i<length;i++{
8 lastmesslen:=length-i //每次截取一段
9 HeapSortMax(arr,lastmesslen) //arr[0] 就是最大的
10 fmt.Println(arr)
11 if i<length{
12 arr[0],arr[lastmesslen-1]=arr[lastmesslen-1],arr[0] //把最大的放在最后面
13 }
14 fmt.Println("ex",arr)
15 }
16 return arr
17}
18
19
20func HeapSortMax(arr[] int,length int ) []int{
21 //length:=len(arr)//数组长度
22 if length <=1{
23 return arr //一个元素的数组，直接返回
24 }else{
25 depth:=length/2-1 //深度(顶点的最大深度）， n 2*n+1,2*n+2 ,树的数量等于depth+1个
26 for i:=depth;i>=0;i--{ //循环所有的三节点
27 topmax:=i //假定最大的在i的位置 ，
28 leftchild:=2*i+1
29 rightchild:=2*i+2 //左右孩子的节点
30 if leftchild <=length-1 && arr[leftchild]>arr[topmax]{ //防止越界
31 topmax=leftchild //如果左边比我大，记录最大
32 }
33 if rightchild<=length-1 && arr[rightchild]>arr[topmax]{
34 topmax=rightchild //如果右边比我大，记录最大
35 }
36 if topmax!=i{ //确保i的值就是最大
37 arr[i],arr[topmax]=arr[topmax],arr[i]
38 }
39 }
40 return arr
41 }
42}
43func main(){
44 arr:=[]int {1,9,2,8,3,7,4,6,5,10}
45 fmt.Println(HeapSort(arr))
46}
1[10 1 7 8 9 2 4 6 5 3]
2ex [3 1 7 8 9 2 4 6 5 10]
3[9 3 7 8 1 2 4 6 5 10]
4ex [5 3 7 8 1 2 4 6 9 10]
5[8 5 7 3 1 2 4 6 9 10]
6ex [6 5 7 3 1 2 4 8 9 10]
7[7 5 6 3 1 2 4 8 9 10]
8ex [4 5 6 3 1 2 7 8 9 10]
9[6 5 4 3 1 2 7 8 9 10]
10ex [2 5 4 3 1 6 7 8 9 10]
11[5 2 4 3 1 6 7 8 9 10]
12ex [1 2 4 3 5 6 7 8 9 10]
13[4 3 1 2 5 6 7 8 9 10]
14ex [2 3 1 4 5 6 7 8 9 10]
15[3 2 1 4 5 6 7 8 9 10]
16ex [1 2 3 4 5 6 7 8 9 10]
17[2 1 3 4 5 6 7 8 9 10]
18ex [1 2 3 4 5 6 7 8 9 10]
19[1 2 3 4 5 6 7 8 9 10]
20ex [1 2 3 4 5 6 7 8 9 10]
21[1 2 3 4 5 6 7 8 9 10]
快速排序
利用递归，在内存中处理， 把数组元素分成 左，中，右 3堆
1package main
2
3import (
4 "fmt"
5 "math/rand"
6)
7
8//3,9,2,8,1,7,4,6,5,10
9//3 9,2,8,1,7,4,6,5,10
10// 2,1 3, 9,,8,7,4,6,5,10
11
12// 9,2,8,,7,4,6,5,10
13// ,8,7,4,6,5 9 10
14//4 5 6
15
16func QuickSort(arr []int) []int {
17 length := len(arr) //数组长度
18 if length <= 1 {
19 return arr //一个元素的数组，直接返回
20 } else {
21 splitdata := arr[0] //以第一个为基准
22 low := make([]int, 0, 0) //存储比我小的
23 high := make([]int, 0, 0) //存储比我大的
24 mid := make([]int, 0, 0) //存储与我相等
25 mid = append(mid, splitdata) //加入第一个相等
26
27 for i := 1; i < length; i++ {
28 if arr[i] < splitdata {
29 low = append(low, arr[i])
30 } else if arr[i] > splitdata {
31 high = append(high, arr[i])
32 } else {
33 mid = append(mid, arr[i])
34 }
35 }
36 low, high = QuickSort(low), QuickSort(high) //切割递归处理
37 myarr := append(append(low, mid...), high...)
38 return myarr
39 }
40}
41
42func QuickSort2(arr []int) []int {
43 length := len(arr) //数组长度
44 if length <= 1 {
45 return arr //一个元素的数组，直接返回
46 } else {
47 //n:=length-1//n>=0 && n<=length-1
48 n := rand.Int() % length
49 splitdata := arr[n] //以第一个为基准
50 low := make([]int, 0, 0) //存储比我小的
51 high := make([]int, 0, 0) //存储比我大的
52 mid := make([]int, 0, 0) //存储与我相等
53 mid = append(mid, splitdata) //加入第一个相等
54
55 for i := 0; i < length; i++ {
56 if i == n {
57 continue
58 }
59 if arr[i] < splitdata {
60 low = append(low, arr[i])
61 } else if arr[i] > splitdata {
62 high = append(high, arr[i])
63 } else {
64 mid = append(mid, arr[i])
65 }
66 }
67 low, high = QuickSort(low), QuickSort(high) //切割递归处理
68 myarr := append(append(low, mid...), high...)
69 return myarr
70 }
71}
72
73func main() {
74 arr := []int{3, 9, 2, 8, 1, 7, 4, 6, 5, 10}
75 fmt.Println(QuickSort2(arr))
76}
1func binarySearch( []int,search int ) int {
2 low = 0
3 height :=len(mid) - 1
4 for low <=height {
5 mid := (low+height) /2
6 middata :=n[mid]
7 if middata < search {
8 low = mid +1
9 }else if middata > search {
10 height = mid -1
11 }else{
12 return mid
13 }
14 }
15 return -1
16}