Jade's Fantastic Blog

package stack

// 基于数组的栈实现
type ArrayStack struct {
	data []string
	length int
	size int
}

func NewArrayStack(len int) *ArrayStack{
	if len <0 {
		return nil
	}

	return &ArrayStack{
		data: make([]string, len),
		length: len,
		size: 0,
	}
}

func (me *ArrayStack) push(data string) bool {
	if me.length == me.size {
		return false
	}

	me.data = append(me.data, data)

	me.size++

	return true
}

func (me *ArrayStack) pop() string{
	if me.size == 0 {
		return ""
	}

	item := me.data[me.size - 1]

	me.size--

	return item

}

// 基于链表的栈实现
type node struct {
	 next *node
	 val interface{}
}

type LinkedListStack struct {
	top *node
}

func NewLinkedListStack() *LinkedListStack {
	return &LinkedListStack{nil}
}

func (me LinkedListStack) IsEmpty() bool {
	return me.top == nil
}

func (me *LinkedListStack) Push(data interface{}) bool {
	nd := &node{val: data, next: nil}

	if me.IsEmpty() {
		me.top = nd
	} else {
		nd.next = me.top
		me.top = nd.next
	}

	return true
}

func (me *LinkedListStack) Pop() interface{} {
	if me.IsEmpty() {
		return nil
	}

	result := me.top.val
	me.top = me.top.next

	return result
}

func (me *LinkedListStack) Top() interface{} {
	if me.IsEmpty() {
		return nil
	}

	return me.top.val
}

func (me *LinkedListStack) Print() {
	if me.IsEmpty() {
		return
	} else {
		curr := me.top

		for nil != curr {
			fmt.Println(curr.val)
			curr = curr.next
		}
	}

}

package sort

func ShellSort(arr []int, len int) {
	if len <=1 {
		return
	}

	times := 0

	gap := len / 2

	for gap >=1 {
		j := 0

		for i:=gap; i<len; i++ {
			curr := arr[i]

		//	对第i个元素以及之前相同的gap间距元素进行对比排序
		   for j = i - gap; j>=0 && curr < arr[j]; j -= gap {

			   times++
			   arr[j+gap] = arr[j]
		   }

		   arr[j + gap] = curr
		}

		gap /= 2
	}

	println("time O(", times, ")")
}

package sort

import "math"

func CountingSort(a []int, n int) {
	if n <= 1 {
		return
	}

	var times = 0

	var max int = math.MinInt32
	for i := range a {
		if a[i] > max {
			max = a[i]
		}
		times++
	}

	c := make([]int, max+1)
	for i := range a {
		c[a[i]]++
		times++
	}
	for i := 1; i <= max; i++ {
		c[i] += c[i-1]
		times++
	}

	r := make([]int, n)
	for i := range a {
		index := c[a[i]] - 1
		r[index] = a[i]
		c[a[i]]--
		times++
	}

	copy(a, r)

	println("Time O(", times, ")")
}

package sort

// 基数排序
func RadixSort(arr []int, len int) {
	if len<=1 {
		return
	}

	max := arr[0]

	for i:=0; i< len; i++ {
		if arr[i] > max {
			max = arr[i]
		}
	}

	for exp:=1; max/exp > 0; exp *= 10 {
		countSort(arr, exp, len)
	}
}


func countSort(arr []int, exp int, len int) {

	c := make([]int, 10, 10)

	for i := range arr {
		c[arr[i]/exp % 10]++
	}

	for i := 1; i < cap(c); i++ {
		c[i] += c[i-1]
	}

	r := make([]int, len, len)

	for i := 0; i<len; i++ {
		r[c[arr[i]/exp %10] -1] = arr[i]
		c[arr[i]/exp %10]--
	}

	copy(arr, r)
}

package sort

func getMax(arr []int) int {
	max := 0

	for i := range arr {
		if i > max {
			max = i
		}
	}

	return max
}

func BucketSort(arr []int, arrLen int) {
	if arrLen <= 1 {
		return
	}

	max := getMax(arr)
	buckets := make([][]int, arrLen / 10) // seperate to length/10 buckets

	for i := 0; i < arrLen; i++ {
		index := arr[i] * ( arrLen - 1 ) / (10 * max) // sperate data to different bucket

		buckets[index] = append(buckets[index], arr[i])
	}

	datalen := 0 // mark current data processed

	for j := 0; j < len(buckets); j++ {
		bucLen := len(buckets[j])

		if bucLen > 0 {
			// use quicksort to sort every bucket
			QuickSort(buckets[j], bucLen)

			copy(arr[datalen:], buckets[j])

			datalen += bucLen
		}
	}
}

// TBD

package sort

// 插入排序
// v1: time O(n * n) space O(n)
func InsertSortArray1 (array []int, length int) []int {
	// 1. 创建一个新的数组
	// 2. 循环旧的数组数据并复制到插入到新数组的指定位置
	if length <= 1 {
		return array
	}

	times := 0

	newArray := make([]int, length, length)

	newArray[0] = array[0]

	for i := 1; i < length; i++ {
		index := 0

		for j := i-1; j >=0 ; j-- {

			times++

			if array[i] >= newArray[j] {
				index = j + 1

				break
			}

		}

		if index < i {
			for k:=i-1; k>=index; k-- {
				times++

				newArray[k + 1] = newArray[k]
			}
		}

		newArray[index] = array[i]
	}

	println("time O(", times, ")")

	return newArray
}

// v2 time o(n * n) space O(0)
func InsertSortArray2 ( array []int, len int) []int {
	// 原地交换数据
	if len <= 1 {
		return array
	}

	times := 0

	for i := 1; i< len; i++ {
		curr := array[i]
		j := i-1

		for ; j>=0; j-- {
			times++

			if array[j] > curr {
				array[j+1] = array[j]
			} else {
				break
			}
		}

		array[j+1] = curr
	}

	println("time O(", times, ")")

	return array
}

package sort

func SelectionSort1(arr []int, len int) {
	if len <=1 {
		return
	}

	times := 0

	for i:=0; i< len; i++ {
		minIndex := i

		for j:= i+1; j < len; j++ {

			times++

			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}

		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}

	println(times)
}

package sort

func BubleSort(arr []int, len int) {
	if len <=1 {
		return
	}

	flag := false

	times := 0

	for i :=0; i< len; i++ {
		for j :=0; j< len-i-1; j++ {

			times++

			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]

				flag = true
			}
		}

		if !flag {
			break
		}
	}

	println("time:", times)
}```


### 快速排序
> 首先选择一个pivot, 一般选最后一个元素， 然后便利数据从start和end， 如果小于pivot， 那么交换正在比较的两个数据， 第一次对比完成后，pivot所在的索引左边都是小于pivot的数据，右侧都是大于pivot的数据， 然后分别对左侧和右侧数据进行排序， 直到start>=end. 时间复杂度O(logN)


```go
package sort

/*
排序过程：

j=0, 1, i=0 1
1      111 23 31 43  54 45
> i=1

j=1 111, i=1 1111
1      111    23 31 43  54 45

j=2 23, i=1 111
1      23    111 31 43  54 45
> i=2 111

j = 3   31
1      23   31 111 43  54 45
> i = 3 111

j = 4, 43
1      23   31 43 111  54 45
> i = 4 111

j = 5, 54
1      23   31 43 111  54 45
> i=4 111

1      23   31 43 45  54 111
> i =4, j =5

*/
func QuickSort(arr []int, len int) {
	separate(arr, 0, len-1)

	println("time O(", times, ")")
}

func separate(arr []int, start,end int) {
	if start >= end {
		return
	}

	i := partition(start, end, arr)

	separate(arr, start, i-1)
	separate(arr, i+1, end)
}

var times int = 0

func partition(start int, end int, arr []int) int {
	pivot := arr[end]

	i := start

	for j :=start; j< end; j++ {
		times++

		if arr[j] < pivot {
			if i != j {
				arr[i], arr[j] = arr[j], arr[i]
			}

			i++
		}
	}

	arr[i], arr[end] = arr[end], arr[i]

	return i
}

package sort

var exetimes int = 0

func MergeSort(arr []int, len int) {
	if len <=1 {
		return
	}

	sort(arr, 0, len-1)

	println("tims O(", exetimes, ")")
}

func sort(arr []int, start, end int) {
	if start >=end {
		return
	}

	mid := (start + end) /2

	sort(arr, start, mid)
	sort(arr, mid+1, end)
	merge(arr, start, mid, end)
}

func merge(arr []int, start, mid, end int) {
	temp := make([]int, end - start + 1)

	i := start
	j :=mid+1
	k := 0

	for ; i<=mid && j<= end; k++ {
		exetimes++

		if arr[i] > arr[j] {
			temp[k] = arr[j]
			j++
		} else {
			temp[k] = arr[i]
			i++
		}
	}

	for ;i<=mid;i++ {
		exetimes++

		temp[k] = arr[i]
		k++
	}

	for ;j<=end;j++ {
		exetimes++
		temp[k] = arr[j]
		k++
	}

	copy(arr[start:end+1], temp)
}

package linkedlist

import (
	"fmt"
	"github.com/pkg/errors"
)

type Node struct {
	next *Node
	data interface{}
}

type LinkedList struct {
	head *Node
	length uint
}

func NewNode(value interface{}) *Node {
	return &Node{nil, value}
}

func NewLinkedList() *LinkedList{
	return &LinkedList{NewNode(0), 0}
}

func (self *Node) GetNext(node *Node) *Node {
	if nil == node {
		return nil
	}

	return node.next
}

func (self *Node) GetValue(node *Node) interface{} {
	if nil == node {
		return nil
	}

	return node.data
}

// insert new node after specific node
func (self *LinkedList) InsertBefore(node *Node, v interface{}) error {
	if nil == node {
		return errors.New("Try to insert before a empty node")
	}

	newNode := NewNode(v)
	curr := self.head.next
	pre := self.head

	for nil != curr {
		if curr == node {
			break
		}

		pre = curr
		curr = curr.next
	}

	if nil == curr {
		return errors.New("Can not find node to insert")
	}

	pre.next = newNode
	newNode.next = curr

	self.length++

	return nil
}

func (self *LinkedList) InsertAfter(node *Node, v interface{}) error {
	if nil == node {
		return errors.New("Try to insert after a empty node")
	}

	curr := self.head

	for nil != curr {
		if curr == node {
			break
		}

		curr = curr.next
	}

	if curr == nil {
		return errors.New("Can not find node to insert")
	}

	newNode := NewNode(v)
	nextNode := curr.next
	curr.next = newNode
	newNode.next = nextNode

	self.length++

	return nil
}

func (self *LinkedList) Prepend(v interface{}) error {
	return self.InsertAfter(self.head, v)
}

func (self *LinkedList) Append(v interface{}) error {
	newNode := NewNode(v)

	head := self.head

	if nil == head.next {

		head.next = newNode

	} else {

		curr := head

		for nil != curr.next {
			curr = curr.next
		}

		curr.next = newNode
	}

	self.length++

	return nil
}


// find
func (self *LinkedList) FindByIndex(index uint) (*Node, error) {

	if index > self.length {
		return nil, errors.New("Find out of range")
	}

	curr := self.head

	for i := uint(0); i< index; i++ {
		curr = curr.next
	}

	return curr, nil
}

func (self *LinkedList) FindByData(data interface{}) (*Node, error) {
	curr := self.head

	for nil != curr {
		curr = curr.next
	}

	return curr, nil
}

func (self *LinkedList) DelNode(node *Node) (bool, error) {
	if nil == node {
		return false, errors.New("Try to delete empty node")
	}

	curr := self.head

	for nil != curr {

		if(curr.next == node) {
			curr.next = curr.next.next

			return true, nil
		}

		curr = curr.next
	}

	return false, nil
}

func (self *LinkedList) Print() {
	curr := self.head

	var formatStr string

	for nil != curr.next {
		curr = curr.next

		formatStr += fmt.Sprintf("|%+v", curr.data)
	}

	fmt.Println(formatStr)
}

package array

import (
	"errors"
	"fmt"
)

type Array struct {
	data []int
	length int
}

func NewArray(capcity int) *Array {
	if capcity <= 0 {
		return nil
	}

	return &Array{
		data: make([]int, capcity, capcity),
		length: 0,
	}
}

func (self *Array) IsOutOfRange(index int) bool {
	if index < 0  || index >= cap(self.data) {
		return true
	}

	return false
}

func (self *Array) Len() int {
	return self.length
}

// find specfic data index value
func (self *Array) FindIndexByData(data int) int {
	for index, value := range self.data {
		if value == data {
			return index
		}
	}

	return -1
}

func (self *Array) FindDataByIndex(index int) (int, error) {
	if self.IsOutOfRange(index) {
		return -1, errors.New("Out of range when find")
	}

	return self.data[index], nil
}

// Delete elements  by sepecific value
func (self *Array) Delete(index int) (int, error) {
	if self.IsOutOfRange(index) {
		return -1, errors.New("Out of range when delete!")
	}

	v := self.data[index]

	for i:=index; i< self.Len() - 1; i++ {
		self.data[i] = self.data[i] + 1
	}

	self.length--

	return v, nil
}

func (self *Array) Insert(index int, data int) (bool, error) {
	if self.IsOutOfRange(index) {
		return false, errors.New("Out of range when insert")
	}

	if self.Len() == cap(self.data) {
		return false, errors.New("Capcity is full when insert")
	}

	for i := self.length-1; i >= index ; i-- {
		fmt.Println("Insert: ", self.data, i, index)

		self.data[i] = self.data[i-1]
	}

	self.data[index] = data

	self.length++

	return true, nil
}

func (self *Array) Append(data int) (bool, error) {

	if self.Len() == cap(self.data) {
		return false, errors.New("Capcity is full when insert")
	}

	return self.Insert(self.length, data)
}

func (self *Array) Prepend(data int) (bool, error) {
	if self.Len() == cap(self.data) {
		return false, errors.New("Capcity is full when insert")
	}

	return self.Insert(0, data)
}

func (self *Array) Print() {
	var formatString string
	for i :=0; i < self.length; i++ {
		formatString += fmt.Sprintf("|%+v", self.data[i])
	}

	fmt.Println(formatString)
}