缘起
最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之
插入排序
插入排序是一种从序列左端开始依次对数据进行排序的算法。
在排序过程中，左侧的数据陆续归位，
而右侧留下的就是还未被排序的数据。
插入排序的思路就是从右侧的未排序区域内取出一个数据，
然后将它插入到已排序区域内合适的位置上。
时间复杂度和冒泡排序的一样，都为O(n^2)。
摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一
基本流程
- 给定待排序数组data[N]
- 如果N <= 1, 直接返回
- 视data[0]为已排序状态
- 从位置1开始, "插入"到左侧已排序区
- 类似冒泡排序, 将data[1]与其前方的数字两两比较
- 因为左侧是已排序区, 因此遇到首个更小的数字, 本轮比较即可终止, 前面的数字只会更小, 无需比较了.
- 循环4-6, 直到右侧数字全部插入左侧区域, 完成排序
改进流程(二分插入)
- 由于左侧区域是已排序区域, 因此可以使用二分查找法, 快速定位插入位置
- 给定左侧已排序的区域data[0:N]
- 现准备插入data[N+1]
- 初始状态, 设置left=0, right = N-1
- 取位置p = (left + right) / 2
- 比较data[p]与data[N+1]
- 如果data[p] == data[N+1], 则直接插入位置p
- 如果data[p]更大, 说明目标位置还在更左, 则设置right = p - 1
- 如果data[p]更小, 说明目标位置还在更右, 则设置left = p + 1
- 循环5-9步, 直到left,right收敛为同一位置
- 比较data[left]与data[N+1], 小于等于则插入left+1位置, 否则插入left位置
- 循环3-11步, 直到右侧数字全部插入左侧区域, 完成排序
目标
- 实现并验证普通插入排序, 二分插入排序, 并观察两者效率差异
- 通过定义比较函数兼容任意值类型
- 通过调整比较函数实现倒序输出
设计
- ISorter: 定义排序算法接口, 以及值比较函数
- tInsertSort: 实现插入排序, 通过参数控制, 切换插入函数, 分别实现普通插入和二分插入
单元测试
insert_sort_test.go, 测试过程与选择排序基本一致
从测试结果看, 普通插入排序比选择排序快约30%, 二分插入又比普通插入快近四倍.
package sorting
import (
"fmt"
"learning/gooop/sorting"
"learning/gooop/sorting/insert_sort"
"math/rand"
"testing"
"time"
)
func Test_InsertSort(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
}
}
}
fnTestSorter := func(sorter sorting.ISorter) {
reversed = false
// test simple array
samples := []interface{} { 2,3,1 }
sorter.Sort(samples, fnCompare)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 2 3]", "expecting 1,2,3")
t.Log("pass sorting [2 3 1] >> [1 2 3]")
// 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.Logf("sorting large array with %v items", sampleCount)
t0 := time.Now().UnixNano()
sorter.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)
sorter.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{} {}
sorter.Sort(samples, fnCompare)
t.Log("pass sorting []")
samples = []interface{} { 1 }
sorter.Sort(samples, fnCompare)
t.Log("pass sorting [1]")
samples = []interface{} { 3,1 }
sorter.Sort(samples, fnCompare)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 3]", "expecting 1,3")
t.Log("pass sorting [1 3]")
reversed = true
samples = []interface{} { 2, 3,1 }
sorter.Sort(samples, fnCompare)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[3 2 1]", "expecting 3,2,1")
t.Log("pass sorting [3 2 1]")
}
t.Log("\ntesting SimpleInsertSorter")
fnTestSorter(insert_sort.SimpleInsertSorter)
t.Log("\ntesting BinaryInsertSorter")
fnTestSorter(insert_sort.BinaryInsertSorter)
}
测试输出
$ go test -v insert_sort_test.go
=== RUN Test_InsertSort
insert_sort_test.go:109:
testing SimpleInsertSorter
insert_sort_test.go:48: pass sorting [2 3 1] >> [1 2 3]
insert_sort_test.go:53: prepare large array with 10000 items
insert_sort_test.go:59: sorting large array with 10000 items
insert_sort_test.go:66: end sorting large array, cost = 188 ms
insert_sort_test.go:70: sorting 0-20
insert_sort_test.go:81: unsort = [10 6 14 18 12 11 19 9 17 8 7 0 15 16 1 3 5 13 4 2]
insert_sort_test.go:84: sorted = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]
insert_sort_test.go:86: pass sorting 0-20
insert_sort_test.go:91: pass sorting []
insert_sort_test.go:95: pass sorting [1]
insert_sort_test.go:100: pass sorting [1 3]
insert_sort_test.go:106: pass sorting [3 2 1]
insert_sort_test.go:112:
testing BinaryInsertSorter
insert_sort_test.go:48: pass sorting [2 3 1] >> [1 2 3]
insert_sort_test.go:53: prepare large array with 10000 items
insert_sort_test.go:59: sorting large array with 10000 items
insert_sort_test.go:66: end sorting large array, cost = 46 ms
insert_sort_test.go:70: sorting 0-20
insert_sort_test.go:81: unsort = [3 19 13 17 11 4 15 10 14 5 6 0 7 2 8 16 18 12 1 9]
insert_sort_test.go:84: sorted = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]
insert_sort_test.go:86: pass sorting 0-20
insert_sort_test.go:91: pass sorting []
insert_sort_test.go:95: pass sorting [1]
insert_sort_test.go:100: pass sorting [1 3]
insert_sort_test.go:106: pass sorting [3 2 1]
--- PASS: Test_InsertSort (0.24s)
PASS
ok command-line-arguments 0.237s
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
tInsertSort.go
实现插入排序, 通过参数控制, 切换插入函数, 分别实现普通插入和二分插入
package insert_sort
import (
"learning/gooop/sorting"
)
type tInsertSort struct {
fnInsert fnInsertFunction
}
func newInsertSort(usingBinarySearch bool) sorting.ISorter {
it := &tInsertSort{
nil,
}
if usingBinarySearch {
it.fnInsert = binaryInsert
} else {
it.fnInsert = simpleInsert
}
return it
}
type fnInsertFunction func(data []interface{}, from int, to int, comparator sorting.CompareFunction)
// 插入排序
func (me *tInsertSort) Sort(data []interface{}, comparator sorting.CompareFunction) []interface{} {
if data == nil {
return nil
}
size := len(data)
if size <= 1 {
return data
}
for i := 1;i < size;i++ {
me.fnInsert(data, 0, i, comparator)
}
return data
}
// 将位于to的值插入到有序序列data的[from,to)位置
func simpleInsert(data []interface{}, from int, to int, comparator sorting.CompareFunction) {
for i := to;i>from;i-- {
prev := i - 1
if comparator(data[prev], data[i]) == sorting.GREATER {
data[prev], data[i] = data[i], data[prev]
} else {
break
}
}
}
// 将位于to的值插入到有序序列data的[from,to)位置
func binaryInsert(data []interface{}, from int, to int, comparator sorting.CompareFunction) {
p := binaryIndexOf(data, from, to - 1, data[to], comparator)
if p != to {
v := data[to]
moveArrayRange(data, p, p + 1, to - p)
data[p] = v
}
}
// 整体移动数组的指定范围
func moveArrayRange(data []interface{}, src int, dst int, size int) {
t := dst + size - 1
for i := src + size - 1;i >= src;i-- {
data[t] = data[i]
t--
}
}
// 二分查找首个>=v的下标
func binaryIndexOf(data []interface{}, from int, toInclusive int, v interface{}, comparator sorting.CompareFunction) int {
for {
if from == toInclusive {
switch comparator(data[from], v) {
case sorting.LESS:
return from + 1
default:
return from
}
} else {
p := (from + toInclusive) / 2
switch comparator(data[p], v) {
case sorting.LESS:
from = min(p + 1, toInclusive)
break
case sorting.EQUAL:
return p
case sorting.GREATER:
toInclusive = max(from, p - 1)
break
}
}
}
}
func min(a, b int) int {
if a <= b {
return a
} else {
return b
}
}
func max(a, b int) int {
if a >= b {
return a
} else {
return b
}
}
var SimpleInsertSorter = newInsertSort(false)
var BinaryInsertSorter = newInsertSort(true)
(end)
有疑问加站长微信联系（非本文作者）
