缘起

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

归并排序

  1. 归并排序算法会把序列分成长度相同的两个子序列，
  2. 当无法继续往下分时（也就是每个子序列中只有一个数据时），
  3. 就对子序列进行归并。
  5. 归并指的是把两个排好序的子序列合并成一个有序序列。
  6. 该操作会一直重复执行，直到所有子序列都归并为一个整体为止。
  8. 总的运行时间为O(nlogn)，这与前面讲到的堆排序相同。
  10. 摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一

流程

  1. 给定待排序数组data[N]
  2. 创建缓冲区buffer[N]
  3. 设定初始的归并步长(已排序的子序列长度), span=1, 也就是将每个元素视作已排序的一个子序列
  4. 根据当前步长, 将所有已排序的子序列两两合并到缓冲区
    1. 设定q1为子序列1的头部下标, q2为子序列2的头部下标, p指向缓冲区的对应区域
    2. 比较q1与q2位置的值大小
    3. 如果q1的值小, 则取q1的值, 放入p, 然后q1和p都加1
    4. 如果q2的值小, 则取q2的值, 放入p, 然后q2和p都加1
    5. 如果子序列已经取完, 则复制尚未取完的子序列到p
  5. 交换data与buffer的指针, 将data视为缓冲区, buffer视为待归并数据
  6. span = span*2
  7. 重复步骤3-6, 直到span>N

设计

  • ISorter: 定义排序器接口. 定义值比较函数以兼容任意数值类型, 通过调整比较函数实现倒序排序
  • tMergeSort: 归并排序器, 实现ISorter接口.

    单元测试

    merge_sort_test.go. 归并排序是比较快的, 因此设定测试规模为10万元素. ```go package sorting

import ( “fmt” “learning/gooop/sorting” “learning/gooop/sorting/merge_sort” “math/rand” “testing” “time” )

func Test_MergeSort(t *testing.T) { fnAssertTrue := func(b bool, msg string) { if !b { t.Fatal(msg) } }

  1. reversed := false
  2. fnCompare := func(a interface{}, b interface{}) sorting.CompareResult {
  3.     i1 := a.(int)
  4.     i2 := b.(int)
  6.     if i1 < i2 {
  7.         if reversed {
  8.             return sorting.GREATER
  9.         } else {
  10.             return sorting.LESS
  11.         }
  12.     } else if i1 == i2 {
  13.         return sorting.EQUAL
  14.     } else {
  15.         if reversed {
  16.             return sorting.LESS
  17.         } else {
  18.             return sorting.GREATER
  19.         }
  20.     }
  21. }
  23. fnTestSorter := func(sorter sorting.ISorter) {
  24.     reversed = false
  26.     // test simple array
  27.     samples := []interface{} { 2,3,1,5,4,7,6 }
  28.     samples = sorter.Sort(samples, fnCompare)
  29.     fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 2 3 4 5 6 7]",  "expecting 1,2,3,4,5,6,7")
  30.     t.Log("pass sorting [2 3 1 5 4 7 6] >> [1 2 3 4 5 6 7]")
  32.     // test 10000 items sorting
  33.     rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
  34.     for plus := 0;plus < 3;plus++ {
  35.         sampleCount := 100 * 1000 + plus
  36.         t.Logf("prepare large array with %v items", sampleCount)
  37.         samples = make([]interface{}, sampleCount)
  38.         for i := 0; i < sampleCount; i++ {
  39.             samples[i] = rnd.Intn(sampleCount * 10)
  40.         }
  42.         t.Logf("sorting large array with %v items", sampleCount)
  43.         t0 := time.Now().UnixNano()
  44.         samples = sorter.Sort(samples, fnCompare)
  45.         cost := time.Now().UnixNano() - t0
  46.         for i := 1; i < sampleCount; i++ {
  47.             fnAssertTrue(fnCompare(samples[i-1], samples[i]) != sorting.GREATER, "expecting <=")
  48.         }
  49.         t.Logf("end sorting large array, cost = %v ms", cost/1000000)
  50.     }
  52.     // test 0-20
  53.     sampleCount := 20
  54.     t.Log("sorting 0-20")
  55.     samples = make([]interface{}, sampleCount)
  56.     for i := 0;i < sampleCount;i++ {
  57.         for {
  58.             p := rnd.Intn(sampleCount)
  59.             if samples[p] == nil {
  60.                 samples[p] = i
  61.                 break
  62.             }
  63.         }
  64.     }
  65.     t.Logf("unsort = %v", samples)
  67.     samples = sorter.Sort(samples, fnCompare)
  68.     t.Logf("sorted = %v", samples)
  69.     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")
  70.     t.Log("pass sorting 0-20")
  72.     // test special
  73.     samples = []interface{} {}
  74.     samples = sorter.Sort(samples, fnCompare)
  75.     t.Log("pass sorting []")
  77.     samples = []interface{} { 1 }
  78.     samples = sorter.Sort(samples, fnCompare)
  79.     t.Log("pass sorting [1]")
  81.     samples = []interface{} { 3,1 }
  82.     samples = sorter.Sort(samples, fnCompare)
  83.     fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 3]",  "expecting 1,3")
  84.     t.Log("pass sorting [1 3]")
  86.     reversed = true
  87.     samples = []interface{} { 2, 3,1 }
  88.     samples = sorter.Sort(samples, fnCompare)
  89.     fnAssertTrue(fmt.Sprintf("%v", samples) == "[3 2 1]",  "expecting 3,2,1")
  90.     t.Log("pass sorting [3 2 1]")
  91. }
  93. t.Log("\ntesting MergeSort")
  94. fnTestSorter(merge_sort.MergeSort)

}

  2. <a name="rnGi1"></a>
  3. # 测试输出
  5. - 归并排序相当的快, 比堆排序还快1倍左右
  6. - 比冒泡,选择,插入等有指数级的提升, 符合理论分析
  7. - 代价与堆排序一致, 需要额外分配大小为N的空间, 用做归并缓冲区
  8. - 比堆排序快的主要原因, 推测是因为堆排序初始化时, 批量push操作, 可能引发多次数组扩容.

$ go test -v merge_sort_test.go === RUN Test_MergeSort merge_sort_test.go:111: testing MergeSort merge_sort_test.go:48: pass sorting [2 3 1 5 4 7 6] >> [1 2 3 4 5 6 7] merge_sort_test.go:54: prepare large array with 100000 items merge_sort_test.go:60: sorting large array with 100000 items merge_sort_test.go:67: end sorting large array, cost = 35 ms merge_sort_test.go:54: prepare large array with 100001 items merge_sort_test.go:60: sorting large array with 100001 items merge_sort_test.go:67: end sorting large array, cost = 36 ms merge_sort_test.go:54: prepare large array with 100002 items merge_sort_test.go:60: sorting large array with 100002 items merge_sort_test.go:67: end sorting large array, cost = 33 ms merge_sort_test.go:72: sorting 0-20 merge_sort_test.go:83: unsort = [6 10 8 9 14 1 12 4 19 7 11 16 15 17 0 2 18 3 5 13] merge_sort_test.go:86: sorted = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19] merge_sort_test.go:88: pass sorting 0-20 merge_sort_test.go:93: pass sorting [] merge_sort_test.go:97: pass sorting [1] merge_sort_test.go:102: pass sorting [1 3] merge_sort_test.go:108: pass sorting [3 2 1] —- PASS: Test_MergeSort (0.12s) PASS ok command-line-arguments 0.127s

  2. <a name="o3aWp"></a>
  3. # ISorter.go
  4. 定义排序器接口. 定义值比较函数以兼容任意数值类型, 通过调整比较函数实现倒序排序
  5. ```go
  6. package sorting
  8. type ISorter interface {
  9.     Sort(data []interface{}, comparator CompareFunction) []interface{}
  10. }
  12. type CompareFunction func(a interface{}, b interface{}) CompareResult
  14. type CompareResult int
  15. const LESS CompareResult = -1
  16. const EQUAL CompareResult = 0
  17. const GREATER CompareResult = 1

tMergeSort.go

归并排序器, 实现ISorter接口.

  1. package merge_sort
  3. import (
  4.     "learning/gooop/sorting"
  5. )
  7. type tMergeSort struct {}
  9. func newMergeSort() sorting.ISorter {
  10.     return &tMergeSort{}
  11. }
  13. func (me *tMergeSort) Sort(data []interface{}, comparator sorting.CompareFunction) []interface{} {
  14.     if data == nil {
  15.         return nil
  16.     }
  18.     size := len(data)
  19.     if size <= 1 {
  20.         return data
  21.     }
  23.     var result []interface{} = nil
  24.     buffer := make([]interface{}, size)
  25.     for span := 1; span <= size;span *= 2 {
  26.         for i := 0;i < size;i += span * 2 {
  27.             merge(size, data, i, i + span, span, buffer, i, comparator)
  28.         }
  30.         result = buffer
  31.         data, buffer = buffer, data
  32.     }
  34.     if result == nil {
  35.         result = data
  36.     }
  38.     return result
  39. }
  41. // 合并data数组中的两个子序列: [q1:q1+span), [q2:q2+span), 到目标数组result的offset位置
  42. func merge(size int, data []interface{}, q1 int, q2 int, span int, result []interface{}, offset int, comparator sorting.CompareFunction) {
  43.     e1 := min(q1 + span, size)
  44.     e2 := min(q2 + span, size)
  45.     j := -1
  46.     k := -1
  48.     for i := 0;i < span*2;i++ {
  49.         if q1 >= e1 {
  50.             j = q2
  51.             k = e2
  53.         } else if q2 >= e2 {
  54.             j = q1
  55.             k = e1
  56.         }
  58.         if j >= 0 {
  59.             for p := j;p < k;p++ {
  60.                 result[offset] = data[p]
  61.                 offset++
  62.             }
  63.             break
  64.         }
  66.         v1 := data[q1]
  67.         v2 := data[q2]
  69.         if lessEqual(v1, v2, comparator) {
  70.             result[offset] = v1
  71.             q1++
  72.         } else {
  73.             result[offset] = v2
  74.             q2++
  75.         }
  76.         offset++
  77.     }
  78. }
  80. func lessEqual(v1 interface{}, v2 interface{}, comparator sorting.CompareFunction) bool {
  81.     return comparator(v1, v2) != sorting.GREATER
  82. }
  84. func min(a,b int) int {
  85.     if a <= b {
  86.         return a
  87.     } else {
  88.         return b
  89.     }
  90. }
  92. var MergeSort = newMergeSort()

(end)