地球仪的BLOG

go语言几种算法（一）

原文链接：http://www.golangprograms.com/data-structure-and-algorithms.html

1、Linear Search(线性搜索)

package main
  
import "fmt"
 
func linearsearch(datalist []int, key int) bool {
    for _, item := range datalist {
        if item == key {
            return true
        }
    }
    return false
} 
  
func main() {
    items := []int{95,78,46,58,45,86,99,251,320}
    fmt.Println(linearsearch(items,58))
}

2、Binary Search(二进制搜索)

package main
import "fmt"
 
func binarySearch(needle int, haystack []int) bool {
 
    low := 0
    high := len(haystack) - 1
 
    for low <= high{
        median := (low + high) / 2
 
        if haystack[median] < needle {
            low = median + 1
        }else{
            high = median - 1
        }
    }
 
    if low == len(haystack) || haystack[low] != needle {
        return false
    }
 
    return true
}
 
 
func main(){
    items := []int{1,2, 9, 20, 31, 45, 63, 70, 100}
    fmt.Println(binarySearch(63, items))
}

3、Interpolation Search(插值搜索)

package main
import "fmt"
 
func interpolationSearch(array []int, key int) int {
 
    min, max := array[0], array[len(array)-1]
 
    low, high := 0, len(array)-1
 
    for {
        if key < min {
            return low
        }
 
        if key > max {
            return high + 1
        }
 
        // make a guess of the location
        var guess int
        if high == low {
            guess = high
        } else {
            size := high - low
            offset := int(float64(size-1) * (float64(key-min) / float64(max-min)))
            guess = low + offset
        }
 
        // maybe we found it?
        if array[guess] == key {
            // scan backwards for start of value range
            for guess > 0 && array[guess-1] == key {
                guess--
            }
            return guess
        }
 
        // if we guessed to high, guess lower or vice versa
        if array[guess] > key {
            high = guess - 1
            max = array[high]
        } else {
            low = guess + 1
            min = array[low]
        }
    }
}
 
 
func main(){
    items := []int{1,2, 9, 20, 31, 45, 63, 70, 100}
    fmt.Println(interpolationSearch(items,63))
}

4、Bubble Sort(冒泡排序) 

package main
 
import (
    "fmt"
    "math/rand"
    "time"
)
 
func main() {
 
    slice := generateSlice(20)
    fmt.Println("\n--- Unsorted --- \n\n", slice)
    bubblesort(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 bubblesort(items []int) {
    var (
        n = len(items)
        sorted = false
    )
    for !sorted {
        swapped := false
        for i := 0; i < n-1; i++ {
            if items[i] > items[i+1] {
                items[i+1], items[i] = items[i], items[i+1]
                swapped = true
            }
        }
        if !swapped {
            sorted = true
        }
        n = n - 1
    }
}

5、Quick Sort(快速排序)

package main
 
import (
    "fmt"
    "math/rand"
    "time"
)
 
func main() {
 
    slice := generateSlice(20)
    fmt.Println("\n--- Unsorted --- \n\n", slice)
    quicksort(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 quicksort(a []int) []int {
    if len(a) < 2 {
        return a
    }
      
    left, right := 0, len(a)-1
      
    pivot := rand.Int() % len(a)
      
    a[pivot], a[right] = a[right], a[pivot]
      
    for i, _ := range a {
        if a[i] < a[right] {
            a[left], a[i] = a[i], a[left]
            left++
        }
    }
      
    a[left], a[right] = a[right], a[left]
      
    quicksort(a[:left])
    quicksort(a[left+1:])
      
    return a
}

package main
 
import (
    "fmt"
    "math/rand"
    "time"
)
 
func main() {
 
    slice := generateSlice(20)
    fmt.Println("\n--- Unsorted --- \n\n", slice)
    selectionsort(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 selectionsort(items []int) {
    var n = len(items)
    for i := 0; i < n; i++ {
        var minIdx = i
        for j := i; j < n; j++ {
            if items[j] < items[minIdx] {
                minIdx = j
            }
        }
        items[i], items[minIdx] = items[minIdx], items[i]
    }
}