• 150455

    文章

  • 1095

    评论

  • 13

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

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


缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉;宫崎修一) 本系列笔记拟采用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 < last;i++ {
		hit := false
		
		for j := last;j > 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)


695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

0条评论

Loading...


发表评论

电子邮件地址不会被公开。 必填项已用*标注

自定义皮肤 主体内容背景
打开支付宝扫码付款购买视频教程
遇到问题联系客服QQ:419400980
注册梁钟霖个人博客