缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

插入排序

  1. 插入排序是一种从序列左端开始依次对数据进行排序的算法。
  3. 在排序过程中，左侧的数据陆续归位，
  4. 而右侧留下的就是还未被排序的数据。
  6. 插入排序的思路就是从右侧的未排序区域内取出一个数据，
  7. 然后将它插入到已排序区域内合适的位置上。
  9. 时间复杂度和冒泡排序的一样，都为O(n^2)。
  11. 摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一

基本流程

  1. 给定待排序数组data[N]
  2. 如果N <= 1, 直接返回
  3. 视data[0]为已排序状态
  4. 从位置1开始, “插入”到左侧已排序区
  5. 类似冒泡排序, 将data[1]与其前方的数字两两比较
  6. 因为左侧是已排序区, 因此遇到首个更小的数字, 本轮比较即可终止, 前面的数字只会更小, 无需比较了.
  7. 循环4-6, 直到右侧数字全部插入左侧区域, 完成排序

改进流程(二分插入)

  1. 由于左侧区域是已排序区域, 因此可以使用二分查找法, 快速定位插入位置
  2. 给定左侧已排序的区域data[0:N]
  3. 现准备插入data[N+1]
  4. 初始状态, 设置left=0, right = N-1
  5. 取位置p = (left + right) / 2
  6. 比较data[p]与data[N+1]
  7. 如果data[p] == data[N+1], 则直接插入位置p
  8. 如果data[p]更大, 说明目标位置还在更左, 则设置right = p - 1
  9. 如果data[p]更小, 说明目标位置还在更右, 则设置left = p + 1
  10. 循环5-9步, 直到left,right收敛为同一位置
  11. 比较data[left]与data[N+1], 小于等于则插入left+1位置, 否则插入left位置
  12. 循环3-11步, 直到右侧数字全部插入左侧区域, 完成排序

目标

  • 实现并验证普通插入排序, 二分插入排序, 并观察两者效率差异
  • 通过定义比较函数兼容任意值类型
  • 通过调整比较函数实现倒序输出

设计

  • ISorter: 定义排序算法接口, 以及值比较函数
  • tInsertSort: 实现插入排序, 通过参数控制, 切换插入函数, 分别实现普通插入和二分插入

单元测试

insert_sort_test.go, 测试过程与选择排序基本一致
从测试结果看, 普通插入排序比选择排序快约30%, 二分插入又比普通插入快近四倍.

  1. package sorting
  3. import (
  4.     "fmt"
  5.     "learning/gooop/sorting"
  6.     "learning/gooop/sorting/insert_sort"
  7.     "math/rand"
  8.     "testing"
  9.     "time"
  10. )
  12. func Test_InsertSort(t *testing.T) {
  13.     fnAssertTrue := func(b bool, msg string) {
  14.         if !b {
  15.             t.Fatal(msg)
  16.         }
  17.     }
  19.     reversed := false
  20.     fnCompare := func(a interface{}, b interface{}) sorting.CompareResult {
  21.         i1 := a.(int)
  22.         i2 := b.(int)
  24.         if i1 < i2 {
  25.             if reversed {
  26.                 return sorting.GREATER
  27.             } else {
  28.                 return sorting.LESS
  29.             }
  30.         } else if i1 == i2 {
  31.             return sorting.EQUAL
  32.         } else {
  33.             if reversed {
  34.                 return sorting.LESS
  35.             } else {
  36.                 return sorting.GREATER
  37.             }
  38.         }
  39.     }
  41.     fnTestSorter := func(sorter sorting.ISorter) {
  42.         reversed = false
  44.         // test simple array
  45.         samples := []interface{} { 2,3,1 }
  46.         sorter.Sort(samples, fnCompare)
  47.         fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 2 3]",  "expecting 1,2,3")
  48.         t.Log("pass sorting [2 3 1] >> [1 2 3]")
  50.         // test 10000 items sorting
  51.         rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
  52.         sampleCount := 10000
  53.         t.Logf("prepare large array with %v items", sampleCount)
  54.         samples = make([]interface{}, sampleCount)
  55.         for i := 0;i < sampleCount;i++ {
  56.             samples[i] = rnd.Intn(sampleCount*10)
  57.         }
  59.         t.Logf("sorting large array with %v items", sampleCount)
  60.         t0 := time.Now().UnixNano()
  61.         sorter.Sort(samples, fnCompare)
  62.         cost := time.Now().UnixNano() - t0
  63.         for i := 1;i < sampleCount;i++ {
  64.             fnAssertTrue(fnCompare(samples[i-1], samples[i]) != sorting.GREATER, "expecting <=")
  65.         }
  66.         t.Logf("end sorting large array, cost = %v ms", cost / 1000000)
  68.         // test 0-20
  69.         sampleCount = 20
  70.         t.Log("sorting 0-20")
  71.         samples = make([]interface{}, sampleCount)
  72.         for i := 0;i < sampleCount;i++ {
  73.             for {
  74.                 p := rnd.Intn(sampleCount)
  75.                 if samples[p] == nil {
  76.                     samples[p] = i
  77.                     break
  78.                 }
  79.             }
  80.         }
  81.         t.Logf("unsort = %v", samples)
  83.         sorter.Sort(samples, fnCompare)
  84.         t.Logf("sorted = %v", samples)
  85.         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")
  86.         t.Log("pass sorting 0-20")
  88.         // test special
  89.         samples = []interface{} {}
  90.         sorter.Sort(samples, fnCompare)
  91.         t.Log("pass sorting []")
  93.         samples = []interface{} { 1 }
  94.         sorter.Sort(samples, fnCompare)
  95.         t.Log("pass sorting [1]")
  97.         samples = []interface{} { 3,1 }
  98.         sorter.Sort(samples, fnCompare)
  99.         fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 3]",  "expecting 1,3")
  100.         t.Log("pass sorting [1 3]")
  102.         reversed = true
  103.         samples = []interface{} { 2, 3,1 }
  104.         sorter.Sort(samples, fnCompare)
  105.         fnAssertTrue(fmt.Sprintf("%v", samples) == "[3 2 1]",  "expecting 3,2,1")
  106.         t.Log("pass sorting [3 2 1]")
  107.     }
  109.     t.Log("\ntesting SimpleInsertSorter")
  110.     fnTestSorter(insert_sort.SimpleInsertSorter)
  112.     t.Log("\ntesting BinaryInsertSorter")
  113.     fnTestSorter(insert_sort.BinaryInsertSorter)
  114. }

测试输出

  1. $ go test -v insert_sort_test.go 
  2. === RUN   Test_InsertSort
  3.     insert_sort_test.go:109: 
  4.         testing SimpleInsertSorter
  5.     insert_sort_test.go:48: pass sorting [2 3 1] >> [1 2 3]
  6.     insert_sort_test.go:53: prepare large array with 10000 items
  7.     insert_sort_test.go:59: sorting large array with 10000 items
  8.     insert_sort_test.go:66: end sorting large array, cost = 188 ms
  9.     insert_sort_test.go:70: sorting 0-20
  10.     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]
  11.     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]
  12.     insert_sort_test.go:86: pass sorting 0-20
  13.     insert_sort_test.go:91: pass sorting []
  14.     insert_sort_test.go:95: pass sorting [1]
  15.     insert_sort_test.go:100: pass sorting [1 3]
  16.     insert_sort_test.go:106: pass sorting [3 2 1]
  17.     insert_sort_test.go:112: 
  18.         testing BinaryInsertSorter
  19.     insert_sort_test.go:48: pass sorting [2 3 1] >> [1 2 3]
  20.     insert_sort_test.go:53: prepare large array with 10000 items
  21.     insert_sort_test.go:59: sorting large array with 10000 items
  22.     insert_sort_test.go:66: end sorting large array, cost = 46 ms
  23.     insert_sort_test.go:70: sorting 0-20
  24.     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]
  25.     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]
  26.     insert_sort_test.go:86: pass sorting 0-20
  27.     insert_sort_test.go:91: pass sorting []
  28.     insert_sort_test.go:95: pass sorting [1]
  29.     insert_sort_test.go:100: pass sorting [1 3]
  30.     insert_sort_test.go:106: pass sorting [3 2 1]
  31. --- PASS: Test_InsertSort (0.24s)
  32. PASS
  33. ok      command-line-arguments  0.237s

ISorter.go

定义排序算法接口, 以及值比较函数

  1. package sorting
  3. type ISorter interface {
  4.     Sort(data []interface{}, comparator CompareFunction) []interface{}
  5. }
  7. type CompareFunction func(a interface{}, b interface{}) CompareResult
  9. type CompareResult int
  10. const LESS CompareResult = -1
  11. const EQUAL CompareResult = 0
  12. const GREATER CompareResult = 1

tInsertSort.go

实现插入排序, 通过参数控制, 切换插入函数, 分别实现普通插入和二分插入

  1. package insert_sort
  3. import (
  4.     "learning/gooop/sorting"
  5. )
  7. type tInsertSort struct {
  8.     fnInsert fnInsertFunction
  9. }
  11. func newInsertSort(usingBinarySearch bool) sorting.ISorter {
  12.     it := &tInsertSort{
  13.         nil,
  14.     }
  15.     if usingBinarySearch {
  16.         it.fnInsert = binaryInsert
  17.     } else {
  18.         it.fnInsert = simpleInsert
  19.     }
  20.     return it
  21. }
  23. type fnInsertFunction func(data []interface{}, from int, to int, comparator sorting.CompareFunction)
  25. // 插入排序
  26. func (me *tInsertSort) Sort(data []interface{}, comparator sorting.CompareFunction) []interface{} {
  27.     if data == nil {
  28.         return nil
  29.     }
  31.     size := len(data)
  32.     if size <= 1 {
  33.         return data
  34.     }
  36.     for i := 1;i < size;i++ {
  37.         me.fnInsert(data, 0, i, comparator)
  38.     }
  40.     return data
  41. }
  43. // 将位于to的值插入到有序序列data的[from,to)位置
  44. func simpleInsert(data []interface{}, from int, to int, comparator sorting.CompareFunction) {
  45.     for i := to;i>from;i-- {
  46.         prev := i - 1
  47.         if comparator(data[prev], data[i]) == sorting.GREATER {
  48.             data[prev], data[i] = data[i], data[prev]
  49.         } else {
  50.             break
  51.         }
  52.     }
  53. }
  55. // 将位于to的值插入到有序序列data的[from,to)位置
  56. func binaryInsert(data []interface{}, from int, to int, comparator sorting.CompareFunction) {
  57.     p := binaryIndexOf(data, from, to - 1, data[to], comparator)
  58.     if p != to {
  59.         v := data[to]
  60.         moveArrayRange(data, p, p + 1, to - p)
  61.         data[p] = v
  62.     }
  63. }
  65. // 整体移动数组的指定范围
  66. func moveArrayRange(data []interface{}, src int, dst int, size int) {
  67.     t := dst + size - 1
  68.     for i := src + size - 1;i >= src;i-- {
  69.         data[t] = data[i]
  70.         t--
  71.     }
  72. }
  74. // 二分查找首个>=v的下标
  75. func binaryIndexOf(data []interface{}, from int, toInclusive int, v interface{}, comparator sorting.CompareFunction) int {
  76.     for {
  77.         if from == toInclusive {
  78.             switch comparator(data[from], v) {
  79.             case sorting.LESS:
  80.                 return from + 1
  82.             default:
  83.                 return from
  84.             }
  86.         } else {
  87.             p := (from + toInclusive) / 2
  88.             switch comparator(data[p], v) {
  89.             case sorting.LESS:
  90.                 from = min(p + 1, toInclusive)
  91.                 break
  93.             case sorting.EQUAL:
  94.                 return p
  96.             case sorting.GREATER:
  97.                 toInclusive = max(from, p - 1)
  98.                 break
  99.             }
  100.         }
  101.     }
  102. }
  104. func min(a, b int) int {
  105.     if a <= b {
  106.         return a
  107.     } else {
  108.         return b
  109.     }
  110. }
  112. func max(a, b int) int {
  113.     if a >= b {
  114.         return a
  115.     } else {
  116.         return b
  117.     }
  118. }
  120. var SimpleInsertSorter = newInsertSort(false)
  121. var BinaryInsertSorter = newInsertSort(true)

(end)