`sort.Slice` 顺序是不确定的

Question

我正在尝试使用sort.SliceGo 标准库对字符串切片进行排序。我希望它们按字母顺序排序，但我希望空字符串出现在所有其他字符串之后（因此我不能只使用sort.Strings）。

对于 less 函数，我认为这会起作用：

func(i, j int) bool {
    return s[j] == "" || s[i] < s[j]
}

但是，我似乎会根据输入顺序得到随机答案。这是一个 MWE：

package main

import (
    "fmt"
    "math/rand"
    "sort"
    "time"
)

func main() {
    s := []string{"", "foo", "bar", "baz"}

    rand.Seed(time.Now().Unix())
    rand.Shuffle(len(s), func(i, j int) {
        s[i], s[j] = s[j], s[i]
    })
    fmt.Printf("%q\n", s)

    sort.Slice(s, func(i, j int) bool {
        return s[j] == "" || s[i] < s[j]
    })
    fmt.Printf("%q\n", s)
}

这是运行几次的输出：

$ go run ./z
["" "foo" "baz" "bar"]
["bar" "baz" "foo" ""]
$ go run ./z
["baz" "" "foo" "bar"]
["bar" "" "baz" "foo"]
$ go run ./z
["bar" "foo" "" "baz"]
["" "bar" "baz" "foo"]
$ go run ./z
["bar" "foo" "baz" ""]
["" "bar" "baz" "foo"]

Answer 1

这是因为你的less()函数没有表达你想要表达的内容。

您说您希望将空字符串排序在所有非空字符串之后。你的逻辑：

return s[j] == "" || s[i] < s[j]

这确实表明如果第二个是""，那么第一个就更少。这或多或少是正确的（除非两者都是空的，“is-less”并不是真的：它们是相等的）。但如果第一个是""而第二个不是呢？那么你的函数应该返回，false但它却返回s[i] < s[j]。如果第二个不为空，则这将是true，告诉""小于另一个，与您想要的完全相反。

正确的“is-less”关系是这样的：

sort.Slice(s, func(i, j int) bool {
    if s[j] == "" && s[i] != "" {
        return true
    }
    if s[i] == "" && s[j] != "" {
        return false
    }
    return s[i] < s[j]
})

如果只有第二个是""，您希望第一个更少。如果只有第一个是空的，您希望它“不少于”。否则使用正常顺序（按字节）。

在Go Playground上尝试一下。

请注意，如果第一个和第二个值均为空，则此函数将返回，false因为""不小于""（它们相等）。这是返回的正确值，尽管true在此处返回仍会导致正确的顺序（交换空元素将导致相同的结果），但这可能会导致更少的交换。

使用 XOR 转换逻辑

请注意，在自定义逻辑中，如果只有一个字符串为空，则会偏离正常顺序。这就是逻辑 XOR（异或）关系：a XOR b如果true只有a或只有b是true。Go 中没有逻辑XOR运算符，但a XOR b相当于a != b。

如果“检测到”一个空字符串，则结果是true第二个空字符串是否为空（else false）。所以我们可以将这种身份转换应用到我们的逻辑中：

sort.Slice(s, func(i, j int) bool {
    // Move empty elements to the end:
    if (s[i] == "") != (s[j] == "") { // If only one is empty
        return s[j] == ""
    }
    return s[i] < s[j]
})

这更短并且可能更有效，但正如您所看到的，它更难理解。仅当性能很重要时才使用此选项。在Go Playground上试试这个。