常用排序算法
/**
* 冒泡排序
*/
func Bubble_sort(arr []int){
len := len(arr)
for i:=0;i<len-1;i++{
for j:=0;j < len - 1 - i;j++{
if arr[j] < arr[j+1]{
temp := arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
}
}
/**
* 选择排序
*/
func Select_sort(arr []int) {
len := len(arr)
for i:=0;i<len-1;i++{
for j:= i+1;j<len;j++{
if arr[i] > arr[j]{
temp := arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
}
}
/**
* 插入排序
*/
func Insert_sort(arr []int) {
len := len(arr)
for i:=0;i<len;i++{
for j:=i; j>0;j-- {
if arr[j] < arr[j-1] {
temp := arr[j]
arr[j] = arr[j-1]
arr[j-1] = temp
}
}
}
}
/**
* 快速排序分区
*/
func partition(arr []int ,low,high int) int{
pivot := arr[low]
for low < high{
for low<high && arr[high] > pivot {
high--
}
if low < high {
arr[low] = arr[high]
low++
}
for low < high && arr[high] <= pivot {
low++
}
if low < high {
arr[high] = arr[low]
high--
}
}
arr[low] = pivot
return low
}
/**
* 快速排序
*/
func Quick_sort(arr []int,low,high int){
loc := 0
if(low <= high){
loc = partition(arr,low,high)
Quick_sort(arr,low,loc-1)
Quick_sort(arr,loc+1,high)
}
}
/**
* 求m的n次方
*/
func Pow(m, n int) int {
num := 1
for i := 1; i <= n; i++ {
num *= m
}
return num
}
/**
* 序列求和 -1,1,-1,1,-1,1,...,(-1)n
*/
func Sum_1(n int) int {
sum := 0
for i := 1; i <= n; i++ {
p := Pow(-1, i)
sum += p
}
return sum
}
/**
* 序列求和 -1,1,-1,1,-1,1,...,(-1)n
*/
func Sum_2(n int) int {
if n%2 == 0 {
return 0
} else {
return -1
}
}
/**
* 斐波那契数列 算法1， 1，1，2，3，5，8，13，21，34
*/
func Fib_1(n int) int {
if n < 1 {
return 0
} else if n == 1 || n == 2 {
return 1
} else {
return Fib_1(n-2) + Fib_1(n-1)
}
}
/**
* 斐波那契数列 算法2
*/
func Fib_2(n int) int {
if n < 1 {
return 0
}
arr := make([]int, n+1)
arr[1] = 1
arr[2] = 2
for i := 3; i <= n; i++ {
arr[i] = arr[i-1] + arr[i-2]
}
return arr[n-1]
}
/**
* 斐波那契数列 算法3
*/
func Fib_3(n int) int {
if n < 1 {
return 0
}
if n==1 || n ==2 {
return 1
}
s1 := 1
s2 := 1
for i := 3; i<= n; i++{
s2 = s2 + s1
s1 = s2 - s1
}
return s2
}
func People_count(){
x :=0
y:=0
z :=0
for x=1;x<10;x++{
y = 20-2*x
z = 30 - x - y
if (3*x + 2*y + z) == 50{
fmt.Printf("x=%d,y=%d,z=%d \n",x,y,z)
}
}
}
/**
* 二分查找算法
*/
func Binary_search(arr []int,target int) int{
len := len(arr)
if len == 1 && arr[0] == target{
return 0
}
low := 0
high := len - 1
for low <= high{
mid := (low + high) / 2
if target == arr[mid]{
return mid
}else if target < mid{
high = mid - 1
}else {
low = mid + 1
}
}
return -1
}
/**
* 求最长公共子串
*/
func SerachMaxCommString(arr1 ,arr2 []int) []int {
len1 := len(arr1)
len2 := len(arr2)
//利用二维数组记录子问题的LCS长度
opt := make([][]int,len1,len1)
for i := 0; i < len1; i++ {
opt[i] = make([]int, len2)
}
for i:=0;i<len1;i++{
for j:=0;j<len2;j++{
if arr1[i] == arr2[j] {
if i == 0 || j == 0 {
opt[i][j] = 1
}else {
opt[i][j] = opt[i-1][j-1] + 1
}
}else{
opt[i][j] = 0
}
}
}
//找出最大公共长度和坐标
max := opt[0][0]
indexi := 0
indexj := 0
for i:=0;i<len1;i++{
for j:=0;j<len2;j++{
if opt[i][j] > max {
max = opt[i][j]
indexi = i
indexj = j
}
}
}
fmt.Printf("max lcs = %v \n",max)
fmt.Printf("max lcs indexi= %v \n",indexi)
fmt.Printf("max lcs indexj = %v \n",indexj)
//取短的串返回
narr := make([]int,max)
index := 0
var shortArr []int
if len1 < len2 {
index = indexi
shortArr = arr1
}else {
index = indexj
shortArr = arr2
}
fmt.Println(index)
fmt.Println(shortArr)
for i:=0;i<max;i++{
fmt.Println(shortArr[index-max+1+i])
narr[i] = shortArr[index-max+1+i]
}
return narr
}
/**
* 不使用变量反转数组
*/
func Reversion(arr []int) []int{
if(len(arr) < 2){
return arr
}
len := len(arr)
for i:=0;i<(len/2);i++{
arr[i] = arr[i] ^ arr[len-i-1]
arr[len-i-1] = arr[i] ^ arr[len-i-1]
arr[i] = arr[i] ^ arr[len-i-1]
}
return arr
}
/**
* 查找第二大数字
*/
func FindSecMax(arr []int) int {
len := len(arr)
secMax := 0
max := arr[0]
for i:=1;i<len;i++{
if arr[i] > max {
secMax = max
max = arr[i]
}else{
secMax = arr[i]
}
}
return secMax
}
unc IpToInt(ip string) (int32, error) {
ipArr := strings.Split(ip, ".")
if len(ipArr) != 4 {
return 0, errors.New("IP is wrong")
}
ip1, err1 := strconv.Atoi(ipArr[0])
ip2, err2 := strconv.Atoi(ipArr[1])
ip3, err3 := strconv.Atoi(ipArr[2])
ip4, err4 := strconv.Atoi(ipArr[3])
if err1 != nil || err2 != nil || err3 != nil || err4 != nil {
log.Println(err1, err2, err3, err4)
return 0, errors.New("toint error")
}
ipInt := ip1<<24 + ip2<<16 + ip3<<8 + ip4
return int32(ipInt), nil
}
func IntToIp(ip int32) string {
ip1 := ip >> 24 & 0xFF
ip2 := ip >> 16 & 0xFF
ip3 := ip >> 8 & 0xFF
ip4 := ip & 0xFF
ips := fmt.Sprintf("%d.%d.%d.%d", ip1, ip2, ip3, ip4)
return ips
}
