Skip to content

Python 和 Golang 中的排序操作

March 27, 2022 | 12:20 AM

假设给定一个二维的整形数组 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 返回了一个元组,根据元组比较大小的原则:首先比较第一个元素的大小,若相等,继续比较第二个元素的大小。因为第二个数字需要降序(默认升序),所以我们取了相反数,从而达到降序要求。


延伸阅读

Sorting Workout in Golang by Radhakishan Surwase

golang sort 官方文档

Python3 排序指南