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
	}
}