在学习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]
**/
网友评论