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

Question

我正在尝试使用sort.SliceGo 标准库对一段字符串进行排序。我希望它们按字母顺序排序，除了我希望空字符串出现在所有其他字符串之后（因此我不能只使用sort.Strings）。对于 less 功能，我认为这会起作用：func(i, j int) bool {    return s[j] == "" || s[i] < s[j]}但是，我似乎根据输入顺序得到随机答案。这是一个 MWE：package mainimport (    "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， telling ""is less than the other，与你想要的完全相反。

正确的“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 bis trueif onlya或 only bis 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试试这个。