归并排序

排序分 内部排序 + 外部排序 两种, 区分在于数据量, 内部排序可以将数据全部放到内存中, 然后进行排序
常见的内部排序算法: 冒泡, 快排, 归并排序等, 其中 快排 是速度最快的不稳定排序算法,归并排序可以应用于外部排序.
归并排序时, 可以一次归并多节点达到加速的效果。

package main

import (
    "fmt"
    "sort"
)

/*
排序分 内部排序 + 外部排序 两种, 区分在于数据量, 内部排序可以将数据全部放到内存中, 然后进行排序
常见的内部排序算法: 冒泡, 快排, 归并排序等, 其中 快排 是速度最快的不稳定排序算法,归并排序可以应用于外部排序.
归并排序时, 可以一次归并多节点达到加速的效果
*/

func main() {
    //内部排序（快排）
    a := []int{8, 7, 2, 3, 0, 4, 1, 9}
    sort.Ints(a)
    fmt.Println(a)

    //time.Sleep(5 * time.Second)

    //外部排序 -> 归并排序
    c := Merge(inMemSort(arraySource(3, 6, 2, 1, 9, 10, 8)), inMemSort(arraySource(7, 4, 0, 3, 2, 8, 13)))
    for v := range c {
        fmt.Printf("%4v",v)
    }

}

func inMemSort(in <-chan int) <-chan int {
    out := make(chan int)
    go func() {
        //读入内存中
        a := []int{}
        for v := range in {
            a = append(a, v)
        }
        //sort
        sort.Ints(a)
        //output
        for _, v := range a {
            out <- v
        }
        close(out)
    }()
    return out
}
func arraySource(a ...int) <-chan int { //指定从 channel 获取数据
    out := make(chan int)
    go func() {
        for _, v := range a {
            out <- v
        }
        close(out) //数据传递完毕，关闭channel
    }()
    return out

}

func Merge(in1, in2 <-chan int) <-chan int {
    out := make(chan int)
    go func() {
        // 归并的过程中要处理某个通道中可能没有数据的情况
        v1, ok1 := <-in1
        v2, ok2 := <-in2
        for ok1 || ok2 {
            //fmt.Printf("v1 %s,v2 %s",v1,v2)
            if !ok2 || (ok1 && v1 <= v2) {
                out <- v1
                v1, ok1 = <-in1
            } else {
                out <- v2
                v2, ok2 = <-in2
            }
        }
        close(out)
    }()
    return out
}

/*
输出结果为：
[0 1 2 3 4 7 8 9]
   0   1   2   2   3   3   4   6   7   8   8   9  10  13
*/