go练习:数据结构与算法实践篇

原作者: [db:作者] 来自: [db:来源] 收藏邀请

练习：使用go语言实现冒泡排序和归并排序

冒泡排序是所有排序算法中最简单的，练习时先实现它：

func bubbleSort(array []int) {
    n := len(array)
    for j := 0; j < n; j++ {
        for i := 0; i < n-1-j; i++ {
            fmt.Println(i, j, n, array[i], array[i+1])
            if array[i] > array[i+1] {
                array[i], array[i+1] = array[i+1], array[i]
            }
        }
    }
}

等语法熟悉之后，可以实现更复杂的算法练习，比如归并排序：

func mergeSort(array []int64) []int64 {
    n := len(array)
    if n <= 1 {
        return array
    }
    num := n / 2
    left := mergeSort(array[:num])
    right := mergeSort(array[num:])
    return merge(left, right)
}
func merge(left, right []int64) (result []int64) {
    size, i, j := len(left)+len(right), 0, 0
    slice := make([]int64, size, size)

    for k := 0; k < size; k++ {
        if i > len(left)-1 && j <= len(right)-1 {
            slice[k] = right[j]
            j++
        } else if j > len(right)-1 && i <= len(left)-1 {
            slice[k] = left[i]
            i++
        } else if left[i] < right[j] {
            slice[k] = left[i]
            i++
        } else {
            slice[k] = right[j]
            j++
        }
    }
    return slice
}

测试代码

package main

import "fmt"

func main() {
    src := []int{6, 202, 100, 301, 38, 8, 1}
    for _, e := range src {
        fmt.Print(e, ",")
    }
    fmt.Println()
    for _, e := range mergeSort(src) {
        fmt.Print(e, ",")
    }
    fmt.Println()
}