# 手撸golang 基本数据结构与算法 冒泡排序

## 冒泡排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，

## 目标

• 实现并验证冒泡排序算法, 通过定义比较函数兼容任意值类型, 通过调整比较函数实现倒序输出

## 设计

• ISorter: 定义排序算法接口, 以及值比较函数
• tBubbleSorter: 冒泡排序的实现. 内部是一个双重循环, 不断重复两两比较的过程, 直到无交换发生.

## 单元测试

bubble_sort_test.go

package sorting

import (
"fmt"
"learning/gooop/sorting"
"math/rand"
"testing"
"time"
)

func Test_BubbleSort(t *testing.T) {
fnAssertTrue := func(b bool, msg string) {
if !b {
t.Fatal(msg)
}
}

reversed := false
fnCompare := func(a interface{}, b interface{}) sorting.CompareResult {
i1 := a.(int)
i2 := b.(int)

if i1 < i2 {
if reversed {
return sorting.GREATER
} else {
return sorting.LESS
}
} else if i1 == i2 {
return sorting.EQUAL
} else {
if reversed {
return sorting.LESS
} else {
return sorting.GREATER
}
}
}

// test 10000 items sorting
rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
sampleCount := 10000
t.Logf("prepare large array with %v items", sampleCount)
samples := make([]interface{}, sampleCount)
for i := 0;i < sampleCount;i++ {
samples[i] = rnd.Intn(sampleCount*10)
}

t.Log("sorting large array")
t0 := time.Now().UnixNano()
sorting.BubbleSorter.Sort(samples, fnCompare)
cost := time.Now().UnixNano() - t0
for i := 1;i < sampleCount;i++ {
fnAssertTrue(fnCompare(samples[i-1], samples[i]) != sorting.GREATER, "expecting <=")
}
t.Logf("end sorting large array, cost = %v ms", cost / 1000000)

// test 0-20
sampleCount = 20
t.Log("sorting 0-20")
samples = make([]interface{}, sampleCount)
for i := 0;i < sampleCount;i++ {
for {
p := rnd.Intn(sampleCount)
if samples[p] == nil {
samples[p] = i
break
}
}
}
t.Logf("unsort = %v", samples)

sorting.BubbleSorter.Sort(samples, fnCompare)
t.Logf("sorted = %v", samples)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]", "expecting 0-20")
t.Log("pass sorting 0-20")

// test special
samples = []interface{} {}
sorting.BubbleSorter.Sort(samples, fnCompare)
t.Log("pass sorting []")

samples = []interface{} { 1 }
sorting.BubbleSorter.Sort(samples, fnCompare)
t.Log("pass sorting [1]")

samples = []interface{} { 3,1 }
sorting.BubbleSorter.Sort(samples, fnCompare)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 3]",  "expecting 1,3")
t.Log("pass sorting [1 3]")

samples = []interface{} { 2,3,1 }
sorting.BubbleSorter.Sort(samples, fnCompare)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 2 3]",  "expecting 1,2,3")
t.Log("pass sorting [1 2 3]")

reversed = true
sorting.BubbleSorter.Sort(samples, fnCompare)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[3 2 1]",  "expecting 3,2,1")
t.Log("pass sorting [3 2 1]")
}

## 测试输出

\$ go test -v bubble_sort_test.go
=== RUN   Test_BubbleSort
bubble_sort_test.go:43: prepare large array with 10000 items
bubble_sort_test.go:49: sorting large array
bubble_sort_test.go:56: end sorting large array, cost = 534 ms
bubble_sort_test.go:60: sorting 0-20
bubble_sort_test.go:71: unsort = [4 8 5 3 10 17 6 15 9 16 19 0 12 11 13 18 7 2 1 14]
bubble_sort_test.go:74: sorted = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]
bubble_sort_test.go:76: pass sorting 0-20
bubble_sort_test.go:81: pass sorting []
bubble_sort_test.go:85: pass sorting [1]
bubble_sort_test.go:90: pass sorting [1 3]
bubble_sort_test.go:95: pass sorting [1 2 3]
bubble_sort_test.go:100: pass sorting [3 2 1]
--- PASS: Test_BubbleSort (0.54s)
PASS
ok      command-line-arguments  0.538s

## ISorter.go

package sorting

type ISorter interface {
Sort(data []interface{}, comparator CompareFunction) []interface{}
}

type CompareFunction func(a interface{}, b interface{}) CompareResult

type CompareResult int
const LESS CompareResult = -1
const EQUAL CompareResult = 0
const GREATER CompareResult = 1

## tBubbleSorter.go

package sorting

type tBubbleSorter struct {
}

func newBubbleSorter() ISorter {
return &tBubbleSorter{}
}

func (me *tBubbleSorter) Sort(data []interface{}, fnCompare CompareFunction) []interface{} {
if data == nil {
return nil
}

size := len(data)
if size <= 1 {
return data
}
last := size - 1

for i := 0;i  i;j-- {
prev := j - 1
if fnCompare(data[prev], data[j]) == GREATER {
data[j], data[prev] = data[prev], data[j]
hit = true
}
}

if !hit {
// no changes
break
}
}

return data
}

var BubbleSorter = newBubbleSorter()

(end)