斐波那契堆之Go实现

ACM

一个比二叉堆更高效的数据结构,但是实现起来非常复杂。本科的时候看《算法导论》的时候曾经研究过,不是很明白。今天终于对它有了一个比较清晰的了解。
enter description here

Basic Algorithms in Go

ACM

最近学Go,感觉挺不错的。闲来无事用它写了几种常用的基础算法。

快排

思想很简单,实现起来为了方便每次以left作为基准,也可以使用BFS来节省递归栈:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// QuickSort returns a sorted slice
func QuickSort(arr []int) {
if len(arr) <= 1 {
return
}
left, right := 0, len(arr)-1
for left < right {
if arr[left+1] > arr[left] {
arr[left+1], arr[right] = arr[right], arr[left+1]
right--
} else {
arr[left+1], arr[left] = arr[left], arr[left+1]
left++
}
}
QuickSort(arr[:left])
QuickSort(arr[left+1:])
}