1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func bubbleSort(list []int) []int {
	len := len(list)

	for i := 0; i < len; i++ {
		flag := false
		for j := 0; j < len-i-1; j++ {
			if list[j+1] < list[j] {
				list[j+1], list[j] = list[j], list[j+1]
				flag = true
			}
		}
		if !flag {
			break
		}
	}
	return list
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func insterSort(list []int) []int {
	len := len(list)
	for i := 1; i < len; i++ {
		tmp := list[i] //把当前要排序的变量临时拿出来，就像整理扑克的时候把要整理的牌抽出来
		j := i - 1
		for ; j >= 0; j-- {
			if list[j] > tmp {
				list[j+1] = list[j] //如果牌比手上的牌大，就像后挪一位
			} else {
				break
			}
		}
		list[j+1] = tmp
	}
	return list
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func shellSort(list []int) []int {

	len := len(list)
	group := len / 2
	for group > 0 {
		for i := group; i < len; i += group {
			tmp := list[i]
			j := i - group
			for ; j >= 0; j -= group {
				if list[j] > tmp {
					list[j+group] = list[j]
				} else {
					break
				}
			}
			list[j+group] = tmp
		}
		group /= 2
	}
	return list
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func selectSort(list []int) []int {
	len := len(list)

	for i := 0; i < len-1; i++ {
		min := list[i]
		minIdx := i
		for j := i + 1; j < len; j++ {
			if list[j] < min {
				min = list[j]
				minIdx = j
			}
		}
		list[i], list[minIdx] = list[minIdx], list[i]
	}
	return list
}

 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

var tmp []int

func mergeSort(list []int) []int {
	tmp = make([]int, len(list)) //先申请一个，这样后面就不用重复申请
	sort(list, 0, len(list)-1)
	return list
}

func merge(list []int, lo int, mid int, hi int) {
	i := lo      //左半部分的起点
	j := mid + 1 //右半部分的起点

	for k := lo; k <= hi; k++ {
		tmp[k] = list[k]
	}

	for k := lo; k <= hi; k++ {
		if i > mid {
			list[k] = tmp[j]
			j++
		} else if j > hi {
			list[k] = tmp[i]
			i++
		} else if tmp[j] < tmp[i] {
			list[k] = tmp[j]
			j++
		} else {
			list[k] = tmp[i]
			i++
		}
	}
}
func sort(list []int, lo int, hi int) {
	if hi <= lo {
		return
	}
	mid := lo + (hi-lo)/2
	sort(list, lo, mid)
	sort(list, mid+1, hi)
	merge(list, lo, mid, hi)
}

 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

package sorts

func QuickSort(list []int) []int {
	size := len(list)
	qsort(list, 0, size-1)
	return list

}

func partition(list []int, lo int, hi int) int {
	left := lo       //左扫描指针
	right := hi      //右扫描指针
	flag := list[lo] //作为切分的元素)
	for {
		for list[left] <= flag {
			left++
			if left == hi {
				break
			}

		}
		for list[right] >= flag {
			right--
			if right == lo {
				break
			}
		}
		if left >= right {
			break
		}
		list[left], list[right] = list[right], list[left]
	}
	list[lo], list[right] = list[right], list[lo] //将切分元素放入，此时 left >= right, right指针靠左，所以 list[right] 交换
	return right
}

func qsort(list []int, lo int, hi int) {
	if hi <= lo {
		return
	}
	j := partition(list, lo, hi)
	qsort(list, lo, j)   //递归切分左半部分
	qsort(list, j+1, hi) //递归切分右半部分
}

 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

package sorts

// 桶排序
import s "sort"

// 获取待排序数组中的最大值
func getMax(a []int) int {
	max := a[0]
	for i := 1; i < len(a); i++ {
		if a[i] > max {
			max = a[i]
		}
	}
	return max
}

func bucketSort(a []int) {
	num := len(a)
	if num <= 1 {
		return
	}
	max := getMax(a)
	buckets := make([][]int, num) // 二维切片

	index := 0
	for i := 0; i < num; i++ {
		index = a[i] * (num - 1) / max                // 桶序号
		buckets[index] = append(buckets[index], a[i]) // 加入对应的桶中
	}

	tmpPos := 0 // 标记数组位置
	for i := 0; i < num; i++ {
		bucketLen := len(buckets[i])
		if bucketLen > 0 {
			s.Ints(buckets[i]) // 桶内做排序,这里使用go内建排序包，快排+堆排+希尔结合
			copy(a[tmpPos:], buckets[i])
			tmpPos += bucketLen
		}
	}
}

 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
53
54
55

package sorts

import (
	s "sort"
	"sync"
)

var wg sync.WaitGroup

//PROCESS 逻辑处理器数，下面会用到
const PROCESS int = 8

func bucketSort(a []int) {
	size := len(a)
	if size <= 1 {
		return
	}

	//找到最大值
	max := a[0]
	for _, v := range a {
		if v > max {
			max = v
		}
	}

	buckets := make([][]int, PROCESS) //创建桶

	idx := 0
	// 将元素添加到对应的桶中
	for _, v := range a {
		idx = v * (PROCESS - 1) / max
		buckets[idx] = append(buckets[idx], v)
	}
	for _, bucket := range buckets {
		if bucket == nil {
			continue
		}
		wg.Add(1)
		go func(bucket []int) {
			defer wg.Done()
			s.Ints(bucket)
			return
		}(bucket)
	}
	//等待所有的排序完成
	wg.Wait()
	copyIdx := 0
	for _, bucket := range buckets {
		len := len(bucket)
		copy(a[copyIdx:], bucket)
		copyIdx = copyIdx + len
	}
	return
}

 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

package sorts

func countSort(a []int) []int {
	size := len(a)
	if size <= 1 {
		return a
	}
	//获得一个数组的最大值，函数在桶排序内容中
	max := getMax(a)
	//申请一个数组C用来做计数数组
	c := make([]int, max+1)

	//计算每个数出现的次数
	for _, v := range a {
		c[v]++
	}
	// 求 i 项 前i项和
	for i := 1; i <= max; i++ {
		c[i] = c[i] + c[i-1]
	}

	r := make([]int, size)

	for i := 0; i < size; i++ {
		idx := c[a[i]] - 1
		r[idx] = a[i]
		c[a[i]]--
	}
	return r
}

  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
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
	n := data.Len()
	quickSort(data, 0, n, maxDepth(n))
}

// maxDepth returns a threshold at which quicksort should switch
// to heapsort. It returns 2*ceil(lg(n+1)).
func maxDepth(n int) int {
	var depth int
	for i := n; i > 0; i >>= 1 {
		depth++
	}
	return depth * 2
}

func quickSort(data Interface, a, b, maxDepth int) {
	for b-a > 12 { // Use ShellSort for slices <= 12 elements
		if maxDepth == 0 {
			heapSort(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivot(data, a, b)
		// Avoiding recursion on the larger subproblem guarantees
		// a stack depth of at most lg(b-a).
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)， 相当于quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo) 相当于 quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		// Do ShellSort pass with gap 6
		// It could be written in this simplified form cause b-a <= 12
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		insertionSort(data, a, b)
	}
}

func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
	m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
	if hi-lo > 40 {
		// Tukey's ``Ninther,'' median of three medians of three.
		s := (hi - lo) / 8
		medianOfThree(data, lo, lo+s, lo+2*s)
		medianOfThree(data, m, m-s, m+s)
		medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
	}
	medianOfThree(data, lo, m, hi-1)

	// Invariants are:
	//	data[lo] = pivot (set up by ChoosePivot)
	//	data[lo < i < a] < pivot
	//	data[a <= i < b] <= pivot
	//	data[b <= i < c] unexamined
	//	data[c <= i < hi-1] > pivot
	//	data[hi-1] >= pivot
	pivot := lo
	a, c := lo+1, hi-1

	for ; a < c && data.Less(a, pivot); a++ {
	}
	b := a
	for {
		for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
		}
		for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
		}
		if b >= c {
			break
		}
		// data[b] > pivot; data[c-1] <= pivot
		data.Swap(b, c-1)
		b++
		c--
	}
	// If hi-c<3 then there are duplicates (by property of median of nine).
	// Let's be a bit more conservative, and set border to 5.
	protect := hi-c < 5
	if !protect && hi-c < (hi-lo)/4 {
		// Lets test some points for equality to pivot
		dups := 0
		if !data.Less(pivot, hi-1) { // data[hi-1] = pivot
			data.Swap(c, hi-1)
			c++
			dups++
		}
		if !data.Less(b-1, pivot) { // data[b-1] = pivot
			b--
			dups++
		}
		// m-lo = (hi-lo)/2 > 6
		// b-lo > (hi-lo)*3/4-1 > 8
		// ==> m < b ==> data[m] <= pivot
		if !data.Less(m, pivot) { // data[m] = pivot
			data.Swap(m, b-1)
			b--
			dups++
		}
		// if at least 2 points are equal to pivot, assume skewed distribution
		protect = dups > 1
	}
	if protect {
		// Protect against a lot of duplicates
		// Add invariant:
		//	data[a <= i < b] unexamined
		//	data[b <= i < c] = pivot
		for {
			for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
			}
			for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
			}
			if a >= b {
				break
			}
			// data[a] == pivot; data[b-1] < pivot
			data.Swap(a, b-1)
			a++
			b--
		}
	}
	// Swap pivot into middle
	data.Swap(pivot, b-1)
	return b - 1, c
}

  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
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

package redblacktree

const (
	// RED is true
	RED = true
	// BLACK is false
	BLACK = false
)

//Node 定义为红黑树的节点
type Node struct {
	Key   int
	Value interface{}
	Color bool
	Left  *Node
	Right *Node
	N     int
}

//RedBlackTree 定义一棵红黑树
type RedBlackTree struct {
	root   *Node
	length int
}

func isRed(n *Node) bool {
	return n != nil && n.Color
}

// InitRBTree 初始化一个红黑树
func InitRBTree() *RedBlackTree {
	return &RedBlackTree{}
}

func initNode(k int, v interface{}, size int, color bool) *Node {
	return &Node{
		Key:   k,
		Value: v,
		N:     size,
		Color: color,
	}
}

// Size 用于计算子树大小
func (t *RedBlackTree) Size(node *Node) int {
	if node == nil {
		return 0
	}
	return node.N
}

func (t *RedBlackTree) rotateLeft(node *Node) *Node {
	x := node.Right
	node.Right = x.Left
	x.Left = node
	x.Color = node.Color
	node.Color = RED
	x.N = node.N
	node.N = 1 + t.Size(node.Left) + t.Size(node.Right)
	return x

}

func (t *RedBlackTree) rotateRight(node *Node) *Node {
	x := node.Left
	node.Left = x.Right
	x.Right = node
	x.Color = node.Color
	node.Color = RED
	x.N = node.N
	node.N = 1 + t.Size(node.Left) + t.Size(node.Right)
	return x
}

// 颜色翻转,将两个红叶子节点变成黑色,再将自己变成红色
func (t *RedBlackTree) colorFlip(node *Node) {
	node.Color = RED
	node.Left.Color = BLACK
	node.Right.Color = BLACK
	return
}

// Put 向红黑树中插入函数
func (t *RedBlackTree) Put(key int, value interface{}) {
	t.root = t.put(t.root, key, value)
	// 红黑树根节点总是为黑色
	t.root.Color = BLACK
}

// put 用的递归辅助方法
func (t *RedBlackTree) put(node *Node, key int, value interface{}) *Node {
	if node == nil {
		return initNode(key, value, 1, RED)
	}
	cmp := key - node.Key
	switch {
	case cmp > 0:
		node.Right = t.put(node.Right, key, value)
	case cmp < 0:
		node.Left = t.put(node.Left, key, value)
	case cmp == 0:
		node.Value = value
	}

	//对树进行平衡操作
	// 右红 左不红 ,左旋
	if isRed(node.Right) && !isRed(node.Left) {
		node = t.rotateLeft(node)
	}
	if isRed(node.Left) && isRed(node.Left.Left) {
		node = t.rotateRight(node)
	}
	if isRed(node.Left) && isRed(node.Right) {
		t.colorFlip(node)
	}
	node.N = 1 + t.Size(node.Left) + t.Size(node.Right)
	return node
}

 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
53
54

package unnionfind

// UF 并查集数据结构
type UF struct {
	elements []int

	//给并查集加权用的
	//将小树挂在大树上以降低数的高度
	size []int
}

//IsContained 判断pq 两个元素是否联通
func (u *UF) IsContained(p, q int) bool {
	//如果这两个节点的根节点是相同的就表示是联通的
	return u.root(p) == u.root(q)
}

// Union 函数用来联通两个节点
func (u *UF) Union(p, q int) {
	pRoot := u.root(p)
	qRoot := u.root(q)
	if pRoot == qRoot {
		return
	}

	if u.size[pRoot] < u.size[qRoot] {
		//如果 p 的树比 q 的树小,那么就把 p接在q上
		u.elements[pRoot] = qRoot
		u.size[qRoot] += u.size[pRoot]
	} else {
		u.elements[qRoot] = pRoot
		u.size[pRoot] = u.size[qRoot]
	}
	return

}

func (u *UF) root(num int) int {
	//这样的写法每次只能 回溯 一层
	// for num != u.elements[num] {
	// 	num = u.elements[num]
	// }
	// 路径压缩
	// 将路径上的每个节点都指向他的祖父节点
	for num != u.elements[num] {
		// u.elements[num] 表示num的父节点
		// 如果 num 的父节点 不是num
		// 就将 num 的父节点设成 num 当前父节点的父节点 -- 祖父节点
		u.elements[num] = u.elements[u.elements[num]]
		// 进入num 的 父节点继续寻找
		num = u.elements[num]
	}
	return num
}