最近有时间, 都在看 Go, 感觉 Go 语言真的不错, 具体自行百度. 今天简单说一下算法
什么是算法
一系列的计算步骤, 用来将输入数据转化成输出结果
算法的意义
用于解决特定的问题
解决同一个问题的不同算法的效率常常相差非常大, 这种差距的影响往往比硬件和软件方面的差距还要大.
算法在我们编程开发中, 还是不可或缺的.
下面简单来列举一下 go 语言常见的十大算法. 具体如下:
- BubbleSort(冒泡排序)
- func Sort(list []int, left, right int) {
- if right == 0 {
- return
- }
- for index,num := range list {
- if index <right && num> list[index + 1] {
- utils.SwapGo(list, index, index + 1)
- }
- }
- Sort(list, left, right - 1)
- }
- BucketSort(桶排序)
- func Sort(list []int) []int{
- max := max(list)
- min := min(list)
- base := 0
- if min <0 {
- base = -min
- } else {
- base = min
- }
- max = (max + base)/10
- min = (min + base)/10
- bucket := make([][]int, max - min + 1)
- var result []int
- for _,value := range list {
- i := (int)((value+base)/10)
- bucket[i] = append(bucket[i], value)
- }
- for _,value := range bucket {
- if len(value)> 0 {
- quicksort.Sort(value, 0, len(value)-1)
- }
- }
- for _,value := range bucket {
- if len(value)> 0 {
- for _,v := range value {
- result = append(result,v)
- }
- }
- }
- return result
- }
- func max(list []int) int {
- max := list[0]
- for _,value := range list {
- if value> max {
- max = value
- }
- }
- return max
- }
- func min(list []int) int {
- min := list[0]
- for _,value := range list {
- if value <min {
- min = value
- }
- }
- return min
- }
- CountSort (计数排序)
- func Sort(list []int) []int{
- max := max(list)
- min := min(list)
- base := -min
- max = max - base
- min = min - base
- numbers := make([]int, max - min + 1)
- for _,value := range list{
- numbers[value + base] = numbers[value + base] + 1
- }
- var result []int
- for i,value := range numbers {
- for j:=value;j>0 && value> 0;j-- {
- result = append(result, i - base)
- }
- }
- return result
- }
- func max(list []int) int {
- max := list[0]
- for _,value := range list {
- if value> max {
- max = value
- }
- }
- return max
- }
- func min(list []int) int {
- min := list[0]
- for _,value := range list {
- if value <min {
- min = value
- }
- }
- return min
- }
- HeapSort(堆排序)
- func Sort(list []int) {
- length := len(list)
- for {
- if length < 1 {
- break
- }
- index := length/2 -1
- for ;index>=0;index-- {
- swap(list, index, length-1)
- }
- tmp := list[0]
- list[0] = list[length - 1]
- list[length - 1] = tmp
- length--
- }
- }
- func swap(list []int, index int, length int) {
- left := 2*index + 1
- right := 2*index + 2
- if left <= length && list[left]> list[index] {
- tmp := list[index]
- list[index] = list[left]
- list[left] = tmp
- }
- if right <= length && list[right]> list[index] {
- tmp := list[index]
- list[index] = list[right]
- list[right] = tmp
- }
- }
- InsertSort(插入排序)
- func Sort(list []int, left, right int) {
- for index := left;index <= right;index++ {
- if index> 0 {
- for i:=index;i>0;i-- {
- current := list[i]
- pre := list[i-1]
- if current <= pre {
- utils.SwapGo(list, i, i-1)
- } else {
- break
- }
- }
- }
- }
- }
- MergeSort(合并排序)
- func Sort(list []int, left, right int) []int{
- return mergeSort(list[left:right-left + 1])
- }
- func mergeSort(list []int) []int {
- if len(list) <2 {
- return list
- } else {
- return merge(mergeSort(list[:len(list)/2]), mergeSort(list[len(list)/2:]))
- }
- }
- func merge(list0, list1 []int) []int{
- var result []int
- index0 := 0
- index1 := 0
- for {
- if index0 < len(list0) && index1 < len(list1) {
- if list0[index0] < list1[index1] {
- result = append(result, list0[index0])
- index0 = index0 + 1
- } else {
- result = append(result, list1[index1])
- index1 = index1 + 1
- }
- } else {
- break
- }
- }
- if index0 < len(list0) {
- result = append(result, list0[index0:]...)
- }
- if index1 < len(list1) {
- result = append(result, list1[index1:]...)
- }
- return result
- }
- QuickSort(快速排序)
- import "github.com/go-algorithm/utils"
- func Sort(list []int, left, right int) {
- if right < left {
- return
- }
- flag := list[left]
- start := left
- end := right
- for {
- if start == end {
- break
- }
- for list[end]>= flag && end> start {
- end--
- }
- for list[start] <= flag && end> start {
- start++
- }
- if end> start {
- utils.SwapGo(list, start, end)
- }
- }
- utils.SwapGo(list, left, start)
- Sort(list, left, start - 1)
- Sort(list, start + 1, right)
- }
- RadixSort(基数排序)
- func Sort(list []int) {
- baseList := make([][]int, 10)
- maxDigist := maxDigist(list)
- for i:=0;i<maxDigist;i++ {
- for _,value := range list {
- baseList[getDigist(value, i)] = append(baseList[getDigist(value, i)], value)
- }
- j := 0
- for index,value :=range baseList {
- if len(value)> 0 {
- for _,v := range value {
- list[j] = v
- j++
- }
- }
- baseList[index] = nil
- }
- }
- }
- func maxDigist(list []int) int {
- maxDigist := 1
- for _,value := range list {
- if len(strconv.Itoa(value))> maxDigist {
- maxDigist = len(strconv.Itoa(value))
- }
- }
- return maxDigist
- }
- func getDigist(number int, index int) int {
- strNum := strconv.Itoa(number)
- if index> len(strNum) - 1 {
- return 0
- }
- index = len(strNum) - 1 - index
- //fmt.Println("index =", index)
- result,error := strconv.Atoi(string(strNum[index]))
- if error != nil {
- return -1
- } else {
- return result
- }
- }
- SelectSort(选择排序)
- import "github.com/go-algorithm/utils"
- func Sort(list []int, left, right int) {
- if left == right {
- return
- }
- minIndex := left
- for i:=left;i<=right;i++ {
- if list[i] <= list[minIndex] {
- minIndex = i
- }
- }
- utils.SwapGo(list, left, minIndex)
- Sort(list, left + 1, right)
- }
- shellsort(希尔排序)
- func Sort(list []int, left, right int) {
- increment := len(list)/3 + 1
- for {
- if increment < 1 {
- break
- }
- for i:=left;i<increment;i++ {
- for j:=i+increment;j<=right;j++ {
- if list[j] < list[j-increment] {
- tmp := list[j]
- list[j] = list[j-increment]
- list[j-increment] = tmp
- }
- }
- }
- increment--
- }
- }
附: Utils.go
- /***
- * 变量交换
- */
- func Swap(list []int, i, j int) {
- tmp := list[i]
- list[i] = list[j]
- list[j] = tmp
- }
- /***
- * go 特有变量交换
- */
- func SwapGo(list []int, i, j int) {
- list[i],list[j]=list[j],list[i]
- }
- /***
- * go 变量高阶交换 (不推荐, 一般不好理解)
- */
- func SwapGoAdvanced(list []int, i, j int) {
- list[i]=list[i]+list[j]
- list[j]=list[i]-list[j]
- list[i]=list[i]-list[j]
- }
运行排序方法
使用终端执行
go get GitHub.com/e9ab98e991ab/go-algorithm
执行 touch main.go
执行 VIM main.go
拷贝下方代码块代码到 main.go 文件中
wq 保存后直接执行 go run main.go 即可查看结果
- package main
- import (
- "fmt"
- "github.com/e9ab98e991ab/go-algorithm/bubblesort"
- "github.com/e9ab98e991ab/go-algorithm/quicksort"
- "github.com/e9ab98e991ab/go-algorithm/selectsort"
- "github.com/e9ab98e991ab/go-algorithm/insertsort"
- "github.com/e9ab98e991ab/go-algorithm/shellsort"
- "github.com/e9ab98e991ab/go-algorithm/radixsort"
- "github.com/e9ab98e991ab/go-algorithm/heapsort"
- "github.com/e9ab98e991ab/go-algorithm/bucketsort"
- "github.com/e9ab98e991ab/go-algorithm/countsort"
- "github.com/e9ab98e991ab/go-algorithm/mergesort"
- )
- var data = []int{8, 3, 6, 9, 11, 2, 7, 23, 65, 13, 9}
- func main() {
- datePrintln("桶排序")
- datePrintln("计数排序")
- datePrintln("冒泡排序")
- datePrintln("快速排序")
- datePrintln("选择排序")
- datePrintln("插入排序")
- datePrintln("希尔排序")
- datePrintln("合并排序")
- datePrintln("基数排序")
- datePrintln("堆排序")
- }
- func datePrintln(name string) {
- var result []int
- fmt.Println("初始数据:", data)
- switch name {
- case "桶排序":
- result = bucketsort.Sort(data)
- break
- case "计数排序":
- result = countsort.Sort(data)
- break
- case "合并排序":
- result = mergesort.Sort(data, 0, len(data)-1)
- break
- case "冒泡排序":
- bubblesort.Sort(data, 0, len(data)-1)
- result = data
- break
- case "快速排序":
- quicksort.Sort(data, 0, len(data)-1)
- result = data
- break
- case "选择排序":
- selectsort.Sort(data, 0, len(data)-1)
- result = data
- break
- case "插入排序":
- insertsort.Sort(data, 0, len(data)-1)
- result = data
- break
- case "希尔排序":
- shellsort.Sort(data, 0, len(data)-1)
- result = data
- break
- case "基数排序":
- radixsort.Sort(data)
- result = data
- break
- case "堆排序":
- heapsort.Sort(data)
- result = data
- break
- }
- fmt.Println(name+":", result)
- data = []int{8, 3, 6, 9, 11, 2, 7, 23, 65, 13, 9}
- fmt.Println("原始数据:", data, "\n")
- }
源码地址: GitHub
来源: http://www.jianshu.com/p/49335969cfd4