go语言几种算法（二）
7、Shell Sort(希尔排序)
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
slice := generateSlice(20)
fmt.Println("\n--- Unsorted --- \n\n", slice)
shellsort(slice)
fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
slice := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}
func shellsort(items []int) {
var (
n = len(items)
gaps = []int{1}
k = 1
)
for {
gap := element(2, k) + 1
if gap > n-1 {
break
}
gaps = append([]int{gap}, gaps...)
k++
}
for _, gap := range gaps {
for i := gap; i < n; i += gap {
j := i
for j > 0 {
if items[j-gap] > items[j] {
items[j-gap], items[j] = items[j], items[j-gap]
}
j = j - gap
}
}
}
}
func element(a, b int) int {
e := 1
for b > 0 {
if b&1 != 0 {
e *= a
}
b >>= 1
a *= a
}
return e
}
8、Insertion Sort(插入排序)
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
slice := generateSlice(20)
fmt.Println("\n--- Unsorted --- \n\n", slice)
insertionsort(slice)
fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
slice := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}
func insertionsort(items []int) {
var n = len(items)
for i := 1; i < n; i++ {
j := i
for j > 0 {
if items[j-1] > items[j] {
items[j-1], items[j] = items[j], items[j-1]
}
j = j - 1
}
}
}
9、Comb Sort(梳排序)
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
slice := generateSlice(20)
fmt.Println("\n--- Unsorted --- \n\n", slice)
combsort(slice)
fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
slice := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}
func combsort(items []int) {
var (
n = len(items)
gap = len(items)
shrink = 1.3
swapped = true
)
for swapped {
swapped = false
gap = int(float64(gap) / shrink)
if gap < 1 {
gap = 1
}
for i := 0; i+gap < n; i++ {
if items[i] > items[i+gap] {
items[i+gap], items[i] = items[i], items[i+gap]
swapped = true
}
}
}
}
10、Merge Sort(合并排序)
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
slice := generateSlice(20)
fmt.Println("\n--- Unsorted --- \n\n", slice)
fmt.Println("\n--- Sorted ---\n\n", mergeSort(slice), "\n")
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
slice := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}
func mergeSort(items []int) []int {
var num = len(items)
if num == 1 {
return items
}
middle := int(num / 2)
var (
left = make([]int, middle)
right = make([]int, num-middle)
)
for i := 0; i < num; i++ {
if i < middle {
left[i] = items[i]
} else {
right[i-middle] = items[i]
}
}
return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) (result []int) {
result = make([]int, len(left) + len(right))
i := 0
for len(left) > 0 && len(right) > 0 {
if left[0] < right[0] {
result[i] = left[0]
left = left[1:]
} else {
result[i] = right[0]
right = right[1:]
}
i++
}
for j := 0; j < len(left); j++ {
result[i] = left[j]
i++
}
for j := 0; j < len(right); j++ {
result[i] = right[j]
i++
}
return
}
11、Binary Tree(二叉树)
package main
import (
"fmt"
"os"
"io"
)
type BinaryNode struct {
left *BinaryNode
right *BinaryNode
data int64
}
type BinaryTree struct {
root *BinaryNode
}
func (t *BinaryTree) insert(data int64) *BinaryTree {
if t.root == nil {
t.root = &BinaryNode{data: data, left: nil, right: nil}
} else {
t.root.insert(data)
}
return t
}
func (n *BinaryNode) insert(data int64) {
if n == nil {
return
} else if data <= n.data {
if n.left == nil {
n.left = &BinaryNode{data: data, left: nil, right: nil}
} else {
n.left.insert(data)
}
} else {
if n.right == nil {
n.right = &BinaryNode{data: data, left: nil, right: nil}
} else {
n.right.insert(data)
}
}
}
func print(w io.Writer, node *BinaryNode, ns int, ch rune) {
if node == nil {
return
}
for i := 0; i < ns; i++ {
fmt.Fprint(w, " ")
}
fmt.Fprintf(w, "%c:%v\n", ch, node.data)
print(w, node.left, ns+2, 'L')
print(w, node.right, ns+2, 'R')
}
func main() {
tree := &BinaryTree{}
tree.insert(100).
insert(-20).
insert(-50).
insert(-15).
insert(-60).
insert(50).
insert(60).
insert(55).
insert(85).
insert(15).
insert(5).
insert(-10)
print(os.Stdout, tree.root, 0, 'M')
}
12、Linked List(链表)
package main
import "fmt"
type Node struct {
prev *Node
next *Node
key interface{}
}
type List struct {
head *Node
tail *Node
}
func (L *List) Insert(key interface{}) {
list := &Node{
next: L.head,
key: key,
}
if L.head != nil {
L.head.prev = list
}
L.head = list
l := L.head
for l.next != nil {
l = l.next
}
L.tail = l
}
func (l *List) Display() {
list := l.head
for list != nil {
fmt.Printf("%+v ->", list.key)
list = list.next
}
fmt.Println()
}
func Display(list *Node) {
for list != nil {
fmt.Printf("%v ->", list.key)
list = list.next
}
fmt.Println()
}
func ShowBackwards(list *Node) {
for list != nil {
fmt.Printf("%v <-", list.key)
list = list.prev
}
fmt.Println()
}
func (l *List) Reverse() {
curr := l.head
var prev *Node
l.tail = l.head
for curr != nil {
next := curr.next
curr.next = prev
prev = curr
curr = next
}
l.head = prev
Display(l.head)
}
func main() {
link := List{}
link.Insert(5)
link.Insert(9)
link.Insert(13)
link.Insert(22)
link.Insert(28)
link.Insert(36)
fmt.Println("\n==============================\n")
fmt.Printf("Head: %v\n", link.head.key)
fmt.Printf("Tail: %v\n", link.tail.key)
link.Display()
fmt.Println("\n==============================\n")
fmt.Printf("head: %v\n", link.head.key)
fmt.Printf("tail: %v\n", link.tail.key)
link.Reverse()
fmt.Println("\n==============================\n")
}
发表评论：