golang sort.Slice

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 }

2. 使用了闭包

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 }

3. 可以参考何时使用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 }

4. 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 }

5. 合法性处理

// 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     }

转载于:https://www.jianshu.com/p/851b23bffcf6