自定义排序的三种方法
重写sort方法
- 要重写srot方法需要实现sort方法的三个接口，Len，Less，Swap
- 其中Len方法返回数组长度，Less实现排序规则，Swap实现交换
- 代码如下
type vis struct { a int weight int } type byWeight []vis func getKth(lo int, hi int, k int) int { arr := byWeight{} for lo <= hi { arr = append(arr, vis{lo, getWeight(lo)}) lo++ } sort.Sort(arr) return arr[k-1].a } func (b byWeight) Len() int { return len(b) } func (b byWeight) Less(i, j int) bool { if b[i].weight == b[j].weight { return b[i].a < b[j].a } return b[i].weight < b[j].weight } func (b byWeight) Swap(i, j int) { b[i], b[j] = b[j], b[i] } func getWeight(a int) int { num := 0 for a != 1 { if a%2 == 0 { a /= 2 } else { a = a*3 + 1 } num++ } return num }
sort.Slice方法
- Slice方法相当于自动实现了Len和Swap方法，只需要自定义排序规则就行
type vis1 struct { a int weight int } type byWeight1 []vis1 func getKth1(lo int, hi int, k int) int { arr := byWeight1{} for lo <= hi { arr = append(arr, vis1{lo, getWeight1(lo)}) lo++ } sort.Slice(arr, func(i, j int) bool { if arr[i].weight == arr[j].weight { return arr[i].a < arr[j].a } return arr[i].weight <= arr[j].weight }) return arr[k-1].a } func getWeight1(a int) int { num := 0 for a != 1 { if a%2 == 0 { a /= 2 } else { a = a*3 + 1 } num++ } return num }
sort.SliceStable方法
- SliceStable和Slice用法一样，只是SliceStable是一个稳定的排序，即元素相等时，不会破坏原数组的前后顺序关系
type vis2 struct { a int weight int } type byWeight2 []vis2 func getKth2(lo int, hi int, k int) int { arr := byWeight2{} for lo <= hi { arr = append(arr, vis2{lo, getWeight2(lo)}) lo++ } sort.SliceStable(arr, func(i, j int) bool { return arr[i].weight < arr[j].weight }) return arr[k-1].a } func getWeight2(a int) int { num := 0 for a != 1 { if a%2 == 0 { a /= 2 } else { a = a*3 + 1 } num++ } return num }
