假设给定一个二维的整形数组 nums
,元素是长度为 2 的数组,如下:
[[5,4],[6,4],[6,7],[2,3]]
目前的需求是对该数组排序,要求为将每个元素的第一个数字升序排列,如果该数字相等,则将第二个数字降序排列。
即排序后 nums
如下所示:
[[2,3],[5,4],[6,7],[6,4]]
二维的有点麻烦,我们先考虑怎样对一个一维数组进行排序。
比如,我们现在有这样的一个一维数组:
[35, 22, 189, 33, -33, 0]
我们怎样对它进行升序排序呢?
先看一下 Python (Python 3 以上版本) 是怎样做的。
nums = [35, 22, 189, 33, -33, 0]
# 第一种方式
nums.sort()
# 第二种方式
nums = sorted(nums)
从两种方式的不同调用方式可以看出差异:sort() 对原数组(列表)排序,而 sorted() 会返回一个新的数组。除此之外,sort() 只能被数组调用,而 sorted() 可以对任意可迭代对象(比如元组)进行排序。
那如果要降序排序呢?
nums = [35, 22, 189, 33, -33, 0]
# 第一种方式
nums.sort(reverse=True)
# 第二种方式
nums = sorted(nums, reverse=True)
只需要指定 reverse 参数为 True
即可。
那么 Golang 是怎样做的?
package main
import (
"sort"
)
func main() {
nums := []int{35, 22, 189, 33, -33, 0}
// 升序排序
sort.Ints(nums)
// 降序排序
sort.Sort(sort.Reverse(sort.IntSlice(nums)))
}
从调用方式上来看,可以看出 Golang 要比 Python 麻烦一些,其中,升序排序很直观。
我们数组中存储的 int 类型的元素,所以调用 sort.Ints()
。同理,如果数组中存储的浮点类型,只需调用 sort.Floats()
;如果数组中存储字符串,那么调用 sort.Strings()
。
回到我们的例子上来。如果要降序排列,我们不再调用 Ints()
,而是 Sort()
,而且函数参数也变成了 sort.Reverse(sort.IntSlice(nums))
。
这里 Sort()
接收实现了 sort.Interface
接口的类型,该接口共有下面的三种方法:
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less reports whether the element with index i
// must sort before the element with index j.
// Less 输出的是下标为 i 元素是否需要放到下标为 j 的元素之前。
//
// Less must describe a transitive ordering:
// - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
// - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
//
// Note that floating-point comparison (the < operator on float32 or float64 values)
// is not a transitive ordering when not-a-number (NaN) values are involved.
// See Float64Slice.Less for a correct implementation for floating-point values.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
而 sort.Reverse()
返回一个 sort.Interface
接口,重写了原来的 Less()
方法,调整为原来的逆序。
// Source: https://cs.opensource.google/go/go/+/refs/tags/go1.18:src/sort/sort.go;l=265
type reverse struct {
// This embedded Interface permits Reverse to use the methods of
// another Interface implementation.
Interface
}
// Less returns the opposite of the embedded implementation's Less method.
func (r reverse) Less(i, j int) bool {
return r.Interface.Less(j, i)
}
// Reverse returns the reverse order for data.
func Reverse(data Interface) Interface {
return &reverse{data}
}
然后 sort.IntSlice()
其实是整型切片的别名,并且实现了 sort.Interface
接口。
type IntSlice []int
func (x IntSlice) Len() int { return len(x) }
// x[i] < x[j] 表示的是当 x[i] < x[j] 时 x[i] 放到 x[j] 之前,即为升序。
// 如果想降序排列只需改为 x[i] > x[j]
func (x IntSlice) Less(i, j int) bool { return x[i] < x[j] }
func (x IntSlice) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
这里的 sort.IntSlice(nums)
其实就是将 nums
转换成 sort.IntSlice()
。
总之,我们先把 nums
转换成 sort.IntSlice()
,实现了 sort.Interface
接口(默认升序排列)。然后,重写 Less()
方法调整为降序,然后对该接口类型排序。
简言之,决定升序还是降序排列的是 Less()
方法。
既然这样,那有没有其它更直观的方法呢?答案是有。在 Go 1.8 中提出了新的接口 Slice
,如果要降序排列可以使用如下代码:
package main
import (
"sort"
"fmt"
)
func main() {
nums := []int{35, 22, 189, 33, -33, 0}
// 降序排序
sort.Slice(nums, func(i, j int) bool {return nums[i] > nums[j]})
fmt.Println(nums)
}
Slice
的参数除接口外,还有一个 Less
匿名函数,规则与 IntSlice
接口中的 Less
相同。
如果需要升序排列,将大于号改为小于号即可。
一维数组讲完了,回到最开始的问题,我们怎样对二维数组排序呢?
有了上面对 Golang sort 库的介绍,二维数组的排序就变得容易起来,先用第一种方法。我们需要定义一个 [][]int
别名,然后实现 sort.Interface
接口,将排序逻辑实现在 Less 方法中。
package main
import (
"sort"
"fmt"
)
type ArraySlice [][]int
func (a ArraySlice) Len() int {
return len(a)
}
func (a ArraySlice) Less(i, j int) bool {
if a[i][0] == a[j][0] {
return a[i][1] > a[j][1] // 第一个数字相等,则按照第二个数字降序排列
}
return a[i][0] < a[j][0] // 按照第一个数字降序排列
}
func (a ArraySlice) Swap(i, j int) {
a[i], a[j] = a[j], a[i]
}
func main() {
nums := [][]int{[]int{2,3},[]int{5,4},[]int{6,7},[]int{6,4}}
// 参考 Golang 降序排序部分
sort.Sort(ArraySlice(nums))
fmt.Println(nums)
}
很麻烦是吧,再用 sort.Slice
试着解决:
func main() {
nums := [][]int{[]int{2,3},[]int{5,4},[]int{6,7},[]int{6,4}}
sort.Slice(nums, func(i, j int) bool {
if nums[i][0] == nums[j][0] {
return nums[i][1] > nums[j][1]
}
return nums[i][0] < nums[j][0]
})
}
从代码中可以看出,我们只是把上面的 Less
方法传到 Slice
中。
这种方法不再需要定义新类型和实现 sort.Interface
接口,只需要明确 Less
函数,并将其作为匿名函数传到 Slice
中即可。从而,减少了代码量。
那 Python 怎样去实现这个需求呢?直接指定 key 参数即可,如下所示:
nums = [[2,3],[5,4],[6,7],[6,4]]
nums.sort(key=lambda x: (x[0], -x[-1]))
nums = sorted(nums, key=lambda x: (x[0], -x[-1]))
key 指定的是在进行比较前在每个列表元素上调用的函数,该函数的参数只能是一个。因此,如果 key 函数比较简单,可以使用 lambda 表达式。
这里 key 返回了一个元组,根据元组比较大小的原则:首先比较第一个元素的大小,若相等,继续比较第二个元素的大小。因为第二个数字需要降序(默认升序),所以我们取了相反数,从而达到降序要求。