go-常见排序算法
目录
快排
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
li:=[]int{1,3,5,2,4,6,9,7}
left:=0
right:=len(li)-1
fmt.Println(quick_sort(li,left,right))
}
func quick_sort(li []int, left,right int) []int {
if left<right{
mid := paitition(li,left,right)
quick_sort(li,left,mid-1)
quick_sort(li,mid+1,right)
}
return li
}
func paitition(li []int, left,right int) int {
r := rand.New(rand.NewSource(time.Now().UnixNano()))
res := r.Intn(right-left+1)+left
li[left],li[res] = li[res],li[left]
temp:=li[left]
for left<right {
for left<right && li[right]>=temp{
right-=1
}
li[left]=li[right]
for left<right && li[left]<=temp{
left+=1
}
li[right]=li[left]
}
li[left]=temp
return left
}
冒泡
package main
import "fmt"
func main() {
li:=[]int{1,3,5,2,4,6,9,7}
fmt.Println(bubble_sort(li))
}
func bubble_sort(li[]int) []int {
for i:=0;i<len(li)-1;i++ {
res:=true
for j:=0;j<len(li)-1-i;j++{
if li[j]>li[j+1]{
li[j],li[j+1]=li[j+1],li[j]
res=false
}
}
if res{
return li
}
}
return nil
}
选择排序
package main
import "fmt"
func main() {
li:=[]int{1,3,5,2,4,6,9,7}
fmt.Println(select_sort(li))
}
func select_sort(li[]int) []int {
for i:=0;i<len(li);i++ {
min_loc := i
for j:=i+1;j<len(li);j++ {
if li[j]<li[min_loc] {
min_loc=j
}
}
if min_loc!=i {
li[i],li[min_loc]=li[min_loc],li[i]
}
}
return li
}
插入排序
package main
import "fmt"
func main() {
li:=[]int{1,3,201,5,2,100,4,6,9,7,2}
fmt.Println(insert_sort(li))
}
func insert_sort(li[]int) []int {
for i:=1;i<len(li); i++{
tmp:=li[i]
j := i-1
for j>0 && li[j]>tmp {
li[j+1]=li[j]
j=j-1
}
li[j+1] = tmp
}
return li
}
希尔排序
package main
import "fmt"
func main() {
li:=[]int{1,3,201,5,2,100,4,6,9,7,2}
fmt.Println(shell_sort(li))
}
func shell_sort(li[]int) []int {
res := len(li)/2
for res>0 {
for i:=res;i<len(li);i++{
tmp := li[i]
j := i-res
for j>=0 && tmp <li[j]{
li[j+res] = li[j]
j -= res
}
li[j+res] = tmp
}
res /=2 //res = res/2
}
return li
}
二分法查找
package main
import "fmt"
func main() {
li:=[]int{1,2,3,4,5,6,7,8}
left:=0
right:=len(li)-1
value := 8
fmt.Println(bin_search(li,value,left,right))
}
func bin_search(li[]int,value,left,right int) int {
if left <=right{
mid := (left+right)/2
if li[mid] == value{
return mid
} else if li[mid]>value {
return bin_search(li,value,left,mid-1)
} else {
return bin_search(li,value,mid+1,right)
}
} else {
return 999
}
}