golang sort.Slice

frank3 · · 4905 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

sort.Slice是golang提供的切片排序方法,

  1. 其中使用到了反射(reflect)包
241 // Slice sorts the provided slice given the provided less function.
242 //
243 // The sort is not guaranteed to be stable. For a stable sort, use
244 // SliceStable.
245 //
246 // The function panics if the provided interface is not a slice.
247 func Slice(slice interface{}, less func(i, j int) bool) {
248     rv := reflect.ValueOf(slice) 
249     swap := reflect.Swapper(slice)
250     length := rv.Len()
251     quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
252 }
  1. 使用了闭包
swap := reflect.Swapper(slice)

// Swapper returns a function that swaps the elements in the provided
 10 // slice.
 11 //
 12 // Swapper panics if the provided interface is not a slice.
 13 func Swapper(slice interface{}) func(i, j int) {
 14     v := ValueOf(slice)
 15     if v.Kind() != Slice {
 16         panic(&ValueError{Method: "Swapper", Kind: v.Kind()})
 17     }
..................此处省略部分代码
 62     tmp := unsafe_New(typ) // swap scratch space
 63
 64     return func(i, j int) {
 65         if uint(i) >= uint(s.Len) || uint(j) >= uint(s.Len) {
 66             panic("reflect: slice index out of range")
 67         }
 68         val1 := arrayAt(s.Data, i, size)
 69         val2 := arrayAt(s.Data, j, size)
 70         typedmemmove(typ, tmp, val1)
 71         typedmemmove(typ, val1, val2)
 72         typedmemmove(typ, val2, tmp)
 73     }
 74 }
  1. 可以参考何时使用panic
250     length := rv.Len()

1019 // Len returns v's length.
1020 // It panics if v's Kind is not Array, Chan, Map, Slice, or String.
1021 func (v Value) Len() int {
1022     k := v.kind()
1023     switch k {
1024     case Array:
1025         tt := (*arrayType)(unsafe.Pointer(v.typ))
1026         return int(tt.len)
1027     case Chan:
1028         return chanlen(v.pointer())
1029     case Map:
1030         return maplen(v.pointer())
1031     case Slice:
1032         // Slice is bigger than a word; assume flagIndir.
1033         return (*sliceHeader)(v.ptr).Len
1034     case String:
1035         // String is bigger than a word; assume flagIndir.
1036         return (*stringHeader)(v.ptr).Len
1037     }
1038     panic(&ValueError{"reflect.Value.Len", v.kind()})
1039 }
  1. quickSort函数设计学习,同时使用了heapsort、insertionSort和单次希尔排序
135 // Auto-generated variant of sort.go:quickSort
136 func quickSort_func(data lessSwap, a, b, maxDepth int) {
137     for b-a > 12 {
138         if maxDepth == 0 {
139             heapSort_func(data, a, b)
140             return
141         }
142         maxDepth--
143         mlo, mhi := doPivot_func(data, a, b)
144         if mlo-a < b-mhi {
145             quickSort_func(data, a, mlo, maxDepth)
146             a = mhi
147         } else {
148             quickSort_func(data, mhi, b, maxDepth)
149             b = mlo
150         }
151     }
152     if b-a > 1 {
153         for i := a + 6; i < b; i++ {
154             if data.Less(i, i-6) {
155                 data.Swap(i, i-6)
156             }
157         }
158         insertionSort_func(data, a, b)
159     }
160 }
  1. 合法性处理
// Swapper returns a function that swaps the elements in the provided
 10 // slice.
 11 //
 12 // Swapper panics if the provided interface is not a slice.
 13 func Swapper(slice interface{}) func(i, j int) {
 14    ...........省略部分代码
 18     // Fast path for slices of size 0 and 1. Nothing to swap.
 19     switch v.Len() {
 20     case 0:
 21         return func(i, j int) { panic("reflect: slice index out of range") }
 22     case 1:
 23         return func(i, j int) {
 24             if i != 0 || j != 0 {
 25                 panic("reflect: slice index out of range")
 26             }
 27         }
 28     }

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:frank3

查看原文:golang sort.Slice

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

4905 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传