Golang语言常用算法

在学习golang语言,文档看的实在是乏味,就想着把常用的算法做个实现,边写变学习,想来效果还是不错的!

1. 堆排序

package main
import "fmt"
func buildHeap(array []int, length int) {
 var i, j int;
 for i = 1; i < length; i = i + 1 {
 for j = i; j > 0 && array[j] > array[(j-1)/2]; j = (j - 1)/2 {
 array[j], array[(j-1)/2] = array[(j-1)/2], array[j] 
 }
 }
 }
func heapSort(array []int, length int) {
 array[0], array[length - 1] = array[length - 1], array[0]
 if length <= 2 {
 return
 }
 i, j:= 0, 0
 for {
 j = 2 * i + 1
 if j + 1 < length - 1 {
 if array[j] < array[j + 1] {
 j = j + 1
 }
 } else if j >= length -1 {
 break
 } 
 array[i], array[j] = array[j], array[i]
 i = j
 }
 heapSort(array, length - 1)
 }
func main() {
 primes := [6]int{3, 11, 5, 2, 13, 7}
 fmt.Println("orginal", primes)
 buildHeap(primes[:], len(primes))
 fmt.Println("Max heap", primes)
 heapSort(primes[:], len(primes))
 fmt.Println("after sorting", primes)
}
 /**
 out:
 orginal [3 11 5 2 13 7]
 Max heap [13 11 7 2 3 5]
 after sorting [2 3 5 7 11 13]
 **/

2.冒泡排序

package main
import "fmt"
func BubbleSort(vector []int) {
 fmt.Println("BubbleSort")
 fmt.Println(vector)
 for i := 0; i < len(vector); i++ {
 tag := true // 为了剪枝
 // 每一趟将最大的数冒泡
 for j := 0; j < len(vector)-i-1; j++ {
 if vector[j] > vector[j+1] { /*vector[j] < vector[j+1]*/
 temp := vector[j]
 vector[j] = vector[j+1]
 vector[j+1] = temp
 tag = false
 }
 }
 if tag {
 break //0~len(vector)-i没有发生交换说明已经有序
 }
 fmt.Println(vector)
 }
}
func main() {
 primes := [6]int{3, 11, 5, 2, 13, 7}
 fmt.Println("orginal", primes)
 BubbleSort(primes[:])
 fmt.Println("after sorting", primes)
}
 /**
 out:
 orginal [3 11 5 2 13 7]
 BubbleSort
 [3 11 5 2 13 7]
 [3 5 2 11 7 13]
 [3 2 5 7 11 13]
 [2 3 5 7 11 13]
 after sorting [2 3 5 7 11 13]
 **/

3. 插入排序

package main
import "fmt"
func InsertSort(vector []int) {
 fmt.Println("InsertSort")
 fmt.Println(vector)
 for i := 1; i < len(vector); i++ {
 // 每一趟不满足条件就选择i为哨兵保存,将哨兵插入0~i-1有序序列(0~i-1始终是有序的)
 if vector[i] < vector[i-1] { /*vector[i] > vector[i-1]*/
 temp := vector[i]
 //后移直到找到哨兵合适的位置
 j := i - 1
 for ; j >= 0 && vector[j] > temp; j-- { /*vector[j] < temp*/
 vector[j+1] = vector[j]
 }
 //插入位置前后都是有序的,最后也是有序的
 vector[j+1] = temp
 }
 fmt.Println(vector)
 }
}
func main() {
 primes := [6]int{3, 11, 5, 2, 13, 7}
 fmt.Println("orginal", primes)
 InsertSort(primes[:])
 fmt.Println("after sorting", primes)
}
/**
 out:
 orginal [3 11 5 2 13 7]
 InsertSort
 [3 11 5 2 13 7]
 [3 11 5 2 13 7]
 [3 5 11 2 13 7]
 [2 3 5 11 13 7]
 [2 3 5 11 13 7]
 [2 3 5 7 11 13]
 after sorting [2 3 5 7 11 13]
**/

4. 选择排序

package main
import "fmt"
func SelectSort(vector []int) {
 fmt.Println("SelectSort")
 fmt.Println(vector)
 for i := 0; i < len(vector); i++ {
 // 选择最小的元素
 k := i
 for j := i + 1; j < len(vector); j++ {
 if vector[k] > vector[j] {
 k = j
 }
 }
 // 交换
 if k != i {
 temp := vector[i]
 vector[i] = vector[k]
 vector[k] = temp
 }
 fmt.Println(vector)
 }
}
func main() {
 primes := [6]int{3, 11, 5, 2, 13, 7}
 fmt.Println("orginal", primes)
 SelectSort(primes[:])
 fmt.Println("after sorting", primes)
}
/**
 out:
 orginal [3 11 5 2 13 7]
 SelectSort
 [3 11 5 2 13 7]
 [2 11 5 3 13 7]
 [2 3 5 11 13 7]
 [2 3 5 11 13 7]
 [2 3 5 7 13 11]
 [2 3 5 7 11 13]
 [2 3 5 7 11 13]
 after sorting [2 3 5 7 11 13]
**/

5. 二元选择排序

package main
import "fmt"
func BinarySelectSort(vector []int) {
 fmt.Println("SelectSort")
 fmt.Println(vector)
 n := len(vector)
 for i := 0; i < n/2; i++ {
 // 选择最小的元素和最大元素
 k := i
 t := n - i - 1
 for j := i + 1; j <= n-i-1; j++ {
 if vector[k] > vector[j] {
 k = j
 }
 if vector[t] < vector[j] {
 t = j
 }
 }
 // 交换
 if k != i {
 temp := vector[i]
 vector[i] = vector[k]
 vector[k] = temp
 }
 if t != n-i-1 {
 temp := vector[n-i-1]
 vector[n-i-1] = vector[t]
 vector[t] = temp
 }
 fmt.Println(vector)
 }
}
func main() {
 primes := [6]int{3, 11, 5, 2, 13, 7}
 fmt.Println("orginal", primes)
 BinarySelectSort(primes[:])
 fmt.Println("after sorting", primes)
}
/**
 out:
 orginal [3 11 5 2 13 7]
 SelectSort
 [3 11 5 2 13 7]
 [2 11 5 3 7 13]
 [2 3 5 11 7 13]
 [2 3 5 11 7 13]
 after sorting [2 3 5 11 7 13]
**/

6. 快速排序

本文来自:简书

感谢作者:Diogoxiang

查看原文:Golang语言常用算法

• 编辑
• 预览