手撸golang 基本数据结构与算法 冒泡排序
2010 年 12 月 16 日
缘起
最近阅读<>(【日】石田保辉;宫崎修一)
本系列笔记拟采用golang练习之
冒泡排序
冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小, 再根据结果交换两个数字的位置”这一操作的算法。 在这个过程中,数字会像泡泡一样, 慢慢从右往左“浮”到序列的顶端, 所以这个算法才被称为“冒泡排序”。 在序列的最右边放置一个天平,比较天平两边的数字。 如果右边的数字较小,就交换这两个数字的位置。 完成后,天平往左移动一个位置,比较两个数字的大小。 不断对数字进行交换,天平最终到达了最左边。 通过这一系列操作,序列中最小的数字就会移动到最左边。 将天平移回最右边,然后重复之前的操作,直到天平到达左边第2个位置为止。 冒泡排序的时间复杂度为O(n^2)。 摘自 <> 【日】石田保辉;宫崎修一
目标
- 实现并验证冒泡排序算法, 通过定义比较函数兼容任意值类型, 通过调整比较函数实现倒序输出
设计
- 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)
有疑问加站长微信联系(非本文作者)