算法go!

用 go 去实现一些算法,感觉会很有用(趣)。

时间复杂度

首先我觉得先要对时间复杂度有个概念:

  • O(1)
  • O(N)
  • O(logN)
  • O(NlogN)
  • O(N^2)

algorithm

冒泡排序

快速排序

条件

给定一个数组 [8,4,2,6,5,8,9,1]
需要从小到大排序

思路

快速排序的思路就是双管齐下,左右同时开始比较。
在左右两个标注相遇后,生成子比较任务,递归执行。

先上代码:

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 main

import (
"fmt"
)

func main() {
var box []int
box = []int{5,4,3,2,1}

box = quickSort(box, 0, len(box)-1)
fmt.Println("排序后:", box)
}

func quickSort(v []int, left, right int) []int {
if left < right {
flag := v[left]
i, j := left, right

for {
for v[j] >= flag && i < j {
j--
}

for v[i] <= flag && i < j {
i++
}

if i >= j {
break
}

v[i], v[j] = v[j], v[i]
}

v[left] = v[i]
v[i] = flag

quickSort(v, left, i-1)
quickSort(v, i+1, right)
}

return v
}

我喜欢把上述过程归结为:

  1. 拿出一个比较标准
  2. 左边网右走起来
  3. 右边往左走起来
  4. 不满足标准位置了就换一换
  5. 再和标准换一换
  6. 重复1

最小堆

  1. 最小堆是一个数据结构(废话)
  2. 他是一个从小到大排序的二叉树
  3. 最小的作为根节点,且元素是相对有序的

为什么会说到最小堆呢?其实最小堆实现了基本的时间队列。
也就是我们常说的定时器。

其实最小堆排序能够达到 O(Nlog2N)的原因是他在插入元素的时候就依据了强约束的数据结构,也就是最小二叉树。
他让元素的下表在数学层面增加了一些排序信息。
比如,寻找父节点,至少要知道当前的元素下标,除以2就得到了父元素。

我们先看看最小堆的 go 代码:

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
package main

import (
"fmt"
"math"
)
// 最小堆结构体
// 之所以封装成一个结构体,因为 int 切片不能被引用
type MinHeap struct {
Element []int
}

// 新建一个最小堆的实例
func NewMinHeap() *MinHeap {
element := &MinHeap{ Element: []int{math.MinInt64}}
return element
}

// 插入新元素
func (m *MinHeap) Insert(v int) {
// 将新插入的元素放在最后一个
m.Element = append(m.Element, v)
// 统计出数组的长度
k := len(m.Element) - 1
// 因为是最小二叉树的结构,所以循环对半递减
for ; m.Element[k/2] > v ; k /= 2 {
m.Element[k], m.Element[k/2] = m.Element[k/2], m.Element[k]
// 对交换的元素进行排序
m.Sort(k)
}
// 对最后一个元素进行排序
m.Sort(len(m.Element) - 1)
}

// 向前排序
// 专业术语似乎是上浮
func (m *MinHeap) Sort(k int) {
for ; m.Element[k] < m.Element[k-1]; k -- {
m.Element[k], m.Element[k-1] = m.Element[k-1], m.Element[k]
}
}

func main() {
m := NewMinHeap()
sample := []int{5,2,6,7,8,9,2,3,3,5,1,9,43,12}
n := len(sample)

for i := 0; i < n; i++ {
m.Insert(sample[i])
}

fmt.Println(m)
}

巧妙利用最小二叉树,使得循环次数最大数减半递减。

有趣的判重

需求:
给出了一组无需随机数组,可能存在重复,要求找出第一个重复的数字。