乐趣区

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

jiezi

缘起

最近浏览 << 我的第一本算法书 >>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳 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)

退出移动版