golang数据结构与算法——十大排序算法

---

一 LowB三人组

1.1 冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

示意图：

排序思想：

1. 有n个数需要被排序；假设先选取第0个位置的数字和让其和后一位的数进行比较；
2. 如果比较时发现当前数比后一个数大（即比较时，出现不符合我们规则的顺序），交换两数；
3. 然后选第1个位置的数字，继续遍历，一轮后，即可找出一个最大数；(即最后一位已经到达其应在位置)最后一个数已经不需要参与后面的比较了；
4. 继续遍历，则每轮比较后，最后一个数就会到达其应到位置；
5. 每轮能找出一个最大的数，则最多仅需n-1轮即可全部排序完成；因为其余数排序好后，最后一个数不用在找自己的位置了；（i表示外层for循环表示轮数）
6. 每轮选中的数下标为j,从0开始；
   因为选中的数和后一个比较，最后一个不用选中，所以j的上限 -1；
   又因为每过1轮，最后一个数就会被定下来，所以每轮j的上限 -i;

代码实现：

package main

import (
	"fmt"
)

func main() {
   

	//1.定义测试数组
	var intArr = [...]int{
   10, 5, 11, 9, 0} //test01

	//2.输出排序前数组；
	fmt.Println("排序前:", intArr)

	for i := 0; i < len(intArr)-1; i++ {
   

		//3.如果一轮遍历比较后，没有发生过交换，则当前每一个数都比他后面的数小，
		//即当前数组已有序；则立即可停止排序；

		//定义 is_changed ,记录每轮发生过交换；
		var is_changed bool
		for j := 0; j < len(intArr)-1-i; j++ {
   

			if intArr[j+1] < intArr[j] {
   
				//如果顺序不对，则发生交换,字段变为 true;
				is_changed = true
				//交换两数位置；
				intArr[j] = intArr[j+1] ^ intArr[j]
				intArr[j+1] = intArr[j+1] ^ intArr[j]
				intArr[j] = intArr[j+1] ^ intArr[j]
			}

		}
		fmt.Printf("经过%v轮遍历；冒泡排序后结果为：%v\n", i+1, intArr)
		//如果一整轮没交换过，则已经有序；退出排序；
		if is_changed == false {
   
			fmt.Printf("现在已经有序，直接停止；\n")
			break
		}

	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

运行结果：

[Running] go run "e:\golang开发学习\go_pro\test.go"
排序前: [10 5 11 9 0]
经过1轮遍历；冒泡排序后结果为：[5 10 9 0 11]
经过2轮遍历；冒泡排序后结果为：[5 9 0 10 11]
经过3轮遍历；冒泡排序后结果为：[5 0 9 10 11]
经过4轮遍历；冒泡排序后结果为：[0 5 9 10 11]

[Done] exited with code=0 in 2.41 seconds
1
2
3
4
5
6
7
8

1.2 选择排序

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，经过和其他元素重整，再依原则交换位置后达到排序的目的。

示意图：

排序思想：

1. 第一次从 R[0]~R[n-1]中选取最小值，与 R[0]交换，
2. 第二次从 R[1]~R[n-1]中选取最小值，与 R[1]交换，
3. 第三次从 R[2]~R[n-1]中选取最小值，与 R[2]交换，…，
4. 第 i 次从 R[i-1]~R[n-1]中选取最小值，与 R[i-1]交换，…,
5. 第 n-1 次从R[n-2]~R[n-1]中选取最小值，与 R[n-2]交换，
6. 总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。

代码实现：

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func Select_Sort(arr []int) {
   
	for i := 0; i < len(arr)-1; i++ {
   
		// 假设最小值是无序区的第一个位置
		min_loc := i
		// 自己不用跟自己比较
		for j := i + 1; j < len(arr); j++ {
   
			if arr[min_loc] > arr[j] {
   
				min_loc = j
			}
		}
		arr[min_loc], arr[i] = arr[i], arr[min_loc]
	}
}

// 生成随机int切片 正整数 rand.Intn返回一个非负伪随机数[0,n)作为int。如果n <= 0则报错
func rand_array(arr []int, min int, max int) {
   
	if min >= max || min == 0 || max == 0 {
   
		fmt.Println("输入最大, 最小值有误！")
		return
	}
	// 如果不加这个 每次会生成一样的
	rand.Seed(time.Now().Unix())
	for i := 0; i < len(arr); i++ {
   
		arr[i] = rand.Intn(max-min) + min
	}
}

func main() {
   
	min := 5
	max := 100
	var mylist []int = make([]int, 10)
	rand_array(mylist, min, max)
	fmt.Printf("随机的int 切片为:%d\n", mylist)
	Select_Sort(mylist)
	fmt.Printf("选择排序后的int 切片为:%d\n", mylist)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

运行结果：

[Running] go run "e:\golang开发学习\go_pro\test.go"
随机的int 切片为:[29 50 37 36 70 19 56 64 66 88]
选择排序后的int 切片为:[19 29 36 37 50 56 64 66 70 88]

[Done] exited with code=0 in 1.246 seconds
1
2
3
4
5

1.3 插入排序

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的

示意图：

排序思想：

1. 把 n 个待排序的元素看成为一个有序表和一个无序表，
2. 开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，
3. 排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

代码实现：

package main

import "fmt"

func Insert_Sort(arr *[7]int) {
   
	for i := 1; i < len(arr); i++ {
   

		inserVal := arr[i]
		inserIndex := i - 1 //下标

		//从大到小
		for inserIndex >= 0 && arr[inserIndex] < inserVal {
   
			arr[inserIndex+1] = arr[inserIndex] //数据后移
			inserIndex--
		}

		//插入
		if inserIndex+1 != i {
   
			arr[inserIndex+1] = inserVal
		}
		fmt.Printf("第%d此插入后: %v\n", i, *arr)
	}
}

func main() {
   
	arr := [7]int{
   23, 0, 12, 56, 34, -1, 55}
	fmt.Println("原始数组为:", arr)
	Insert_Sort(&arr)

	fmt.Println(arr)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

运行结果：

[Running] go run "e:\golang开发学习\go_pro\test.go"
原始数组为: [23 0 12 56 34 -1 55]
第1此插入后: [23 0 12 56 34 -1 55]
第2此插入后: [23 12 0 56 34 -1 55]
第3此插入后: [56 23 12 0 34 -1 55]
第4此插入后: [56 34 23 12 0 -1 55]
第5此插入后: [56 34 23 12 0 -1 55]
第6此插入后: [56 55 34 23 12 0 -1]
[56 55 34 23 12 0 -1]

[Done] exited with code=0 in 1.666 seconds
1
2
3
4
5
6
7
8
9
10
11

二 NB三人组

2.1 快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。

排序思想：

1. 通过一趟排序将要排序的数据分割成独立的两部分，
2. 其中一部分的所有数据都比另外一部分的所有数据都要小，
3. 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

示意图：

应用实例：

​ 要求：对 [-9，78，0，23，-567，70] 进行从小到大的排序

​ 说明 [ 验证分析 ]：

1. 如果取消左右递归，结果是：-9 -567 0 23 78 70
2. 如果取消右递归，结果是： -567 -9 0 23 78 70
3. 如果取消左递归，结果是：-9 -567 0 23 70 78

代码实现：

package main

import (
	"fmt"
)

//快速排序
//说明
//1. left 表示 数组左边的下标
//2. right 表示数组右边的下标
//3 array 表示要排序的数组
func QuickSort(left int, right int, array *[9]int) 
1
2
3
4
5
6
7
8
9
10
11