常见排序算法

常用排序算法

/**
 * 冒泡排序
 */
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
}