Go 语言实现算法之冒泡排序

冒泡排序是最基本的排序算法，它的复杂度为O(n²)。
它的实现原理非常简单，就是从头遍历数组，如果第 i 个数比第 i + 1 个数大，那么就交换他们，这样遍历第一次就会让最大的数放到数组末尾，第二遍会把第二大的数放到数组倒数第二的位置，依次类推……
冒泡排序过程图形表示如下：

那么我们可以实现最基本的冒泡排序如下：

func BubbleSort1(list []int) {
    n := len(list)
    for i := 0; i < n; i++ {
        for j := 0; j < n-1; j++ {
            if list[j] > list[j+1] {
                list[j], list[j+1] = list[j+1], list[j]
            }
        }
    }
}

BubbleSort1 的实现是最基本实现，每次遍历都是遍历所有数据，其实根据上面我们讲解冒泡的原理知道每冒泡依次我们最少会把一个大的数据更新到数组尾部，也就是说我们可以每次遍历数量少一个。改进算法如下：

func BubbleSort2(list []int) {
    n := len(list)
    for i := 0; i < n; i++ {
        for j := 0; j < n-1-i; j++ {
            if list[j] > list[j+1] {
                list[j], list[j+1] = list[j+1], list[j]
            }
        }
    }
}

BubbleSort2 做了一个小的改进，其实我们还可以进一步改进，从上面的冒泡原理我们知道，每次遍历的时候，只要该次遍历有顺序需要调整的那么这个数组就还没有完全有序，反过来如果我们该次遍历没有元素的位置需要调整，那么就表明数组内元素已经完全有序了，那么我们可以设置一个标志量来进一步改进算法。改进算法如下：

func BubbleSort3(list []int) {
    n := len(list)
    flag := true

    for flag {
        flag = false
        for j := 0; j < n-1; j++ {
            if list[j] > list[j+1] {
                list[j], list[j+1] = list[j+1], list[j]
                flag = true
            }
        }
        n = n - 1
    }
}

到这里冒泡排序基本完了，可优化的点也没了。
源码地址

单元测试

写了三个单元测试用来测试三个算法的正确性，源码地址

var list = []map[string][]int{
    {
        "origin": {10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
        "result": {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
    },
    {
        "origin": {22, 33, 22, 1, 2, 11, 22, 123, 110},
        "result": {1, 2, 11, 22, 22, 22, 33, 110, 123},
    },
    {
        "origin": {22, 23, 10, 9, 54, 17, 100, 2},
        "result": {2, 9, 10, 17, 22, 23, 54, 100},
    },
    {
        "origin": {22, 23, 22, 23, 22, 23, 22, 23},
        "result": {22, 22, 22, 22, 23, 23, 23, 23},
    },
    {
        "origin": {1, 1111, 298989, 8422, 2222, 44422},
        "result": {1, 1111, 2222, 8422, 44422, 298989},
    },
    {
        "origin": {22, 10, 1, 99, 22, 10, 11, 10, 2, 100},
        "result": {1, 2, 10, 10, 10, 11, 22, 22, 99, 100},
    },
    {
        "origin": {23, 22},
        "result": {22, 23},
    },
    {
        "origin": {1},
        "result": {1},
    },
    {
        "origin": {},
        "result": {},
    },
}

func listEqual(list1, list2 []int) bool {
    for index, _ := range list1 {
        if list1[index] != list2[index] {
            return false
        }
    }
    return true
}

func TestBubbleSort1(t *testing.T) {
    for _, item := range list {
        origin := make([]int, len(item["origin"]))
        copy(origin, item["origin"])
        BubbleSort1(origin)
        if !listEqual(origin, item["result"]) {
            t.Error("bubble sort", item["origin"], "should be", item["result"],
                "but get", origin)
        }
    }
}
func TestBubbleSort2(t *testing.T) {
    for _, item := range list {
        origin := make([]int, len(item["origin"]))
        copy(origin, item["origin"])
        BubbleSort2(origin)
        if !listEqual(origin, item["result"]) {
            t.Error("bubble sort", item["origin"], "should be", item["result"],
                "but get", origin)
        }
    }
}

func TestBubbleSort3(t *testing.T) {
    for _, item := range list {
        origin := make([]int, len(item["origin"]))
        copy(origin, item["origin"])
        BubbleSort3(origin)
        if !listEqual(origin, item["result"]) {
            t.Error("bubble sort", item["origin"], "should be", item["result"],
                "but get", origin)
        }
    }
}

运行测试

> $ go test -run=BubbleSort* -v
=== RUN   TestBubbleSort1
--- PASS: TestBubbleSort1 (0.00s)
=== RUN   TestBubbleSort2
--- PASS: TestBubbleSort2 (0.00s)
=== RUN   TestBubbleSort3
--- PASS: TestBubbleSort3 (0.00s)
PASS
ok      github.com/yushuailiu/go-algorithm/sort 0.006s

基准测试

基准测试源码

func BenchmarkBubbleSort1(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for _, item := range list {
            origin := make([]int, len(item["origin"]))
            copy(origin, item["origin"])
            BubbleSort1(origin)
            if !listEqual(origin, item["result"]) {
                b.Error("bubble sort", item["origin"], "should be", item["result"],
                    "but get", origin)
            }
        }
    }
}
func BenchmarkBubbleSort2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for _, item := range list {
            origin := make([]int, len(item["origin"]))
            copy(origin, item["origin"])
            BubbleSort2(origin)
            if !listEqual(origin, item["result"]) {
                b.Error("bubble sort", item["origin"], "should be", item["result"],
                    "but get", origin)
            }
        }
    }
}
func BenchmarkBubbleSort3(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for _, item := range list {
            origin := make([]int, len(item["origin"]))
            copy(origin, item["origin"])
            BubbleSort3(origin)
            if !listEqual(origin, item["result"]) {
                b.Error("bubble sort", item["origin"], "should be", item["result"],
                    "but get", origin)
            }
        }
    }
}

运行基准测试

> $ go test -bench=BubbleSort* -run=^1 -v
goos: darwin
goarch: amd64
pkg: github.com/yushuailiu/go-algorithm/sort
BenchmarkBubbleSort1-4       1000000          1012 ns/op
BenchmarkBubbleSort2-4       2000000           993 ns/op
BenchmarkBubbleSort3-4       2000000           883 ns/op
PASS
ok      github.com/yushuailiu/go-algorithm/sort 6.676s

可以看到 BubbleSort2 比 BubbleSort1 稍有提升，而 BubbleSort3 比 BubbleSort2 提升还是挺大的。